Программирование игр и головоломок
Шрифт:
— мы пробегаем все поля на строке 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, ПРОГРАММА) как метки, позволяющие отсылать к части программы, в начале которой стоят эти имена со знаком «:» после них, и как инструкцию ПЕРЕЙТИ К, если они указаны в конце последовательности операций. Поэтому все это непосредственно переводится на совершенно любой язык.