Календарный план. 
Программное решение задачи о 8 ферзях

Теоретическая часть

Поиск алгоритма

Задача состоит в том, чтобы сделать программу, генерирующую все конфигурации восьми ферзей на шахматной доске из 8×8 полей, так, чтобы ни один ферзь не мог взять никакого другого ферзя. Это значит, что в искомых конфигурациях никакие два ферзя не могут находиться на одной горизонтали, на одной вертикали или на одной диагонали. У нас нет оператора, генерирующего все эти конфигурации: именно этот оператор мы и должны получить. Ныне (весьма общий!) подход для решения такой проблемы состоит в следующем. Назовем искомое множество конфигураций множеством A; будем искать множество конфигураций B со следующими свойствами:

• 1. множество A является подмножеством множества B; мы можем получить оператор, генерирующий все элементы множества B.
• 2. если задан элемент из множества B, то нетрудно установить, принадлежит ли он также множеству A;
• 3. мы можем сделать оператор, генерирующий все элементы множества B.

При помощи генератора (3) элементов множества B можно генерировать по очереди все элементы из B; к ним будет применяться логический критерий (2), который решает, должны ли эти элементы пропускаться или передаваться дальше, генерируя таким образом элементы множества A. Благодаря условию (1) этот алгоритм выработает все элементы множества A.

Следует сделать три замечания:

• 1. Если все наши рассуждения имеют смысл, то множество B не идентично множеству A, и, поскольку оно должно содержать A в качестве подмножества, оно должно быть больше. Лучше однако, выбрать множество B «как можно меньшим»: чем больше элементов будет в нем, тем больше придется отбрасывать элементов в соответствии с критерием (2).
• 2. Мы должны искать такой критерий принятия решения, который «дешев» в применении или, по крайней мере, «дешевым» (в среднем) должно быть установление того, что некий элемент из B не принадлежит множеству A.
• 3. Предполагается, что генерировать элементы множества B легче, чем непосредственно генерировать элементы множества A. Если, тем не менее, генерация элементов множества B все же представляет трудности, то мы пересмотрим наш шаблон рассуждений, повторно применим тот же прием и будем искать еще большее множество конфигураций C, содержащее B как подмножество и т. д.

Выше мы наметили весьма общий подход, применимый для многих очень различных задач. Когда мы сталкиваемся с конкретной задачей, т. е. с конкретным искомым множеством A, то, конечно, проблема состоит в выборе подходящего множества B. Оптимист мог бы подумать, что это легкое дело, так как возможен следующий прием. Мы перечисляем все взаимно независимые условия, которым должны удовлетворять наши элементы множества B, и затем отбрасываем одно из этих условий. Иногда этот прием срабатывает, но как общий прием, он слишком наивен; если мы захотим увидеть его недостатки, нужно только вслепую применить его к задаче восьми ферзей. Мы можем охарактеризовать наши решения двумя условиями:

• 1. на доске есть восемь ферзей
• 2. никакие два ферзя не могут взять друг друга.

Отбрасывание любого из этих условий дает для множества B следующие альтернативы.

B1: все такие конфигурации из N ферзей на доске, в которых никакие два ферзя не могут взять друг друга.

B2: все конфигурации из 8 ферзей на доске.

Ну, хорошо, на этом этапе нашего рассмотрения, находясь в некотором «недоумении», мы заботимся не столько об эффективности нашей конечной программы, сколько об эффективности нашего процесса мышления! Так что, если мы решаем сделать список свойств решений в надежде найти ключ, то это, скорее, обходной, мы не должны затрачивать слишком много мыслительной энергии на такой поиск, другими словами: для начала мы должны ограничиться его очевидными свойствами.

a) Никакая горизонталь не может содержать более одного ферзя; нужно разместить 8 ферзей, и доска содержит 8 горизонталей. Как результат, мы можем заключить, что каждая горизонталь будет содержать ровно одного ферзя.

b) Аналогично мы заключаем, что каждая вертикаль будет содержать ровно одного ферзя.

c) Есть 15 «восходящих» диагоналей, каждая из которых содержит не более одного ферзя, т. е. 8 восходящих диагоналей содержат ровно по одному ферзю, 7 восходящих диагоналей являются пустыми.

