Описываю использованный алгоритм деления фигуры на N равных частей по клеточкам.
Назовем фигурами части, на которые делится исходная фигура. Исходную же фигуру назовем полем. Через Sz (size) обозначим размер одной части, а через N - число частей, на которые делится поле.
Сначала находим все движения, переводящие фигуру, содержащую первую клетку поля, в другую фигуру. Некоторые такие движения сразу забраковываем, если число клеток, являющихся образом или прообразом движения, меньше 2*Sz.
Например, при делении правильного шестиугольника 5x5 с треугольной клеткой на 5 частей получается 545 таких движений.
Далее перебираем все наборы из N-1 движений. Например, при делении на 5 частей будет 4 движения, они переводят фигуру, содержащую первую клетку поля в оставшиеся 4 фигуры. Эти движения перебираются послойно. При выборе K движений должно удовлетворяться условие: число клеток, являющихся образом или прообразом хотя бы одного из выбранных движений не должно быть менее (K+1)*Sz. В том числе, когда все движения выбраны, каждая клетка поля должна участвовать хоть в одном движении. На самом деле, критерий еще усиливается в существующем варианте и может быть еще усовершенствован, см. ниже.
После выбора всех движений распределяем клетки по фигурам следующим образом.
Делаем прямой логический вывод. Он заключается в том, что пока есть клетка которая может быть заполнена только одной фигурой, мы ее относим к ней и соответствующие при выбранных движениях клетки относим ко всем остальным фигурам. При этом другие возможности в клетках, соотнесенных фигурам, исключаем со всеми относящимися движениями. Если есть клетка, которая не участвует ни в каком движении, то противоречие, делаем возврат в переборе вариантов.
Когда больше вывести ничего нельзя, проверяем возможность связности первой фигуры. Проверку связности можно было бы усилить, например, учитывать оставшееся число невыбранных клеток первой фигуры и более сложные топологические соображения. Кроме того, можно было бы не только забраковывать вариант, но и выводить, какие клетки обязаны принадлежать или не принадлежать первой фигуре. Но в основных исследуемых случаях такие улучшения несущественны для быстродействия.
Если вариант не отбракован проверкой на связность, то выбираем клетку, которая может принадлежать наименьшему числу фигур и рассматриваем 2 варианта: когда она принадлежит или не принадлежит первой из этих фигур. В каждом из этих вариантов также делаем прямой вывод, проверку на связность и ветвление, пока не придем к противоречию или не разделим все клетки по фигурам.
Алгоритм не зависит от вида клеток и движений - хоть в 4-мерном пространстве или на поверхности сферы, когда клетки - грани многогранника, или если клетки нескольких видов.
Отдельно рассматривается случай деления на 2 части зеркально симметричной исходной фигуры на связные по стороне части. Здесь возможен только случай деления на части остью или в 3D плоскостью симметрии, что легко доказать.
К тонкостям также относится то, что из движения исключается перевод клетки саму в себя и перевод в первую клетку поля. И разные движения не могут переводить одну клетку в одну и ту же другую клетку.
Усовершенствование метода забраковки K отобранных движений заключается в следующем алгоритме. Определяем граф, вершины которого - клетки поля, а ребрами соединены клетки, которые одновременно не могут принадлежать первой фигуре. Это произойдет, если эти клетки переводятся какими-то двумя из выбранных движений в одну и ту же клетку. Вариант отбраковывается, если нельзя выбрать множество из Sz несвязанных ребрами вершин. Сначала отбираем все вершины, которые связаны с 0 или 1 оставшейся вершиной, это не ухудшит результат. Вершины, связанные с отобранными вершинами исключаем из рассматриваемого множества. Затем оставшиеся вершины сортируем по убыванию числа оставшихся в них ребер. Делаем оценку сверху числа несвязанных вершин в наилучшем подмножестве, для случая, если бы ребра при таких числах смежности были бы распределены наилучшим образом. Для этого каждый раз выбираем оставшуюся вершину с наибольшей смежностью и распределяем ее ребра по другим вершинам в порядке их наибольшей смежности. После этого подправляем сортировку оставшегося множества. Будем таким образом выбирать вершины и удалять ребра, пока не останется множество вершин, не связанных ребрами. Это и будет оценка сверху. Если она нарушает наше условие, то вариант забраковывается.
Заметим, что этот алгоритм может быть использован при поиске максимальной клики в любом графе. Я его придумал и применил в январе этого года при решении задачи 1 Заочного Чемпионата России по головоломкам. Не знаю, известен ли он.
Принцип анализа движений может быть использован в алгоритме деления произвольного многоугольника на части ломанными линиями - не обязательно по клеточкам.
