Упражнение

4.6.  При поиске решения программа, приведенная на рис. 4.7, проверяет различные значения Y-координат ферзей. В каком месте программы задается порядок перебора альтернативных вариантов? Как можно без труда модифицировать программу, чтобы этот порядок изменился? Поэкспериментируйте с разными порядками, имея в виду выяснить, как порядок перебора альтернатив влияет на эффективность программы.

4.5.2. Программа 2

В соответствии с принятым в программе 1 представлением доски каждое решение имело вид

[1/Y1, 2/Y2, 3/Y3, ..., 8/Y8]

так как ферзи расставлялись попросту в последовательных вертикалях. Никакая информация не была бы потеряна, если бы X-координаты были пропущены. Поэтому можно применить более экономное представление позиции на доске, оставив в нем только Y-координаты ферзей:

[Y1, Y2, Y3, ..., Y8]

Чтобы не было нападений по горизонтали, никакие два ферзя не должны занимать одну и ту же горизонталь. Это требование накладывает ограничение на Y-координаты: ферзи должны занимать все горизонтали с 1-й по 8-ю. Остается только выбрать порядок следования этих восьми номеров. Каждое решение представляет собой поэтому одну из перестановок списка:

[1, 2, 3, 4, 5, 6, 7, 8]

Такая перестановка S является решением, если каждый ферзь в ней не находится под боем (список S — "безопасный"). Поэтому мы можем написать:

решение( S) :-

 перестановка( [1, 2, 3, 4, 5, 6, 7, 8], S),

 безопасный( S).

Рис. 4.8.  (а) Расстояние по X между Ферзь и Остальные равно 1. (b) Расстояние по X между Ферзь и Остальные равно 3

Отношение перестановка мы уже определила в гл. 3, а вот отношение безопасный нужно еще определить. Это определение можно разбить на два случая:

(1) S — пустой список. Тогда он, конечно, безопасный, ведь нападать не на кого.

(2) S — непустой список вида [Ферзь | Остальные]. Он безопасный, если список Остальные — безопасный и Ферзь не бьет ни одного ферзя из списка Остальные.

На Прологе это выглядит так:

безопасный( []).

безопасный( [Ферзь | Остальные ] :-

 безопасный( Остальные),

 небьет(Ферзь | Остальные).

В этой программе отношение небьет более хитрое.

решение( Ферзи) :-

 перестановка( [1, 2, 3, 4, 5, 6, 7, 8], Ферзи),

 безопасный( Ферзи).

перестановка( [], []).

перестановка( [Голова | Хвост], СписПер) :-

 перестановка( Хвост, ХвостПер),

 удалить( Голова, СписПер, ХвостПер).

  % Вставка головы в переставленный хвост

удалить( А, [А | Список).

удалять( А, [В | Список], [В, Список1] ) :-

 удалить( А, Список, Список1).

безопасный( []).

безопасный( [Ферзь | Остальные]) :-

 безопасный( Остальные),

 небьет( Ферзь, Остальные, 1).

небьет( _, [], _ ).

небьет( Y, [Y1 | СписY], РасстХ) :-

 Y1-Y =\= РасстХ,

 Y-Y1 =\= РасстХ,

 Расст1 is РасстХ + 1,

 небьет( Y, СписY, Расст1).

Рис. 4.9.  Программа 2 для задачи о восьми ферзях.

Трудность состоит в том, что расположение ферзей определяется только их Y-координатами, а X-координаты в представлении позиции не присутствуют в явном виде. Этой трудности можно избежать путем небольшого обобщения отношения небьет, как это показано на рис. 4.8. Предполагается, что цель

небьет( Ферзь, Остальные)

обеспечивает отсутствие нападении ферзя Ферзь на поля списка Остальные в случае, когда расстояние по X между Ферзь и Остальные равно 1. Остается рассмотреть более общий случай произвольного расстояния. Для этого мы добавим его в отношение небьет в качестве третьего аргумента:

небьет( Ферзь, Остальные, РасстХ)

Соответственно и цель небьет в отношении безопасный должна быть изменена на

небьет( Ферзь, Остальные, 1)

Теперь отношение небьет может быть сформулировано в соответствии с двумя случаями, в зависимости от списка Остальные: если он пуст, то бить некого и, естественно, нет нападений; если же он не пуст, то Ферзь не должен бить первого ферзя из списка Остальные (который находится от ферзя Ферзь на расстоянии РасстХ вертикалей), а также ферзей из хвоста списка Остальные, находящихся от него на расстоянии РасстХ + 1. Эти соображения приводят к программе, изображенной на рис. 4.9.