Жак Арсак - Программирование игр и головоломок

Будем исходить из наиболее общей ситуации. Пусть на шахматной доске уже размещено k − 1 ферзей. Обозначим это состояние буквой С (в смысле «самое общее состояние»). Это состояние раскладывается на три подсостояния:

— уже размещено по местам 8 ферзей ( k − 1 = 8): состояние С8;

— на строке с номером k есть допустимое место для ферзя: состояние СОК;

— либо строка с номером k блокирована полностью, либо все возможные поля на ней уже исследованы: СБ.

Запишем кусок программы, который различает эти три случая:

С: ЕСЛИ k = 9 ТО С8

ИНАЧЕ искать первое свободное поле на строке k и придать значение этого поля величине i ;

ЕСЛИ нет таких полей ТО СБ

ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

КОНЕЦ_ЕСЛИ

Рассмотрим теперь каждое из подсостояний.

СОК: есть свободное место в точке k , i . Туда ставим ферзя k и получаем снова самое общее состояние с еще одним размещенным ферзем.

Формально:

СОК: занять k , i ; k := k + 1; С

Если строка k блокирована, а также если она полностью исследована, то нужно изменить выбор, который был сделан для ферзя k − 1, и передвинуть его на свободное место правее (если оно есть). Это возвращение назад относится непосредственно к ферзю k − 1 и, следовательно, сохраняет только k − 2 первых ферзей, что вызывает необходимость уменьшить k на 1. Может случиться, что это приведет нас к k = 0, т. е. может случиться, что все места на строке 1 уже исследованы и, следовательно, работа закончена, что мы обозначим как состояние Я, конец программы.

СБ: k := k − 1;

ЕСЛИ k = 0 ТО Я

ИНАЧЕ найти место i ферзя k ; освободить k , i ;

найти первое свободное поле на строке k , расположенное правее i , и придать значение этого поля величине i ;

ЕСЛИ нет таких полей ТО СБ

ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

КОНЕЦ_ЕСЛИ

Когда 8 ферзей уже размещены, нужно записывать решение. Бесполезно искать другое место для восьмого ферзя, потому что если на восьмой строке и есть свободное место, то только одно. Таким образом, строка 8 оказывается полностью исследованной и нужно снова размещать 7 предыдущих ферзей. А состояние, в котором строка 8 полностью исследована, — это состояние СБ с k = 8.

С8: выписать решение;

найти место i ферзя 8;

освободить 8, i ;

k := 8; СБ

Остается пустить этот процесс в ход. В начале ни один ферзь в игре не участвует и, следовательно, k − 1 = 0. Нужна инициализация, которая бы это открыто провозглашала:

ПРОГРАММА: k := 1; инициализировать игру; С

Объединим куски. Мы получим программу, реализующую автомат, как мы уже видели в игре 12. Вы можете рассматривать имена, написанные прописными буквами (С, СБ, СОК, С8, ПРОГРАММА) как метки, позволяющие отсылать к части программы, в начале которой стоят эти имена со знаком «:» после них, и как инструкцию ПЕРЕЙТИ К, если они указаны в конце последовательности операций. Поэтому все это непосредственно переводится на совершенно любой язык.

ПРОГРАММА: k := 1; инициализировать игру; С

С: ЕСЛИ k = 9 ТО С8

ИНАЧЕ искать первое свободное поле на строке k и придать значение этого поля величине i ;

ЕСЛИ нет таких полей ТО СБ

ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

КОНЕЦ_ЕСЛИ

СОК: занять k , i ; k := k + 1; С

СБ: k := k − 1;

ЕСЛИ k = 0 ТО Я

ИНАЧЕ найти место i ферзя k ; освободить k , i ;

ИСКАТЬ первое свободное поле на строке k , расположенное правее i , и придать значение этого поля величине i ;

ЕСЛИ нет таких полей ТО СБ

ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

КОНЕЦ_ЕСЛИ

С8: выписать решение;

найти место i ферзя 8;

освободить 8, i ;

k := 8; СБ

Мы можем улучшить эту программу. Неприятно иметь необходимость находить заново место ферзя в строке, тем более, что знание этого места необходимо дли вывода на экран полученного решения. Заменим i номером c [ k ] столбца, где расположен ферзь k . Тогда искать место этого ферзя больше не нужно. Именно операция «занять k , i » и будет давать величине c [ k ] значение i . У нас есть два похожих отрывка в программе: