Программирование игр и головоломок - [56]

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

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

Рассмотрим сначала случай 9 девушек. Обозначим их

а, б, в, г, д, е, ж, з, и.

Первая прогулка может быть выбрана произвольно. Возьмем:

а б в
г д е
ж з и

Беря в качестве строк столбцы этой таблицы первой прогулки, получаем вторую прогулку:

а г ж
б д з
в е и

Диагонали приводят к двум оставшимся прогулкам:

а д и   а е з
в г з   б г и
б е ж   в д ж

Все благополучно, Попробуем теперь 15.

Первая прогулка

а б в г д е ж з и к л м н о п

Если вы возьмете в качестве трех первых строк второй прогулки начала столбцов первой прогулки:

а г ж
б д з
в е и

вы не сможете далее организовать 6 оставшихся букв в двух строчках, не повторяя пар. Но вы можете сохранить первые пары в этих трех строках и взять в качестве последних элементов соответственно ж, к, н. Посредством этого приема получаются в двух столбцах по три неиспользованных элемента, которые и можно взять в качестве новых строк. Получается вторая прогулка:

а г ж
б д к
в е н
з л о
и м п

Сейчас мы докажем некоторые свойства искомых прогулок. Но здесь я делаю вам подарок. Мне потребовалось несколько дней, чтобы сообразить все то, что следует ниже. Почему бы вам не предоставить себе несколько дней на размышление? Тогда закройте книгу на этом месте…

Рассмотрим подмножество из семи букв а, б, в, г, д, е, ж. Исходя из этих элементов, можно образовать 7 * 6/2 = 21 пару. В первой прогулке участвует 6 из этих пар:

а — б а — в б — в з — д г — е д — в

Во второй прогулке их пять:

а — г а — ж г — ж б — д в — е

что составляет всего 11 пар. Таким образом, на оставшиеся 5 прогулок остается распределить 10 пар. Но поскольку есть 7 элементов и только 5 строк, то в каждой прогулке будет встречаться не менее двух таких нар. Следовательно, в каждой из оставшихся прогулок встретятся в точности две таких пары. Обозначим через x любую из выделенных букв, а остальные буквы будем обозначать точками. Оставшиеся 5 прогулок имеют вид

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

Но можно еще кое-что уточнить. Рассмотрим только первые 6 букв а, б, в, г, д, е. Они дают 15 пар, из которых 9 реализуются в двух первых прогулках. Таким образом, среди 5 оставшихся прогулок надлежит распределить 6 из них, что означает по одной паре в четырех из них и две в последней. Поэтому получаем:

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 .
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) может быть ориентирован восемью способами. Это зависит в первую очередь от симметрии кусков.

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

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