1.10.1. ЗАДАЧА О ФЕРЗЯХ

Рассмотрим классическую задачу о восьми ферзях [Хен 83]. Как известно, в шахматах ферзи атакуют друг друга по горизонтали, по вертикали или по диагоналям шахматной доски. Задача состоит в том, чтобы найти такое размещение 8 ферзей на доске 8х8, чтобы никакие два ферзя не атаковали друг друга.

Мы будем решать несколько более общую задачу, считая, что требуется разместить n ферзей на доске размера nхn.

Занумеруем вертикали и горизонтали доски числами от 1 до n. Будем говорить, что поле имеет координаты (i,j) или, другими словами, является полем (i,j), если оно находится на пересечении i-й вертикали и j-й горизонтали.

Заметим, что для полей любой диагонали, идущей слева направо и снизу вверх, сумма номеров столбцов и строк - постоянна, и что для полей любой диагонали, идущей слева направо и сверху вниз, разность номеров столбцов и строк - постоянна.

Таким образом, поля (i,j) и (i1,j1) лежат на одной диагонали, если i+j = i1+j1 или i-j = i1-j1. Это условие легко проверить. А именно, если вычисление тропы

завершается успешно, поля (i,j) и (i1,j1) лежат на одной диагонали.

Теперь надо выбрать способ, которым мы будем кодировать расположение ферзей на доске.

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

I1 J2 ... In

где число Ik означает, что на k-й вертикали ферзь находится на горизонтали с номером Ik.

Будем строить позицию постепенно, заполняя вертикали одну за другой. При этом всякий раз, пытаясь поставить на доску очередного ферзя, надо проверять, не атакован ли он одним из уже стоящих на доске ферзей. Предположим, что на доске уже стоит k ферзей на вертикалях 1, 2, ..., k. Будем кодировать частично построенную позицию как последовательность чисел

где Im - номер горизонтали для ферзя на m-й вертикали.

Теперь мы можем определить предикат Attack?, который выдает пустое выражение, если поле (i,j) атаковано ферзями, уже стоящими на доске, и выдает неуспех, если это поле не атаковано.

Отметим, что проверку i1=i можно и убрать, поскольку в нашей программе функция Attack? будет вызываться только таким образом, что параметр i будет заведомо больше, чем номера столбцов у тех ферзей, которые уже поставлены на доску.

Теперь опишем функцию Next-Queen?, которая пытается добавить к частично построенной позиции нового ферзя, перебирая различные горизонтали. Если ферзя удается поставить, но этот ферзь не последний, делается попытка поставить следующего ферзя и т.д. Если очередного ферзя поставить не удается, происходит возврат назад и делается попытка переставить на новое место предыдущего ферзя.

Некоторые тонкости в определении функции Next-Queen? заслуживают пояснения. Во-первых, конструкция поиска делает попытку вычислить свое тело, последовательно пробуя для переменной j значения 1, 2, ..., n и увеличивая значение переменной j на 1 после каждой неудачной попытки вычислить свое тело.

Во-вторых, неудача при вычислении тела конструкции поиска может возникнуть по двум причинам: либо поле (i,j) атаковано ферзями, уже стоящими на доске, и тогда успешно завершится вызов функции Attack?, а значит потерпит неудачу отрицание этого условия, либо очередного ферзя можно поставить на поле (i,j), но не удается разместить следующих ферзей, и тогда терпит неудачу рекурсивный вызов функции Next-Queen?.

Теперь осталось определить последнюю функцию Solution?, которая имеет один аргумент - размер доски, и выдает решение задачи, если оно существует, либо терпит неудачу, если решение не существует: