Программирование игр и головоломок
Шрифт:
— мы пробегаем все поля на строке k,
— если поле свободно (т. е. не бьется уже поставленными ранее ферзями), то мы ставим на него ферзя k и решаем ту же задачу для k + 1.
При k = 8 задача проще всего. Не может быть более одного свободного столбца. Если он есть, то мы ставим туда последнего ферзя и записываем полученное таким образом решение. Если свободного столбца нет, то нет и решения.
Для задачи HR (k) необходимо знание состояния игры, получающегося после размещения первых k– 1 ферзей. Это предполагает по крайней мере, что известны столбцы, занятые этими
Операция «освободить k, i» отменяет то, что делает операция «занять k, i». Для решения задачи нужно изложить последовательность инициализации, отмечающую, что ничего не сделано и ни один ферзь в игре не участвует, а затем вызвать HR (1).
Эта процедура рекурсивна, так как она обращается сама к себе. Тщательно изучите ее. Если вы исходите из гипотезы, что HR (k + 1) находит и выводит такие решения, у которых первые k ферзей стоят там, где они поставлены, то у вас не будет никаких затруднений в том, чтобы убедиться, что эта процедура совершенно правильна. Используйте крайние случаи: k = 8 и начальное обращение с k = 1.
Если у вас в наличии нет никакого другого языка, кроме Бейсика, или если вы раб своего языка до такой степени, что не желаете учить что-нибудь, кроме Бейсика, то вам придется писать итеративное решение. Это сложнее.
Будем исходить из наиболее общей ситуации. Пусть на шахматной доске уже размещено k– 1 ферзей. Обозначим это состояние буквой С (в смысле «самое общее состояние»). Это состояние раскладывается на три подсостояния:
— уже размещено по местам 8 ферзей (k– 1 = 8): состояние С8;
— на строке с номером k есть допустимое место для ферзя: состояние СОК;
— либо строка с номером k блокирована полностью, либо все возможные поля на ней уже исследованы: СБ.
Запишем кусок программы, который различает эти три случая:
Рассмотрим теперь каждое из подсостояний.
СОК: есть свободное место в точке k, i. Туда ставим ферзя k и получаем снова самое общее состояние с еще одним размещенным ферзем.
Формально:
Если строка k блокирована, а также если она полностью исследована, то нужно изменить выбор, который был сделан для ферзя k– 1, и передвинуть его на свободное место правее (если оно есть). Это возвращение назад относится непосредственно к ферзю k– 1 и, следовательно, сохраняет только k– 2 первых ферзей, что вызывает необходимость уменьшить k на 1. Может случиться, что это приведет нас к k = 0, т. е. может случиться, что все места на строке 1 уже исследованы и, следовательно, работа закончена, что мы обозначим как состояние Я, конец программы.
Когда 8 ферзей уже размещены, нужно записывать решение. Бесполезно искать другое место для восьмого ферзя, потому что если на восьмой строке и есть свободное место, то только одно. Таким образом, строка 8 оказывается полностью исследованной и нужно снова размещать 7 предыдущих ферзей. А состояние, в котором строка 8 полностью исследована, — это состояние СБ с k = 8.
Остается пустить этот процесс в ход. В начале ни один ферзь в игре не участвует и, следовательно, k– 1 = 0. Нужна инициализация, которая бы это открыто провозглашала:
Объединим куски. Мы получим программу, реализующую автомат, как мы уже видели в игре 12. Вы можете рассматривать имена, написанные прописными буквами (С, СБ, СОК, С8, ПРОГРАММА) как метки, позволяющие отсылать к части программы, в начале которой стоят эти имена со знаком «:» после них, и как инструкцию ПЕРЕЙТИ К, если они указаны в конце последовательности операций. Поэтому все это непосредственно переводится на совершенно любой язык.