d) Аналогично заключаем, что 8 нисходящих диагоналей содержат ровно по одному ферзю, а 7 являются пустыми.

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

Последнее свойство является очень важным. В нашей прежней терминологии это свойство кое-что говорит нам о любой непустой конфигурации из множества B1. И наоборот, оно говорит нам, что любая непустая конфигурация из множества B1 может быть сгенерирована (N разными способами!) расширением конфигурации из B1 с N-1 ферзями еще одним ферзем. Если мы начинаем с какого-то решения (которое является конфигурацией восьми ферзей из множества B1) и удаляем одного ферзя, то мы получаем конфигурацию семи ферзей из множества B1; удаление еще одного ферзя приведет снова к конфигурации из множества B1, и мы можем продолжать этот процесс, пока шахматная доска не опустеет. Мы забраковали B1 из-за того, что оно слишком большое, но, может быть, мы сможем найти подходящее его подмножество, такое, что каждая непустая конфигурация в нем окажется одно-ферзевым расширением только одной конфигурации из этого подмножества. Это «свойство расширения» подразумевает, что мы собираемся рассматривать конфигурации, в которых меньше 8 ферзей, и что мы хотели бы формировать новые конфигурации, добавляя по одному ферзю к имеющимся конфигурациям — по-видимому, это сравнительно простая операция. Итак, мы сосредоточим наше внимание непосредственно на генерации элементов (все еще таинственного) множества B. В каком порядке это делать? И тут опять возникает вопрос, которому до сих пор мы не уделяли ни малейшего внимания: в каком порядке мы собираемся генерировать решения, т. е. элементы множества A? Можно ли сделать разумное предположение на этот счет в надежде, что оно поможет нам распутать клубок?

Но до этого нам нужно спросить себя: как мы будем характеризовать решения, когда они у нас будут? Чтобы охарактеризовать решение, мы должны задать позиции 8 ферзей. Ферзи сами по себе являются неупорядоченными, но для горизонталей и вертикалей это не так: мы можем предположить, что они нумеруются от 0 до 7. Согласно свойству а), которое говорит нам, что каждая горизонталь содержит ровно одного ферзя, мы можем упорядочить ферзей в соответствии с номерами занимаемых ими горизонталей. Тогда каждая конфигурация из 8 ферзей может быть задана значением integer array x[0:7], где x[i] - номер вертикали, занимаемой ферзем в i-й горизонтали.

Каждое решение тогда представляет собой «8-цифорвое слово» (х[0].. х[7]), единственным имеющим смысл порядком генерации этих слов является, я думаю, алфавитный порядок.

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

Сначала мы должны сгенерировать все решения с х[0] = 0, затем решения с х[0] = 1 и т. д.; из решений с фиксированным значением х[0] = 0 (должны сначала генерироваться те, у которых х[1] = 0 если они есть), затем те, у которых х[1] = 1 (если есть), затем те, у которых х[1] = 2 (если есть) и т. д. Другими словами, ферзь с горизонтали 0 помещается на вертикаль 0 — скажем, в клетку в верхнем левом углу доски — и остается там до тех пор, пока не все элементы A (и B) с ферзем 0 в этой позиции не будут сгенерированы, и только затем он перемещается на одну клетку вправо, в следующую вертикаль. Для каждой позиции ферзя 0 ферзь 1 будет перемещаться слева направо в горизонтали 1 — перескакивая через клетки, которые находятся под угрозой ферзя 0; - для каждой комбинированной позиции первых двух ферзей ферзь 2 перемещается по горизонтали 2 слева направо, пропуская все клетки, находящиеся под угрозой предыдущих ферзей, и т. д.

Но теперь мы уже нашли множество B! Оно несомненно является подмножеством множества B1: множество B состоит из всех конфигураций, в которых по одному ферзю в каждой из первых N горизонталей, причем никакие два ферзя не могут взять друг друга.

Установив наш вариант множества B, мы обнаруживаем, что столкнулись с задачей генерации его элементов в алфавитном порядке. Мы попытаемся проделать это при посредстве оператора «ГЕНЕРИРОВАТЬ СЛЕДУЮЩИЙ ЭЛЕМЕНТ B», что приведет к программе следующей структуры:

