Программирование игр и головоломок

Рисунок 23 представляет одно из состояний игры в «Отшельника». Свободные места представлены точками, шашки — знаком x. Как показывает название, это — игра для одного-единственного лица. При каждом ходе нужно съесть шашку, заставляя перепрыгнуть через нее другую шашку так, чтобы попасть на свободное поле — либо горизонтально, либо вертикально. Так, на рис. 23 имеется 4 возможных хода:

— шашка, лежащая на пересечении планок креста, может ваять шашку, расположенную непосредственно над ней, и попасть в середину верхней строки (шашка, через которую перепрыгнули, а именно, расположенная в вершине креста, удаляется из игры);

— та же шашка может взять шашку слева;

— или шашку справа;

— наконец, шашка в центре игрового поля может взять шашку под ней, расположенную в низу креста.

Цель игры состоит в том, чтобы удалить все шашки, кроме одной. Число необходимых для этого ходов легко подсчитать: поскольку при каждом ходе берется одна шашка, то число ходов равно числу подлежащих удалению шашек. В случае креста на рис. 23 вам осталось сделать до конца еще 5 ходов.

Составьте программу для отшельника. Вы даете компьютеру начальную конфигурацию, например крест на рис. 23. Он сообщает вам ходы, которые приводят к решению.

Другие конфигурации приведены на рис. 24.

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

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

В позиции, к которой мы пришли, никакой симметрии уже нет. Ее-то и возьмите как исходную.

Ваша программа дает только одно решение или все возможные решения?

Ханойские башни. Печальный конец Паскаля Младшего

Очень мало говорят о печальном конце Паскаля Младшего. Его бывшие коллеги знали, что у него возникли проблемы, заставившие поместить его в психиатрический госпиталь. Теперь когда он умер, я могу опубликовать письмо, которое он мне послал в свое время; оно уже больше не может причинить ему вреда…

«Господин профессор,

Я не знаю, помните ли вы меня: я был вашим учеником в Институте программирования. Конечно, у вас их столько было… После того, как я окончил институт, я поступил на работу программистом-аналитиком в бюро обслуживания. Я был на очень хорошем счету. Я следовал вашим урокам: использовал программирование «сверху-вниз», я выводил свои циклы в программах, используя пост- и предусловия и инварианты. Мои программы работали верно с первого запуска, с точностью до опечаток. Короче, по прошествии нескольких лет я сказал себе, что у меня будет более интересная работа, если я буду вести ее на свой собственный счет. Поэтому я нее подготовил, нашел помещение. Я подал в отставку и взял все отложенные отгулы, на которые я имел право. Будучи холостым, я, вообще говоря, брал очень мало выходных дней, настолько меня захватывала моя работа. Но, собираясь испытать счастья в большом деле и становясь своим собственным работодателем, я хотел получить настоящий отдых.

Право, я не знаю, как это меня по рекламному объявлению занесло в бюро путешествий «Посетите таинственную Индию». И вот я отправился с тремя десятками других в организованное путешествие. Конечно, я должен был задуматься раньше, то ли я выбрал, что мне нужно. Оказалось, что я с трудом переношу беспрерывную болтовню то одних, то других; это мешало мне думать о чем-нибудь своем. Мне пришлось примириться с тем, что мне придется думать о чем-то еще, кроме написания какой-то упирающейся программы! Детали этого путешествия несущественны вплоть до дня, когда нас привезли в монастырь в предгорьях Гималаев.

Монах, который нас принял, говорил на отличном французском. Сообщение, которое он сделал о монастыре, свидетельствовало о свободном владении нашим языком. Это должно было показаться мне подозрительным. Он ввел нас в помещение и, с того момента как я вошел, я смог только выдавить «ох» изумления: мы увидели монаха, который занимался знаменитейшей игрой в Ханойские башни. Диски были, очевидно, из золота, и я сразу угадал, даже не считая, их ровно 50. Монах объяснял игру посетителям: