Календарь-головоломка

green_fr — 01.02.2022 На новый год дедушка Мороз подарил мне календарь-головоломку. Нужно уложить вот эти 8 деталей вот в эту форму, чтобы в оставшихся клеточках была видна текущая дата. Справа — решение для сегодняшней даты.



Какое-то время я пытался решить для 1 января — нужно же всё делать по порядку! Потом для текущей даты — нужно же сделать хотя бы что-то! Затем просто складывал детали в надежде, что когда-нибудь они улягутся, и записывал получавшиеся даты впрок. Ну а потом вспомнил про MatLab.

1. Первая версия, тупой брутфорс
Написал класс Piece с матрицей, описывающей каждую деталь. Пара пространственных методов — flip и rotate, преобразующих матрицу. Служебный класс-структура Placement с номером детали, координатами на поле и информацией о том, как именно повёрнута деталь. Класс Plateau с матрицей игрового поля. Метод поиска всех возможных положений детали на поле (Placement). Методы put и remove, которые отражают на матрице поля тот факт, что мы положили или убрали деталь.

И рекурсивный метод решения задачи:
* Метод принимает список деталей, которые нужно уложить
* Если список пустой — значит мы уже уложили всё необходимое => сохраняем в файле найденное решение
* Иначе берём первую деталь из списка и ищем все возможные положения её на поле
* Пробегаем по полученному списку положений
** Кладём деталь на поле
** Вызываем этот же метод со списком без первой детали — её мы только что уложили
** (мы вернёмся сюда, когда обработаем все возможные последствия уложенной детали) Убираем деталь с поля
** Переходим к следующему возможному положению

Отличная программа. Гарантированно решает всё. Запустил, проверил первое найденное решение, проверил второе найденное решение. Поставил считать. Прикинул, сколько времени понадобится для полного прохода — порядка 10 лет. Надо что-то делать.

2. Косметические улучшения
Прекращаю вызывать flip и remove в этих бесконечных циклах. Для каждой детали можно с самого начала просчитать все её возможные положения. Более того, не у всех деталей все 8 положений отличаются друг от друга — есть и симметричные детали. Сразу же выкидываю повторяющиеся картинки. На глазок прикидываю ускорение — задача должна решиться примерно за пол года.

Одновременно написал скрипт, который пробегает по уже найденным решениям и идентифицирует их. Скрипт смотрит, какие именно клеточки остались свободными, и если они складываются в дату — помечает эту дату как «решённую».

3. Нужно решать чётко поставленную задачу

Только что написанный скрипт чётко показывает, что не все найденные варианты меня интересуют. Некоторые не соответствуют никакой дате (например, остались видимыми клеточки 1, 8 и 19). А некоторые дают альтернативное решение для уже найденной даты. Это наводит меня на мысль: а чем, собственно, я тут занимаюсь? Я решаю задачу «найти все возможные варианты укладки 8 деталей в указанный шаблон». А какая задача передо мной стояла? Совсем другая — «для каждой даты найти хотя бы одну укладку». Это же существенно более простая задача!

Пишу цикл по всем дням года (для простоты полагаю, что у нас во всех месяцах есть 31 день). Сразу помечаю эти клеточки как занятые — количество доступных положений резко падает!

4. Прозрачные матрицы

Одновременно в голову приходит идея для упрощения поиска всех доступных положений детали на поле. Моё первое «интуитивное» решение — перебирать все варианты для верхней левой точки каждой детали (точнее, верхней левой точки описывающей её матрицы), накладывать матрицу поля на матрицу детали и смотреть, есть ли пересечения — стандартная операция «и». Если есть — деталь положить нельзя. Если нет — запомнили, переходим к следующий координатам / варианту поворота детали. Долго, нудно, качественно.

Но есть вариант и без перебора, который сразу даёт все возможные положения. Представим для начала, что у нас есть некоторое положение деталей на поле. Сделаем «прозрачку» — на прозрачной плёнке нарисуем поле и эти детали. Оставшиеся прозрачными клеточки показывают нам, куда можно положить деталь 1×1. Пока что ничего сверхъестественного.



Возьмём теперь две одинаковые прозрачки (на картинке я их сделал разыми цветами). Наложим их друг на друга со сдвигом на 1 клеточку по горизонтали. Что теперь символизируют оставшиеся прозрачными клеточки? Те места, куда можно положить деталь, состоящую из двух расположенных горизонтально клеточек!



На всякий случай ещё одна картинка для детали из 3 клеточек «уголком». Легко проверить, что на изначальном поле этот уголок можно уложить именно указанными 16 способами.



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

Всё, с этим улучшением задача поиска укладки для одного дня решается за ~1 минуту. Наверняка можно и ещё улучшить — а можно запустить на ночь, и утром у меня будут все решения :-)

---

Сделал и завис. Сказать Анюте, что вместо того, чтобы получать тактильное удовольствие (деревянный пазл, детали из бамбука!) каждый день — я взял всё удовольствие за один раз, но в виртуальном мире? Это может оказаться обидным. Ещё пару дней отсылал ей решения (на самом деле, она подсмотрела идею подарка на работе, и у них там образовался чатик, где все хвастались, кто решил сегодняшнюю задачу), а потом она мне возмущённо говорит: представляешь? Jean-Hervé вместо того, чтобы самому решать — написал какую-то приблуду на Excel! — Ты не поверишь, говорю...

Вчера Жан-Эрве приходил в гости, сравнивали наши методы. Ну, помимо того, что не надо на Excel ничего серьёзного считать, у меня метод, наверное, эффективнее. Но и у него интересно. Он сделал сначала для каждой детали список всех возможных положений на доске. Потом скрестил их: проверил, какие положения первой детали совместимы (не пересекаются) с какими положениями второй детали — и так далее, для всех возможных пар. Потом сделал виртуальную деталь «1+2» — у её положения определяются совместимыми положениями из предыдущего этапа. А следующий этап — построение детали «1+2+3» — существенно проще. Потому что совместимость определённого положения «1+2» с положением «3» определяется через совместимость «1» и «3» умноженную на совместимость «2» и «3». То есть всё делается практически без кода, одними формулами Excel. Даже поворот на 90° он делал через комплексные числа, умножением на мнимую единицу. Проблема лишь в объёме данных — он вынужден хранить всё, и в какой-то момент файл вырастал до 2GB и падал. Ну и во времени расчётов — по его прикидкам машина сама решает одну задачу примерно за один день. Поэтому он работал в режиме «киборга», проверяя какие-то варианты ручками.

Оставить комментарий

Популярные посты:

• Ранее
• Архив