ИНИЦИАЛИЗИРОВАТЬ ПУСТУЮ ДОСКУ;

repeat ГЕНЕРИРОВАТЬ СЛЕДУЮЩИЙ ЭЛЕМЕНТ В;

if N = 8 then ПЕЧАТАТЬ КОНФИГУРАЦИЮ.

until В ИСЧЕРПАНО, но она не очень удобна для нас по двум причинам.

Во-первых, мы не имеем готового критерия распознавания последнего элемента из B, если мы его встретим, и, по всей вероятности, мы должны обобщить оператор «ГЕНЕРИРОВАТЬ СЛЕДУЮЩИЙ ЭЛЕМЕНТ B» так, чтобы он вырабатывал индикацию порождал указание «B ИСЧЕРПАНО», когда он применяется к последнему «истинному» элементу множества B. Во-вторых, не вполне очевидно, как реализовать оператор «ГЕНЕРИРОВАТЬ СЛЕДУЮЩИЙ ЭЛЕМЕНТ B»: число ферзей на доске может оставаться неизменным, может уменьшаться и может увеличиваться.

Итак, эта структура не слишком привлекательна. Что тут можно сделать? До тех пор пока мы рассматриваем последовательность конфигураций из множества B как единую и однородную, не разделяем ее на ряд подпоследовательностей, соответствующая программная структура будет оставаться единственным циклом, как в только что очерченной программе. Поскольку мы ищем альтернативную программную структуру программы, то следовательно мы должны спросить себя: «Как мы можем сгруппировать последовательности конфигураций из множества B в ряд подпоследовательностей?» .

Понимая, что последовательность конфигураций из множества B должна генерироваться в алфавитном порядке, и думая об главном подразделении в словаре — а именно по первой букве — первое группирование является очевидным: по позиции ферзя 0.

Генерация всех элементов множества B — если мы забудем на время о необходимости печатать элементы, которые принадлежат также подмножеству A, — представляется в первом приближении такой.

h:= 0;

repeat УСТАНОВИТЬ ФЕРЗЯ В КЛЕТКУ H;

ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ С ФИКСИРОВАННЫМ ФЕРЗЕМ 0;

ПЕРЕМЕСТИТЬ ФЕРЗЯ;

h:= h + 1.

until h = 8.

где операторы «УСТАНОВИТЬ ФЕРЗЯ» и «ПЕРЕМЕСТИТЬ ФЕРЗЯ» относятся к нулевой горизонтали, т. е., к первой свободной горизонтали или последней занятой соответственно.

Но теперь вопрос повторяется: как мы сгруппируем все конфигурации с фиксированным положением ферзя 0? Мы уже получили ответ: в порядке возрастания номеров вертикалей позиции ферзя 1, т. е.

H2:= 0;

repeat if ПОЛЕ H2 СВОБОДНО do.

begin УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ H2;

ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ С ФИКСИРОВАННЫМИ ПЕРВЫМИ ДВУМЯ ФЕРЗЯМИ;

ПЕРЕМЕСТИТЬ ФЕРЗЯ.

end;

H2:= H2 + 1.

until H2 = 8.

Для «ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ C ФИКСИРОВАННЫМИ ПЕРВЫМИ ДВУМЯ ФЕРЗЯМИ» можно написать аналогичный фрагмент программы, и т. д.: вкладывая эти их один в другой, мы получили бы корректную программу с восемью вложенными циклами, но они будут очень-очень похожими. Это имеет два недостатка:

• 1. требуется слишком много писанины
• 2. дается программное решение нашей задачи для шахматной доски из 8 * 8 клеток, но решение той же головоломки для доски из, скажем, 10×10 клеток, потребовало бы новой (еще более длинной) программы. Мы захотим обойти это, используя схожесть циклов.

Тогда мы должны ответить на два вопроса:

• 1. можем ли мы сделать циклы совершенно идентичными?
• 2. можем ли мы получить выгоду из их схожести?

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

if ПОЛЕ [0, h] СВОБОДНО do.

