Остальные).
принадлежит( X, [X | L] ).
принадлежит( X, [Y | L] ) :-
принадлежит( X, L).
% Шаблон решения
шаблон( [1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]).
Рис. 4. 7. Программа1 для задачи о восьми ферзях.
Система будет генерировать решения в таком виде:
S = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1];
S = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1];
S = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1].
. . .
Упражнение
4. 6. При поиске решения программа, приведенная на рис. 4.7, проверяет различные значения Y-координат ферзей. В каком месте программы задается порядок перебора альтернативных вариантов? Как можно без труда модифицировать программу, чтобы этот порядок изменился? Поэкспериментируйте с разными порядками, имея в виду выяснить, как порядок перебора альтернатив влияет на эффективность программы.
4. 5. 2. Программа 2
В соответствии с принятым в программе 1 представлением доски каждое решение имело вид
[1/Y1, 2/Y2, 3/Y3, ..., 8/Y8]
так как ферзи расставлялись попросту в последовательных вертикалях. Никакая информация не была бы потеряна, если бы Х-координаты были пропущены. Поэтому можно применить более экономное представление позиции на доске, оставив в нем только 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. (а) Расстояние по Х между Ферзь и Остальные равно 1.
(b) Расстояние по Х между Ферзь и Остальные равно 3
Отношение перестановка мы уже определила в гл. 3, а вот отношение безопасный нужно еще определить. Это определение можно разбить на два случая:
(1) S - пустой список. Тогда он, конечно, безопасный, ведь нападать не на кого.
(2) S - непустой список вида [Ферзь | Остальные]. Он безопасный, если список Остальные - безопасный и Ферзь не бьет ни одного ферзя из списка Остальные.
На Прологе это выглядит так:
безопасный( [ ]).
безопасный( [Ферзь | Остальные ] :-
