Программирование игр и головоломок - [53]
>СБ: 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. У нас есть два похожих отрывка в программе:
— в СБ:
>искать первое свободное поле на строке k, расположенное правее i, и придать значение этого поля величине i;
>ЕСЛИ таких полей нет ТО СБ
>ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
— в С:
>искать первое свободное поле на строке k и придать значение этого поля величине i;
>ЕСЛИ таких полей нет ТО СБ
>ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
Второй отрывок идентичен первому, если вместо того, чтобы искать первое свободное поле (что подразумевается как начальный ход), мы потребуем искать первое свободное поле после i, где i придано значение 0. Эту общую последовательность команд мы назовем И (от «искать»). Вот новая программа:
>ПРОГРАММА: k := 1; инициализировать игру; С
>С: ЕСЛИ k = 9 ТО С8
> ИНАЧЕ c[k] := 0; И
>КОНЕЦ_ЕСЛИ
>КОНЕЦ_ЕСЛИ
>И: искать первое свободное поле на строке k после c[k]
> и придать значение этого поля величине c[k];
> ЕСЛИ таких полей нет ТО СБ
> ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
>>СОК: занять k, c[k]; k := k + 1; С
>СБ: k := k − 1;
> ЕСЛИ k = 0 ТО Я
> ИНАЧЕ освободить k, c[k]
> И
> КОНЕЦ_ЕСЛИ
>С8: выписать решение;
> k := 8; освободить k, c[k], СБ
Мы можем еще немного выиграть. Значение 9 для k не может быть достигнуто иначе как после размещения ферзя на строке 8 с помощью СОК. Вместо того, чтобы проверять справедливость соотношения к = 9 в С, можно сделать это в СОК. Если нужно разместить восьмого ферзя, то бесполезно требовать «занять k, i» с тем, чтобы сразу после этого освободить указанное поле. Отсюда — новая, еще более простая программа.
>ПРОГРАММА: k := 1; инициализировать игру; С
>С: c[k] := 0; И
>И: искать первое свободное поле на строке k после c[k]
> и придать значение этого поля величине c[k];
> ЕСЛИ таких полей нет ТО СБ
> ИНАЧЕ СОК КОНЕЦ_ЕСЛИ
>>СОК: ЕСЛИ k = 8 ТО записать решение; СБ
>> ИНАЧЕ занять k, c[k]; k := k + 1; С
>СБ: k := k − 1;
> ЕСЛИ k = 0 ТО Я
> ИНАЧЕ освободить k, c[k]; >И
> КОНЕЦ_ЕСЛИ
Дальше можно выиграть не так уж много, и мы в своих преобразованиях, направленных на улучшение программы, остановимся здесь. Читатель мог бы и удивиться моему способу работать: почему нельзя сразу дать хорошую программу? Потому что, по моему мнению, ее трудно получить сразу. Я мог бы с помощью мелких замечаний представить ее вам без каких-либо промежуточных рассуждений. Читатель был бы восхищен моей сноровкой, но, может быть, заявил бы, что программы такого рода ему самому недоступны, и отказался бы и от этого упражнения, в от остальных упражнений из этого семейства. Если, напротив, читатель находит последнюю программу очевидной, то это потому, что его интуиция намного богаче моей, и он выходит из этой работы ободренный: он еще более ловок, чем автор, браво! И во всех случаях я выигрываю.