Самый внутренний цикл отличается тем, что коль скоро на доске должны быть размещены 8 ферзей, то нет смысла генерировать все конфигурации с фиксированными позициями этих ферзей, так как доска уже заполнена. Вместо этого конфигурация должна быть отпечатана, поскольку мы нашли элемент множества B, который также является элементом множества A. Мы можем отобразить самый внутренний цикл и семь охватывающих его циклов друг на друга, заменив строку «ГЕНЕРИРОВАТЬ» на строку.

if ДОСКА ЗАПОЛНЕНА then ПЕЧАТАТЬ КОНФИГУРАЦИЮ.

else ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ, РАСШИРЯЮЩИЕ ИМЕЮЩУЮСЯ Теперь единственное различие между восемью циклами состоит в том, что каждый цикл имеет «свое собственное h». Когда мы достигли этого этапа, мы можем получить утвердительный ответ на второй вопрос. Последовательное прохождение через восемь вложенных циклов может выполняться с помощью рекурсивной процедуры, скажем, «генерировать», описывающей однократное выполнение цикла. При ее использовании вся программа сводится к виду ИНИЦИАЛИЗИРОВАТЬ ПУСТУЮ ДОСКУ;

генерировать где процедура «генерировать» определяется рекурсивно следующим образом:

procedure генерировать;

begin integer h;

h:= 0;

repeat if КЛЕТКА H СВОБОДНА do.

begin УСТАНОВИТЬ ФЕРЗЯ В КЛЕТКУ H;

if ДОСКА ЗАПОЛНЕНА then ПЕЧАТАТЬ КОНФИГУРАЦИЮ.

else генерировать;

ПЕРЕМЕСТИТЬ ФЕРЗЯ.

end.

h:= h + 1.

until h = 8.

end.

Каждая активизация «генерировать» вводит свою отдельную локальную переменную h, заменяя тем самым переменные H2, H3,…, которые потребовались бы нам при написании восьми циклов, вложенных друг в друга. КЛЕТКА H СВОБОДНА и УСТАНОВИТЬ ФЕРЗЯ В КЛЕТКУ H опять ссылаются на первую свободную горизонталь, операция ПЕРЕМЕСТИТЬ ФЕРЗЯ — на последнюю занятую горизонталь.

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

integer array x [0:7].

задающий по порядку номера вертикалей, занимаемых ферзями. Нам нужно отдельное соглашение о представлении номеров ферзей на доске. Давайте введем integer n, такое, что.

N = число ферзей на доске.

x[i] = при 0 < i n: номер вертикали, занимаемой ферзем из i-ой горизонтали Сочетание массива x и скаляра n является достаточным для фиксации любой конфигурации из множества B, причем это будут только конфигурации с шахматной доски. Следовательно, у нас нет логической необходимости в дополнительных переменных, хотя мы и введем еще несколько, поскольку с практической точки зрения мы можем хорошо их использовать Проблема состоит в том, что c с только вышеприведенным материалом анализ того, находится ли под угрозой данная клетка, оказывается дорогостоящим и требует значительных затрат времени. Здесь мы можем применить стандартный прием, именуемый «расплата объемом памяти за время вычислений». Образец этого приема следующий.

В его простейшей форм мы имеем дело с вычислением, которому регулярно требуется значение функции FUN (arg), где «FUN» — заданная вычислимая функция, определенная на текущих значениях одной или нескольких переменных, которые все вместе названы «arg». В версии программы 1 хранится только значение arg, и FUN (arg) вычисляется всякий раз, когда это нужно. В версии программы 2 вводится дополнительная переменная, скажем, «fun», которая служит для сохранения значения «FUN (arg)», связанного с текущим значением «arg» .

В версии 1 будет.

arg:=… (т.е., присваивание значения) а в версии 2 (более эффективной).

arg:=…; fun:= FUN (arg),.

таким образом поддерживается справедливость отношения.

fun:= FUN (arg).

Введение

этого избыточного дополнительного ингредиента является одним из самых мощных способов для программиста повышения эффективности программы. Конечно же, мы должны применять его творчески!

