Программа 1
Вначале рассмотрим вариант, в котором решение исходит из представления позиции на доске. Вполне обоснованно можно предположить, что позицию допустимо представить как список из восьми элементов, каждый из которых соответствует одному ферзю. Каждый элемент в списке обозначает клетку доски, на которой стоит соответствующий ферзь. Кроме того, каждая клетка на доске может быть обозначена
Глава 4. Использование структур: примеры программ
парой координат (X и Y), где каждая координата представляет собой целое число от 1 до 8. В программе эта пара может быть записана следующим образом:
X/Y
Здесь, безусловно, знак операции "/" не обозначает операцию деления, а просто позволяет объединить обе координаты одной клетки. На рис. 4.5 показано одно из решений задачи с восемью ферзями и его представление в виде списка.
а
12 3 4 5 6 7 8
Рис. 4.5. Решение задачи с восемью ферзями. Эту позицию можно представить в виде списка [1/4, 2/2, 3/7, 4/3. 5/6, 6/8, 7/5, 8/1]
После выбора такого способа представления задачу можно свести к поиску спи
ска, представленного в форме
[ tint, X2/Y2, X3/Y3 Х8/УВ]
который удовлетворяет требованию о том, что ни один ферзь не нападает на другого. Рассматриваемая процедура solution должна обеспечивать поиск соответствующей конкретизации переменных XI, Y1, Х2, Y2. . . . Х8, Y8. Но, поскольку известно, что все ферзи должны стоять на разных столбцах доски для предотвращения нападений по вертикали, можно сразу же ограничить соответствующий выбор и, тем самым, упростить задачу поиска. Таким образом, можно зафиксировать координаты X, чтобы список с решением определялся по следующему, более конкретному образцу: [ l/Vl, 2/Y2, 3/Y3, . . ., S/YB]
Мы заинтересованы в поиске решения задачи на доске с размерами 8x8. Но в программировании ключом к решению часто является рассмотрение более общей проблемы. Как это ни парадоксально, часто возникает такая ситуация, что решение более общей проблемы проще сформулировать по сравнению с более узкой, первоначальной проблемой. После этого первоначальная проблема решается как частный случай более общей проблемы.
Творческая часть решения проблемы состоит в поиске приемлемого обобщения первоначальной проблемы. В данном случае хорошая идея состоит в том, что количество ферзей (количество столбцов в списке) можно обобщить и принять равным не 8, а любому числу, включая нуль. В таком случае требование к отношению solution можно сформулировать, рассматривая два приведенных ниже случая.
| Случай 1. Список ферзей проблемы, поскольку нападения. Случай 2. Список ферзей [X/Y | Others]. |
пуст. Пустой список, безусловно, является решением при отсутствии ферзей отсутствует и возможность для
| не |
пуст. При этом он должен выглядеть примернотак:
Часть I.Язык Prolog
В случае 2 первый ферзь стоит на некоторой клетке X/Y, а остальные ферзи распределены по клеткам, обозначенным списком Others. Если этот список представляет собой одно из решений, то должны соблюдаться приведенные ниже условия.
1. Между ферзями, перечисленными в списке Others, не должно быть возможно обоюдное нападение; это означает, что сам список Others также представляет собой решение.
2. X и Y должны быть целыми числами от 1 до 8.
3. Ферзь, стоящий на клетке X/Y, не должен нападать ни на один из ферзей в списке Others.
Для разработки программы, соответствующей первому условию, можно использовать само отношение solution. Второе условие можно определить следующим образом: переменная Y должна входить в состав списка целых чисел от 1 до 8, т.е. списка (1,2,3,4,5,б, 7, В]. С другой стороны, не следует беспокоиться о выборе значения X, поскольку список с решением должен соответствовать образцу, в котором координаты X уже определены. Поэтому гарантируется, что переменная X будет иметь подходящее значение от 1 до 8. Третье условие можно реализовать еще в одном отношении, noattack. Таким образом, все эти утверждения можно записать на языке Prolog следующим образом: solution( [x/Y | Others] ) :-
solution! Others),
meiPberf Y, [1,2,3,4,5,6,7,8] ),
noattack( X/Y, Others).
Теперь осталось только определить отношение noattack: noattack; 0, Qliat)
Ситуацию, связанную с применением этого отношения, можно снова разделить на два рассматриваемых ниже случая.
1. Если список Qlist пуст, то это отношение, безусловно, является истинным, поскольку отсутствует ферзь, который мог бы подвергнуться нападению.
2. Если список Qlist не пуст, то он имеет форму (Ql | Qlistl] и должны быть удовлетворены следующие два условия:
а) ферзь, который стоит на клетке Q, не должен нападать на ферзя, стоящего
на клетке Q1;
б) ферзь, стоящий на клетке Q, не должен нападать ни на одного из ферзей в
списке Qlistl.
Для указания на то, что ферзь, стоящий на некоторой клетке, не нападает на ферзя, стоящего на другой клетке, достаточно сформулировать следующее простое условие: эти две клетки не должны находиться на одной и той же строке, на одном и том же столбце или на одной и той же диагонали. Применяемый образец решения гарантирует, что все ферзи находятся на разных столбцах, поэтому остается только явно определить следующее:
• координаты У ферзей являются разными;
• ферзи не находятся на одной и той же восходящей (если двигаться слева направо) или нисходящей диагонали; это означает, что расстояние между клетками, на которых стоят ферзи, в направлении X не должно быть равно расстоянию между клетками в направлении Y.
Законченная программа приведена в листинге 4,2. Для упрощения ее использования был введен список с образцом. Выборку этого списка можно выполнить в вопросе, заданном для выработки решений. Поэтому теперь программе можно задать следующий вопрос: ?- template! S), solution r S).
Глава 4. Использование структур: примеры программ
;
и программа начнет вырабатывать решения следующим образом:
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/13;
Листинг 4.2, Программа 1 для решения задачи с восемью ферзями
% solution! BoardPositionj- , если
% BoardPosition - список ненападающих ферзей
solution [ [] ) .
solution) (X/Y I Others] ) :- % Первый ферзь в клетке X/Y;
solution! others), * Others - список прочих ферзей
member; Y, [ 1, 2, 3, 4,5,6,7,8] >,
noattack( x/Y, Others). % Первый ферзь не нападает на других
noattackf, _,[]). % Объект для нападения отсутствует
noattackf X/Y, [Xl/Yl I Others] ) :-
Y -У- Yl, % Разные координаты У
Y1-Y -У- Х1-Х, % Разные диагонали
Y1-Y =4- Х-Х1, noattackf X/Y, Others).
member( Item, [Item I Rest] ).
member[ Item, [First I Rest] ) :-member! Item, Rest) .
% Образец решения
template! [1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,B/YB] ).