---

Даны Тетриминки - фигурки тетриса, состоящие из четырех блоков 1ドル \times 1$. Другими словами, более формально, каждый блок Тетримино должен касаться хотя бы одного другого блока с любой из его четырех сторон (сзади, снизу, слева или справа).

Цель - разместить заданный набор тетриминок в квадратной области наименьшей площади так, чтобы тетриминки не пересекались друг с другом (незаполненные «дырки» в области допускаются).

---

Задача проекта является частным случаем Задачи о покрытии множества.

В нашем случае Задачу о покрытии множества можно переформулировать следующим образом:

• Есть множество $S$ (искомое квадратное поле (возможно, с дырками, т.е. пустыми квадратиками))
• Есть набор подмножеств $Y$ множества $S$ (всевозможные разрезания $S$, включая отдельные квадратики 1x1, невалидные и валидные тетриминки,а также кусочки, содержащие иное (не четыре) число квадратиков)
• Задача состоит в том, чтобы выбрать из $Y$ такие элементы $Y'$ (тетриминки из заданного набора), что каждый элемент из $S$ (непустой квадратик) содержится только в одном из множеств, входящих в $Y'$
• То есть объединение всех множеств в $Y'$ (тетриминки из заданного набора) составляет (покрывает) множество $S$, и при этом в $Y'$ нет попарно пересекающихся множеств

В качестве алгоритма использовалась интерпретация Алгоритма Х Д.Кнута с использованием техники "танцующих ссылок".

1. Вначале нам нужно определить минимальный размер $k$ стороны квадрата поля $S$, в который алгоритм будет пытаться разместить заданные фигуры.
   Размер стороны $k$ будет равен либо максимальной длине тетриминки по высоте или ширине, либо квадратному корню из * n,ドル где $n$ - число тетриминок, поданных на вход.
   При этом значение квадратного корня берется с округлением в бОльшую сторону. Например, если на вход подается две тетраминки \times 4$ и \times 2,ドル то у поля будет размер \times 4$ (его определяет максимальная длина первой тетриминки), а если на вход поданы две тетриминки размером \times 2,ドル то первоначальный размер поля, куда алгоритм будет пытаться уместить тетриминки (увы, безуспешно), будет равен \times 3,ドル т.е. $\sqrt{4*2} = 3$, с округлением в бОльшую сторону).
2. Затем алгоритм рекурсивно, в соответствии с требованиями задания (тетриминки должны располагаться в приоритетном порядке номера в исходном файле относительно левого верхнего угла поля $S$), производит попытку замостить квадратное поле тетриминками.
3. В случае неудачи размер $k$ каждой стороны поля $S$ увеличивается на единицу и процесс рекурсивного подбора покрытия квадрата $S$ тетриминками повторяется.

---

Ниже представлены примеры входных файлов с различными наборами тетриминок и результаты работы программы fillit:

1. Восемь одинаковых вертикальных тетриминок размером 4ドル \times 1$

image

2. Четыре одинаковых "квадратных" тетриминки, размером 2ドル \times 2$

image

3. Четыре тетриминки различной конфигурации

image

4. Еще один пример из четырех тетриминок различной конфигурации

image

---

1. Dancing Links Donald E. Knuth, Stanford University
2. Stanford Lecture: Don Knuth—"Dancing Links" (2018)