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

x . .  x . .  x . .  x . .  ж . .

Заменим ж на к или к и получим тот же результат. Покажите самостоятельно, что в конце концов получаются следующие схемы

x x .  x x .  x x .  x x .  x x .

x ж .  x ж .  x ж .  x ж .  x x .

x к .  x к .  x к .  x к .  x . .

x н .  x н .  x н .  x н .  x . .

x . .  x . .  x . .  x . .  ж к н

Вам остается расставить сначала а, б, в, г, д, е вместо букв x, не возобновляя уже использованных пар, а затем расставить буквы з, и, л, м, о, п вместо точек, соблюдая то же правило. На моем компьютере это отнимает не более 3 минут.

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

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

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

Вы можете действовать двумя способами: — рассматриваете первое свободное поле и ищете кусок, который можно туда поместить;

— берете первый, еще не использованный кусок и пытаетесь поместить его на игровое поле.

Кусок может быть по-разному ориентирован. Если «I» (прямой брус) может быть размещен в прямоугольнике 3 × 20 только одним способом (параллельно большей стороне), то «F» (вроде правой нижней фигуры на рис. 31) может быть ориентирован восемью способами. Это зависит в первую очередь от симметрии кусков.

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

Вы можете составить программу без каких-либо хитростей. Кажется, что более эффективно брать первое пустое поле и пытаться поместить туда какой-либо кусок. Вы ищете первое свободное поле. Вы рассматриваете первый еще не использованный кусок. Вы исследуете в некотором порядке все его ориентации, чтобы выяснить, приемлема яя какая-нибудь из них — покрывает ли она только свободные поля. Если игра блокирована (никакой кусок поместить нельзя), то вы удаляете последний размещенный кусок и продолжаете поиск, начиная со следующей ориентации того же куска. Я пробовал сделать так, и это слишком долго…

Тогда я стал пытаться избежать большого числа испытания, исходя аз замечания, сделанного при постановке задачи: кусок не должен определять в игре «островок» с площадью, не кратной пяти. Но определение островков нетривиально…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a1◦a2◦a3◦…◦ap,

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

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

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

+++

++−

+−+

+−−

−++

−+−

−−+

−−−

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

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

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

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

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

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