Усиленная программа 3

Программа 5: движения + инварианты + Exact Cover

Программа перебирает не раскраски клеток, а наборы движений между равными частями. Большинство наборов отбрасывается до рекурсии, а оставшаяся задача решается как точное покрытие.

Цепочка фильтров: движения → общая область возможной базовой части → симметрии → цветовые линейные инварианты → покрытие всех клеток пакетами → Algorithm X.
Рисование фигуры. ЛКМ или короткое касание рисует и стирает по клеткам. ПКМ выделяет прямоугольник от точки нажатия до точки отпускания. На сенсорном экране тот же режим включается долгим нажатием. Если начальная клетка пустая, прямоугольник заполняется; если закрашена — очищается.
Ограничения тестовой версии: разрезание на 2–6 частей; жёсткий максимум — 120 клеток. Рекомендуемые пределы: 120 клеток для 2–3 частей, 90 — для 4, 64 — для 5 и 48 — для 6. Превышение рекомендации разрешено после предупреждения. До 5 000 000 узлов перебора движений, до 3 000 000 узлов Exact Cover; первое решение или первые 100 решений — в зависимости от переключателя.
A B C D E F
Математические подробности

Фиксируется клетка базовой части. Каждое движение определяется одним из восьми положений и образом этой клетки. Для выбранных движений клетка x создаёт пакет {x,T₂(x),…,Tₖ(x)}.

Общая область. Если меньше n/k клеток имеют все необходимые различные образы внутри исходной фигуры, набор движений невозможен.

Цветовой фильтр. Используются периодические раскраски 2×2 и 3×3. Движения переставляют цвета. Для набора движений проверяется разрешимость необходимой линейной системы по модулям 2, 3 и 5.

Exact Cover. На каждом шаге выбирается ещё не покрытая клетка с наименьшим числом допустимых пакетов. Единственный пакет становится вынужденным. Безуспешные остаточные состояния запоминаются.

Симметрии. Наборы, переходящие друг в друга симметрией исходной фигуры, фиксирующей стартовую клетку, проверяются только один раз.