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

• Название: Программирование игр и головоломок
• Автор: Жак Арсак
• Издательство: Наука. Гл. ред. физ.-мат. лит.
• Жанр: Программирование
• Год: 1990
• ISBN: 5-02-013959-9

Рассматриваются способы программирования различных занимательных игр и головоломок с числами, геометрическими фигурами и др. Изложение большинства игр и головоломок ведется в несколько этапов. Сначала разъясняется сама постановка задачи и требования, предъявляемые к алгоритму ее решения.

В следующем разделе книги обсуждается сам алгоритм и возможные пути его реализации.

В конце книга по многим играм и головоломкам даются наброски их программной реализации. Используемый при этом язык типа Паскаля допускает перевод на другие широко распространенные языки программирования.

Для начинающих программистов, студентов вузов и техникумов.

---

Для задачи HR (k) необходимо знание состояния игры, получающегося после размещения первых k − 1 ферзей. Это предполагает по крайней мере, что известны столбцы, занятые этими ферзями. Может быть, следовало бы сказать больше. Обозначим символически «занять k, i» операцию, которая констатирует факт, что в столбце i на строке k помещен ферзь.

HR (k =

  ДЛЯ i := 1 ДО 8 ВЫПОЛНЯТЬ

    ЕСЛИ место k, i свободно ТО

      занять k, i

ЕСЛИ k = 8 ТО выписать решение

    ИНАЧЕ HR(к + 1)

    КОНЕЦ_ЕСЛИ

    освободить k, i

  КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Операция «освободить k, i» отменяет то, что делает операция «занять k, i». Для решения задачи нужно изложить последовательность инициализации, отмечающую, что ничего не сделано и ни один ферзь в игре не участвует, а затем вызвать HR (1).

Эта процедура рекурсивна, так как она обращается сама к себе. Тщательно изучите ее. Если вы исходите из гипотезы, что HR (k + 1) находит и выводит такие решения, у которых первые k ферзей стоят там, где они поставлены, то у вас не будет никаких затруднений в том, чтобы убедиться, что эта процедура совершенно правильна. Используйте крайние случаи: k = 8 и начальное обращение с k = 1.

Если у вас в наличии нет никакого другого языка, кроме Бейсика, или если вы раб своего языка до такой степени, что не желаете учить что-нибудь, кроме Бейсика, то вам придется писать итеративное решение. Это сложнее.

Будем исходить из наиболее общей ситуации. Пусть на шахматной доске уже размещено 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. У нас есть два похожих отрывка в программе:

— в СБ:

искать первое свободное поле на строке 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]