Пентамино в квадрате

Попробуйте выяснить, какие разноцветные элементы пентамино хорошо прикладываются друг к другу (чтобы длина их общей части была наибольшей). Важно — особенно на начальном этапе — наиболее плотно прикладывать элементы друг к другу, минимизируя незаполненное пространство между элементами, ведь в квадрате 12×12 должны остаться всего 24 незанятые клетки.

а) Существует много решений этой задачи. Одно из них приведено на рис. 2: несложно убедиться, что в квадрате 12×12 размещены два полных набора пентамино, причем одноцветные фигурки не касаются друг друга даже уголками.

Рис. 2.

б) В этом пункте мы ищем такую раскладку пентамино, в которой «расстояние» между наборами будет как можно меньше.

По условию мерой «расстояния» между наборами в раскладке служит сумма квадратов расстояний (измеренных по клеточкам) между одинаковыми фигурками. Обозначим эту сумму за \(r\). Также условимся обозначать через \(r(A)\) расстояние между фигурками одного и того же типа \(A\) из двух наборов (названия всех пентамино показаны на рис. 3, мы следуем схеме, предложенной Соломоном Голомбом). Например, для желтого и синего \(U\)-пентамино на рис. 2 имеем \(r(U)=5\).

Рис. 3.

В приведенной на рис. 4 расстановке половина одноименных элементов пентамино имеют общий отрезок, а значит, расстояние между ними равно 0. Для остальных пар одноименных пентамино расстояния таковы: \(r(U)=1\), \(r(Y)=2\), \(r(I)=r(V)= r(X)=3\). Самыми удаленными оказались желтое и синее \(Т\)-пентамино — расстояние между ними равно 6. Значит, в этом случае \(r=1^2+2^2+3\times3^2+6^2=68\). Для сравнения: в расстановке, приведенной на рис. 2, \(r=476\).

Рис. 4.

Интересно, получил ли кто-то из читателей результат меньше, чем 68? И, конечно, надо разобраться, какой вообще минимум возможен в этой задаче. Это непростой вопрос, который мы обсудим в послесловии.

Предыстория этой задачи такова. В виде головоломки она была представлена на чемпионате России по решению головоломок в 2020 году. Ее автор — Ольга Леонтьева, президент Клуба ценителей головоломок «Диоген» и организатор чемпионатов России. Частенько бывает так, что хорошая головоломка содержит в себе и математическую составляющую, поэтому с любезного разрешения автора, я использовал этот сюжет. В исходной головоломке требовалось сделать то же самое, что и в нашей задаче.

Оказалось, она имеет очень много решений (то есть расстановок двух наборов пентамино), поэтому и возникла необходимость ранжировать присланные участниками решения. Для этого удобно использовать тот самый параметр \(r\), который равен сумме квадратов расстояний между одинаковыми фигурами разных комплектов. Лучшим считалось решение с меньшим значением параметра \(r\). Идеальным вариантом было бы такое расположение, в котором каждая желтая фигура касалась бы такой же синей (тогда \(r\) равно нулю).

Решение этой трудной головоломки прислали 16 участников. По итогам чемпионата лучшим было признано решение Василия Илюхина, именно оно приведено в качестве решения пункта б) задачи (рис. 4). В поиске решения Василий руководствовался простым правилом: стараться расположить одинаковые элементы так, чтобы они имели хотя бы один общий отрезок. Как видно из рис. 4, для всех пар одинаковых фигурок ему этого добиться не удалось, но получить лучшее решение (среди присланных участниками чемпионата) он все же смог.

Победителю того чемпионата Константину Шамсутдинову эта задача не давала покоя. Несмотря на то, что итоги чемпионата были подведены, его не покидало желание найти расположение с как можно меньшим значением \(r\). Он решил воспользоваться помощью компьютера и придумал алгоритм, который оптимизировал поиск нужных решений. Благодаря этому Константину сначала удалось найти решение, в котором \(r=17\), а чуть позже было получено решение с \(r=4\)! Чтобы его найти, программа рассмотрела 393 млн позиций. Эта укладка показана на рис. 5 справа. Как видно, все пары одинаковых пентамино соприкасаются по отрезку, и только два L-пентамино не соседствуют друг с другом — они находятся друг от друга на расстоянии 2, поэтому \(r=4\).

Рис. 5.

Расстановки с \(r=17\) (слева) и \(r=4\)

Ниже — рассказ самого Константина Шамсутдинова:

Головоломка с двойным комплектом пентамино на мой взгляд очень красивая. Это был первый случай, когда я вернулся к задачам Чемпионата России уже после его окончания.

