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

Я действую следующим образом. Я отыскиваю заполнение прямоугольника; параллельно меньшей стороне, Рисунок 39 показывает возможную ситуацию в ходе выполнения этого плана.

Рассмотрим тогда конфигурацию, окружающую крайнее левое из свободных полей. Обозначив через «x» занятые поля и полагая свободные поля точками, мы получим не более 7 возможных случаев (если вы привыкли к двоичной нумерации, то это покажется вам очевидным): см. рис. 40.

В крайней левой ситуации будем искать способ занять свободное поле на верхней строке. Но ни один из кусков ни в какой из их ориентации не подходит. Вы не можете использовать ни крест, ни «F», ни «Z». Кусок «С» можно использовать только с большей стороной по вертикали…

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

— очень неудобно иметь программу, которая работает несколько десятков минут (порядка 45 на моем микрокомпьютере), а мы ничего не знаем о том, что в ней происходит, Это неудобно как собственно для работы, так в для того, чтобы сразу же задавать вопросы. А если, хотя бы это и было ошибкой набора, вдруг найдется бесконечный цикл…

— этот вывод позволяет видеть работу компьютера. Видно, как один за другим исследуются куски, как игровое поле более или менее наполняется (иногда вплоть до одиннадцати кусков. Если вы пытались решить эту головоломку вручную, отметили ли вы, какое впечатление производит нехватка одного куска? Однако это просто: если остается островок площади 5, то он обязательно имеет форму одного из игровых кусков…). Затем она почти полностью опустошается, и возобновляется заполнение…

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

Для вывода на экран я не нашел хорошего рисунка, потому что у меня нет ни графического, ни полуграфического экрана — только алфавитно-цифровой. Каждому куску я сопоставил букву и вывожу куски на экран в виде подходящим образом расположенных пяти букв. Такой вывод показан на рис. 41.

Я представляю игру внутренним образом в виде цепочки символов по двум причинам:

— используемый мною язык (LSE) в используемой мною версии является одним из наиболее эффективных языков для работы с цепочками символов. Это почти также быстро, как если использовать таблицы. Я могу очень быстро найти первое свободное место, я могу очень быстро узнать, свободно ли поле (является ли символ на этом месте в цепочке точкой?);

— вывод мгновенный: я вывожу на экран три подцепочки на трех последовательных строках.

Остается еще установить немало деталей, касающихся представления кусков. Но вы же не ждете, что я за вас сразу и программу напишу?

Головоломка 27.

А эта программа простая. Вам нужно образовать выражение вида

a1◦a2◦a3◦…◦a_p,

где операция, обозначенная ◦, означает либо сложение, либо вычитание. Есть p − 1 знак, каждый из которых может принимать два значения. Это дает 2^p−1 возможных значений. Каким бы ни был способ, которым вы их перебираете, вам нужно перепробовать их все (по крайней мере в случае, когда число s таково, что решения нет).

Два знака «+» и «−», так что снова двоичная система. Вы можете воспользоваться этим замечанием при составлении программы. Меняем целое число от нуля до 2^p−1. Для каждого из значений рассматриваем его двоичное представление. Ставим в выражении «+» на тех местах, где стоят нули, и «−» на местах, где стоят единицы. Но в этом таится опасность побудить некоторых написать программу на языке ассемблера, что было бы ошибкой (по моему мнению. Вы тогда сплутовали бы. Есть хорошие алгоритмы на развитом языке. Не меняйте условий задачи, выписывая алгоритм, который оказался бы необъяснимым).

Вы можете также — и это, конечно, более эффективный способ — поставить знаки «+» в начале выражения и исчерпать все комбинации с тем, что осталось, затем заменить последний знак «+» на «−» и т. д, С четырьмя числами вы получите последовательно:

+++

++−

+−+

+−−

−++

−+−

−−+

−−−

Состояние знаков хранится в таблице или в цепочке.

Заметьте, что рассматриваемая задача имеет простое рекурсивное решение. Достаточно испробовать две комбинации:

a₁ + — любая комбинация, которая может быть составлена из p − 1 оставшихся шашек,

a₁ − — любая комбинация, которую можно составить из оставшихся шашек.

Должно получиться:

s = a₁ + — комбинация из n − 1 чисел или

s = a₁ − — комбинация из n − 1 чисел.