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

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 . .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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