Разрабатывая компьютерную программу мне удалось:
1) усовершенствовать оценку степени свободы в случае, когда фигурки не касаются углом и часть фигурок уже поставлена на поле;
2) выработать оценочную функцию для позиции, когда часть фигурок из обоих комплектов уже поставлена на поле;
3) разработать методику перебора с приоритетом вариантов с лучшей оценочной функцией; при переборе с приоритетом приходится хранить полученные позиции.

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

Теперь о самом алгоритме. Пусть часть фигурок каждого цвета поставлена на поле. Рассмотрим фигурки какого-то из цветов. Для каждого из еще не поставленных пентамино этого цвета определим возможные положения (с учетом ограничения на сумму квадратов расстояний, так как фигурка противоположного цвета может уже стоять на поле), а для каждой клетки поля — возможные заполнения этими положениями. Если пентамино нельзя расположить, то позиция тупиковая, если клетку нельзя заполнить, то исключаем ее из рассмотрения для этого цвета. Далее считаем по этому цвету натуральное число \(S\) — степень свободы оставшихся фигурок. Если \(S<0\), то позиция тупиковая. Формула следующая (считаю, что это мое ноу-хау, существенно ускоряющее перебор, когда фигурки не касаются углом; я его раскрываю, чтобы описать алгоритм):

\[S=min(f_0-p_0,\ 4f_0+f_c-2f_i-f_d-s_p),\]

где \(f_0\) — количество свободных клеток поля, \(p_0\) — количество клеток свободных фигурок этого цвета, \(f_c\) — количество квадратов 2×2 из свободных клеток поля, \(f_i\) — количество касаний клеток поля, одно касание считается один раз, \(f_d\) — количество диагональных касаний клеток поля, когда в квадрате 2×2 одна пара противоположных клеток принадлежит свободной части поля, а другая — занятой, такое касание считается один раз.

Здесь ищется минимум двух функций степени свободы — простой и сложной.

\(s_p\) — величина сложной функции степени свободы для поля размером \(4f_0+f_c-2f_i-f_d\), подсчитанная для свободных фигурок этого цвета, то есть сумма по всем свободным фигуркам выражения \(4p_0+p_c-2p_i-p_d\), где \(p\) обозначает пентамино, \(f\) — поле.

Рис. 6.

Учет диагонального касания свободных клеток поля в этой формуле может быть только занижен, то есть истинное \(f_{d\text{и}}\le f_d\). В результате этого приближения может оказаться, что на следующем слое перебора \(S\) немного возросло, но это происходит редко. На мой взгляд, значение \(S\) может возрасти не более, чем на 1.

Чтобы ускорить поиск, ввел ограничения для коэффициента, положив \(r\le8\). Перебор вариантов решил начинать с установленной на игровое поле пары фигур U-пентамино, примыкающих друг к другу в углу квадрата 12×12 (рис. 6).

Безусловно, возникает вопрос: существует ли решение, в котором \(r=0\)? Затратив около недели процессорного времени, Константин так и не нашел такого решения. Может быть, кому-то из читателей это удастся?

В связи с нашей задачей естественно возникает еще один вопрос: как расположить двойной комплект пентамино с максимальным значением параметра \(r\)? Этот вопрос был сформулирован на командном матче по решению головоломок между командами России и Украины в 2020 году. Такие матчи ежегодно проводятся с 1995 года:

Расположите в квадрате 12×12 два комплекта пентамино, чтобы одинаковые элементы одного комплекта не касались даже углом. Элементы могут быть повернуты и перевернуты. При этом сумма квадратов расстояний между одинаковыми элементами разного цвета должна быть как можно больше. Расстояние между элементами — это минимальное число пустых клеток, по которым надо пройти, чтобы перейти с клетки одного элемента на клетку другого.

Команда России в зачете по этой задаче одержала победу благодаря программе Константина Шамсутдинова — она нашла расстановку с \(r=1254\) (рис. 7). Ее поиск решения оказался вычислительно не таким сложным, как в задаче на минимальную расстановку, потому что в этом случае лучшие результаты достигаются в симметричной конфигурации. В приведенной на рис. 7 расстановке все пары одинаковых элементов пентамино расположены центрально симметрично относительно центра квадрата 12×12. На этом же рисунке справа приведена таблица, в которой подсчитано значение \(r\).

Рис. 7.

Несмотря на подробный анализ при помощи компьютера, здесь есть немало открытых вопросов. Например:
    1) Сколько различных решений имеет задача?
    2) Возможно ли найти решение, в котором одинаковые пентамино разных комплектов имеют одинаковую ориентацию?
    3) Как найти решение с самой большой свободной областью внутри квадрата 12×12?