Программа 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]).