Программирование игр и головоломок - Жак Арсак
Шрифт:
Интервал:
Закладка:
Я не знаю простого решения для симметрии относительно диагонали. Если вы найдете такое решение, напишите мне…
Головоломка 21.
Я не вижу способа взяться за эту задачу, существенно отличного от предыдущего. Нужно найти нижнюю границу для числа ферзей. На пустой шахматной доске ферзь может блокировать 28 полей. Следовательно, нужно по крайней мере 3 ферзя, чтобы блокировать доску. Их нужно не больше 7: если вы уже пытались вручную поставить 8 ферзей, то вы должны были убедиться, что шахматная доска часто блокируется до того, как мы смогли поставить восьмого ферзя. Точно так же вероятно, что 6 ферзей должно хватить. Поэтому нужно исследовать отрезок от 3 до 6 ферзей.
Нет никакой уверенности в том, что эти ферзи не должны бить друг друга. Конечно, на шахматной доске есть поля, которые бьются по крайней мере двумя ферзями. Но нужно иметь возможность ограничить поиск решениями, для которых никакие два ферзя не бьют друг друга, или, может быть, немного проще — решениями, для которых никакие два ферзя не стоят на одной строке.
Вы размещаете k ферзей. Вы пробегаете шахматную доску в поисках свободного поля. Если его нет, то у вас есть решение. Если свободное поле есть, то вы ставите туда ферзя и начинаете поиск сначала. Бесполезно пробегать строки, на которых ферзь уже есть, Это соображение ускоряет проверку.
Головоломка 22.
Ничего трудного. Нужно перепробовать все комбинации, Берем какую-нибудь шашку домино в качестве начальной шашки цепочки и пробуем шашки одну за другой. Они вынимаются из хранилища, а затем отыскивается первая шашка, которую можно связать с данной, тем же способом, которым отыскивалось первое свободное поле на следующей строке.
Тщательно выберите ваше представление шашек домино.
Головоломка 23.
И на этот раз программирование достаточно просто. Вы задаете крайние члены последовательности:
a1 = 0, an = k.
С помощью уже проведенного рассуждения вы можете зафиксировать
a2 = 1, an−1 = k − 2.
Затем вы размещаете следующие члены в интервале (2, k − 3), например, уплотняя их к началу:
a3 = 2, a4 = 3, a5 = 4…
Вы образуете разности и, если они дают слишком много повторений (вы можете узнать его, не вычисляя всех разностей, что ускоряет тест), вы увеличиваете последний подвижный член an−2 и, когда добираетесь до конца, увеличиваете предпоследний подвижный член, затем берете an−2 = an−3 + 1 и продолжаете дальше.
Для последовательности с 5 членами есть только один подлежащий размещению член, и все идет очень быстро. Но сложность растет с ростом n очень круто. Если при 5 членах есть только один подлежащий размещению член, то с n = 6 их уже два и задача квадратична. Для произвольного n число подлежащих испытанию случаев имеет порядок nn−4.
Можно, наверное, и еще ускорить. Если даны пак (значение последнего члена), то известно максимальное число возможных повторений, и можно выбрать наилучшие исходные значения. Если есть право на r повторений, то можно брать не более r − 1 последовательных членов, начиная с a2, и, если они взяты как исходные значения, то права на повторение больше нет. Тем не менее эта задача расходует огромное количество машинного времени…
Головоломка 24.
В этой задаче я вас полностью предоставляю себе. Принцип все тот же. Но нужно как следует все организовать. Желаю успеха.
Головоломка 25.
Здесь, наоборот, помощь может оказаться далеко не лишней. Эта программа потребовала от меня массу времени. Кроме того, это поучительный случай, который я сохраняю в своих архивах как типичный пример для целого класса задач.
Среди информатиков есть два принципиально разных взгляда на программирование. Есть школа, приверженцы которой сначала проделывают всю математическую работу; они считают, что для того, чтобы написать хорошую программу, нужно сначала доказать некоторое свойство данных, а затем использовать его для получения результата. Сначала сделайте математику, а информатика придет позже. Таким образом, это способствует рассмотрению информатики как ветви математики.
Но есть и другой подход. Напишите сначала программу, пусть даже неэффективную. Затем понаблюдайте за ее поведением или постарайтесь прояснить ее действие. С помощью подходящих преобразований сделайте ее более результативной. Довольно часто я получаю таким образом весьма эффективные результаты, и я убежден, что в этом состоит новый метод создания алгоритмов. Но бывают упорно сопротивляющиеся случаи. Эта головоломка — один из них.
Начну со следующего замечания: речь идет о том, чтобы образовать все возможные перестановки и выбросить все те, которые не удовлетворяют условиям задачи.
Рассмотрим сначала случай 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 . . ж . .
Заменим ж на к или к и получим тот же результат. Покажите самостоятельно, что в конце концов получаются следующие схемы