Очень часто ситуация не так проста, как это, и теперь мы приходим ко второй причине для введения такой переменной, как «fun». Часто бывает очень неудобно вычислять FUN (arg) «из ничего» для произвольных значений arg, тогда как гораздо легче вычислить, как изменится значение FUN (arg) при изменении значения arg. В таком случае модификация значения fun более связана с природой функциональной зависимости и историей переменной arg, что подразумевает.

arg:=…; fun:= FUN (arg).

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

Как это сделать? Можно, скажем, представить себе булевский массив из 8×8 элементов, указывающих для каждой клетки, свободна ли она. Если мы делаем это для всей доски, то добавление ферзя может повлиять на 29 клеток; удаление ферзя, однако, является мучительным процессом, поскольку ниоткуда не следует, что клетки, которым не больше угрожает он, на самом деле свободны: они могут находиться под угрозой других ферзей. Против этого есть стандартное средство, а именно, связывание с каждой клеткой не булевской переменной, а целочисленного счетчика, подсчитывающего число ферзей, угрожающих этой клетке. Добавление ферзя означает увеличение на 1 значений до 29 счетчиков, удаление ферзя означает уменьшение на «1» значений до 29 счетчиков, и клетка является свободной, когда ее счетчик равен нулю. Мы можем действовать таким способом, но возникает вопрос, не переусердствуем ли мы: 29 модификаций — это довольно много.

Каждая клетка, состоянием (свободна/несвободна) которой мы интересуемся, держит под прицелом горизонталь (которая свободна по определению, так что нам не нужно об этом заботиться), одну из 8 вертикалей (которая вся должна быть пустой), одну из 15 восходящих диагоналей (которая вся должна быть пустой) и одна из 15 нисходящих диагоналей (которая вся должна быть пустой). Это предполагает, что нам нужно отслеживать:

• 1. свободные вертикали
• 2. свободные восходящие диагонали
• 3. свободные нисходящие диагонали.

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

boolean array col [0:7].

где «col[i]» означает, что i-я вертикаль свободна.

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

boolean array up [-7:+7], down [0:14], чтобы отслеживать свободные диагонали.

Вопрос о том, является ли поле свободным, становится таким:

col[h] and up[n-h] and down [n+h].

а установка или удаление ферзя сводятся к модификации трех булевских элементов, по одному в каждом массиве.

Без дополнительных переменных ПЕРЕМЕСТИТЬ ФЕРЗЯ содержала бы только «n:= n — 1», теперь же мы захотим знать также и номер ее вертикали, т. е., мы заменяем ее на ПЕРЕМЕСТИТЬ ФЕРЗЯ ИЗ КЛЕТКИ H. В результирующей программе вводится переменная «k» для общих вычислительных надобностей, операторы и выражения снабжаются пояснительных меток.

Этим завершается рассмотрение нашей задачи; программа генерирует 92 конфигурации.

begin integer n, k; integer array x[0:7]; boolean array col[0:7], up[-7:+7], down[0:14];

procedure генерировать;

begin integer h; h:= 0;

repeat if КЛЕТКА H СВОБОДНА: (col[h] and up[n-h] and down[n+h]) do.

begin УСТАНОВИТЬ ФЕРЗЯ В КЛЕТКУ H:

x[n]: = h; col[h]: = false; up[n-h]: = false; down[n+h]: = false; n:= n + l;

if ДОСКА ЗАПОЛНЕНА: (n = 8) then.

begin ПЕЧАТАТЬ КОНФИГУРАЦИЮ:

k:= 0; repeat print (x[k]); k:= k + 1 until k = 8; newline.

end.

else генерировать;

ПЕРЕМЕСТИТЬ ФЕРЗЯ С ПОЛЯ H:

n:=n-1;

down[n+h]: = true; up[n-h]: = true; col[h]: = true

end;

h:= h + l.

until h=8.

end;

ИНИЦИАЛИЗИРОВАТЬ ПУСТУЮ ДОСКУ:

n:= 0;

k:= 0; repeat col[k]: = true; k:= k + l until k = 8;

k:= 0; repeat up[k-7]: = true; down[k]: = true; k:= k + l until k = 15;

генерировать.

end.