Интерактивная глава · пять алгоритмов

Как компьютер разрезает клетчатые фигуры на равные части

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

Эволюция алгоритмов

Одна задача — пять разных объектов для перебора

Раскраски

Выбираем, какой части принадлежит каждая клетка.

Связные формы

Выращиваем только кандидатов, которые уже могут быть частью.

Движения

Ищем преобразования, переводящие одну копию части в другие.

Разрез

Перебираем линию или полную границу между частями.

Ограничения

Фильтруем движения инвариантами и решаем Exact Cover.

Сначала — не программирование

Что делает человек, когда видит задачу на разрезание?

Обычно мы не перебираем все варианты. Мы замечаем выступы, узкие перемычки, углы и повторяющиеся фрагменты. Затем пытаемся мысленно выделить одну часть и представить, куда поместится её копия после подходящего движения плоскости.

Такое решение похоже не на последовательное выполнение строгой инструкции, а на сочетание наблюдений, догадок и быстрых проверок. Компьютеру же сначала проще дать гораздо более примитивный, но исчерпывающий план.

Проверить площадь

Если клеток нечётное число, разрезать фигуру на две клетчатые части равной площади невозможно.

Представить половину

Каждая часть должна содержать ровно половину клеток исходной фигуры.

Искать соответствия

Одна часть должна совместиться с другой после допустимого движения: переноса, поворота и, если разрешено, отражения.

Программа 1

Переберём все двухцветные раскраски нужного размера

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

Первую клетку всегда сделаем красной. Иначе каждое разбиение встретится дважды: с переставленными названиями цветов.

Выберем ещё нужное число красных клеток. Все остальные клетки автоматически станут зелёными.

Проверим обе части. По умолчанию они должны быть связными и равными. В тренажёре это условие можно отключить.

Что означает «одинаковые»?

≈ после подходящего движения плоскости ≈

Для сравнения программа переводит клетки в координаты, рассматривает восемь стандартных положений второй части и после каждого преобразования сдвигает фигуру к началу координат. Если отсортированные списки координат совпали, части равны.

Как устроен перебор

Нумеруем клетки и раскрашиваем их по порядку

Фигура из 10 клеток

Эту фигуру можно разрезать на две равные части по 5 клеток.

Порядок нумерации

12 3456 78910

Идём по строкам: слева направо, затем сверху вниз. Пустые клетки не нумеруются.

Почему клетка 1 всегда красная?

Если не зафиксировать первый цвет, каждое разбиение встретится дважды: один раз красная часть будет названа первой, а второй раз — зелёная. Фиксация первой клетки убирает это повторение.

Начало

Клетка 1 заранее отнесена к красной части.

Один из вариантов перебора

Получилось по 5 клеток каждого цвета.

Проверка

Обе части связны и совмещаются движением плоскости: разрез найден.

Проверка равенства

Восемь положений одной и той же фигуры

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

1Исходное положение

2Поворот на 90°

3Поворот на 180°

4Поворот на 270°

5Отражение

6Отражение + поворот на 90°

7Отражение + поворот на 180°

8Отражение + поворот на 270°

Неочевидная часть

Как программа «видит» и сравнивает фигуры

Открыть подробное объяснение

1. У каждой клетки есть адрес

Программа не видит рисунок так, как его видим мы. Поле для неё — таблица. Строки нумеруются сверху вниз, а столбцы — слева направо. Удобно начинать нумерацию с нуля: тогда адрес клетки записывается парой (строка, столбец).

столбец 0

столбец 1

столбец 2

столбец 3

строка 0

(0,0)

(0,1)

(0,2)

(0,3)

строка 1

(1,0)

(1,1)

(1,2)

(1,3)

строка 2

(2,0)

(2,1)

(2,2)

(2,3)

Например, левая верхняя клетка имеет адрес (0,0). Клетка справа от неё — (0,1), а клетка под ней — (1,0). Соседние по стороне клетки отличаются ровно на единицу в одной координате.

2. Фигура превращается в список адресов

(0,0) (1,0) (2,0)(2,1)

[(0,0), (1,0), (2,0), (2,1)]

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

3. Одинаковые фигуры могут иметь разные координаты

Если ту же фигуру перенести в другое место поля, её форма не изменится, но все адреса станут другими:

[(3,5), (4,5), (5,5), (5,6)] и [(0,0), (1,0), (2,0), (2,1)]

Поэтому сравнивать исходные списки напрямую нельзя.

4. Нормализация: сдвигаем фигуру к левому верхнему углу

Программа находит наименьший номер строки и наименьший номер столбца. Затем вычитает эти два числа из координат каждой клетки:

[(3,5), (4,5), (5,5), (5,6)] → вычитаем (3,5) → [(0,0), (1,0), (2,0), (2,1)]

После такого сдвига у фигуры обязательно появляется клетка в строке 0 и клетка в столбце 0. Место фигуры на большом поле больше не влияет на её запись.

5. Координаты сортируются

Один и тот же набор клеток можно перечислить в разном порядке. Чтобы порядок тоже не мешал сравнению, координаты сортируют: сначала по номеру строки, а при равных строках — по номеру столбца.

[(2,1), (0,0), (2,0), (1,0)] → [(0,0), (1,0), (2,0), (2,1)]

6. Повторяем это для восьми положений

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

Попробуйте сами

Нарисуйте фигуру и найдите разрез

Проводите мышью или пальцем по клеткам. Для первой версии разумно начинать с 6–18 клеток: число вариантов быстро растёт.

исходная фигура часть A часть B

Какие ограничения есть у этой версии?

Это учебный полный перебор. Он специально прост и прозрачен, но плохо масштабируется. По умолчанию программа ищет только связные части; переключатель позволяет искать и равные несвязные наборы клеток. Поиск ограничен 26 клетками и максимумом в 200 найденных разбиений. Поиск можно поставить на паузу и затем продолжить с того же варианта. Следующая программа будет строить одну часть как связную фигуру и отсекать заведомо невозможные продолжения значительно раньше.

А если частей больше двух?

Разрезание на 3, 4 и вообще на k равных частей

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

Но число раскрасок растёт значительно быстрее, чем в случае двух частей.

Сколько вариантов нужно проверить?

Пусть в фигуре n клеток, а разрезать её нужно на k частей. Тогда каждая часть должна содержать

\[m=\frac{n}{k}\]

клеток. Если цвета частей пока считаются различимыми, число раскрасок с одинаковым количеством клеток каждого цвета равно мультиномиальному коэффициенту:

\[\frac{n!}{(m!)^k}\]

Но перестановка названий цветов не меняет самого разреза. Поэтому для неразличимых частей естественная оценка числа разбиений:

\[\frac{n!}{(m!)^k\,k!}\]

Клеток	Частей	По клеток в части	Неупорядоченных раскрасок
12	2	6	462
12	3	4	5 775
12	4	3	15 400
18	2	9	24 310
18	3	6	2 858 856
20	4	5	488 864 376
24	3	8	1 577 585 295

Почему способ всё же полезен?

Для маленьких фигур полный перебор остаётся прекрасной учебной моделью: он прост, надёжен и гарантированно найдёт решение, если перебрать всё.

Почему он быстро перестаёт годиться?

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

Как выглядит прямой перебор для трёх частей

Проверить делимость площади на 3. Если число клеток не делится на 3, разрез невозможен.

Первую клетку отнести к части A. Это частично убирает повторения.

Выбрать остальные клетки части A. Затем из оставшихся выбрать клетки части B; остальные образуют часть C.

Проверить связность всех трёх частей.

Сравнить части. Каждая из частей B и C должна быть равна части A.

Главный вывод

Раскрашивание всех клеток — хороший первый алгоритм и хороший способ объяснить задачу. Но для серьёзного поиска по трём и более частям нужен другой принцип: строить одну связную часть постепенно, сразу примерять её копии и как можно раньше отбрасывать невозможные продолжения.

Тренажёр для нескольких частей

Разрезание на 3 или 4 равные части

Нарисуйте фигуру, выберите число частей и запустите полный перебор. Ограничения здесь строже, потому что число раскрасок растёт очень быстро.

Ограничения: для 3 частей — не более 18 клеток и 4 000 000 раскрасок; для 4 частей — не более 16 клеток и 2 000 000 раскрасок. Найденные разрезы ограничены первыми 100 вариантами.

A B C D

Программа 2

Что значит «наращивать часть по границе»?

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

1. Начальная клетка

Берём одну клетку будущей части.

2. Клетки границы

Кандидаты на следующий шаг соприкасаются с частью по стороне.

3. Добавляем одну клетку

Полученная часть автоматически остаётся связной.

4. Доращиваем до нужной площади

После этого пытаемся разместить равные копии части в остатке.

Что даёт такой порядок?

Мы вообще не создаём несвязных кандидатов. Для задачи на цельные куски это резко сокращает число рассматриваемых частей.

Когда он неполон?

Если разрешить части, состоящие из нескольких раздельных компонентов, такой алгоритм их не найдёт: он по построению создаёт только связные фигуры.

Нужно ли, чтобы остаток был связным?

Не обязательно. Когда мы проверяем, можно ли разместить в остатке ещё одну копию уже построенной части, остаток вполне может состоять из нескольких областей. Важно только, чтобы нужное число непересекающихся копий целиком помещалось в оставшихся клетках.

Однако связность остатка иногда даёт полезные ранние проверки. Например, если каждая будущая часть должна быть связной и некоторая компонента остатка содержит меньше клеток, чем одна часть, эти клетки уже невозможно использовать. Аналогично, размеры компонент должны допускать разбиение на целые части или их допустимые комбинации. Это не основа метода, а дополнительное отсечение.

Кандидат-часть

→ ищем все положения →

Остаток фигуры

Точная формулировка второго алгоритма

Мы перебираем связные фигуры нужной площади, содержащие фиксированную стартовую клетку. Для каждой такой фигуры строим все её положения и решаем задачу упаковки: можно ли выбрать ещё \(k-1\) непересекающихся копий, которые вместе с первой покрывают исходную фигуру?

Тренажёр программы 2

Строим одну часть и укладываем её копии

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

Разумные ограничения учебной версии: не более 40 клеток; размер одной части — не более 20 клеток; не более 60 000 связных кандидатов и 800 000 узлов поиска покрытия. Программа показывает первые 50 различных разрезов.

A B C D E F

Программа 3 · перебираем движения

Вместо частей ищем, как одна часть переходит в остальные

Зафиксируем одну клетку базовой части. Движение её копии определяется одним из восьми положений и клеткой, в которую переходит выбранная клетка. Поэтому имеется не более 8n кандидатов на одно движение.

Для k частей выбираются k−1 движений, а затем вся фигура покрывается пакетами соответствующих клеток {x,T₂(x),…,Tₖ(x)}.

Фиксируем стартовую клетку. Она считается клеткой первой части.

Выбираем движения. Остальные части — образы первой.

Строим пакеты. В каждом пакете по одной соответствующей клетке каждой части.

Ищем покрытие. Пакеты не должны пересекаться и обязаны покрыть всю фигуру.

Математические подробности программы 3

Грубая оценка числа неупорядоченных наборов движений: C(8n,k−1). Для фиксированного малого k это полиномиальный по n перебор.

Для фиксированного набора движений остаётся задача точного покрытия. Прототип использует рекурсивный поиск пакетов.

Слабое место проявляется при 5–6 частях: степень полинома растёт вместе с числом частей.

Программа 4 · думаем о самом разрезе

Ищем границу, а не клетки частей

Вариант А

Перебирается одна простая линия по рёбрам сетки от внешней границы до внешней границы. Это очень наглядно, но не охватывает циклические и многокомпонентные границы.

Вариант Б

Ищется вся общая граница двух связных половин. Она может быть замкнутой или состоять из нескольких компонент, но перебор существенно тяжелее.

Почему два варианта действительно различаются?

Граница двух частей не обязана быть одним простым путём. Она может образовывать цикл, иметь несколько компонент или проходить через вершину сетки четырьмя рёбрами.

Поэтому вариант А — быстрый поиск разрезов специального вида, а вариант Б — полный поиск разбиений на две связные равные части в пределах вычислительного лимита.

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

Сохраняем идею 3, но отбрасываем невозможные наборы намного раньше

движения→общая область→симметрии→цветовые инварианты→Exact Cover

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

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

Что именно ускоряет программу 5?

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

Сравнение

Что именно перебирает каждая программа?

Программа	Объект поиска	Сильная сторона	Главное ограничение
1	Раскраски клеток	Простота и очевидная полнота	Экспоненциальный рост
2	Связная форма одной части	Не строит заведомо несвязные части	Форм всё ещё очень много
3	Движения между копиями	Очень мало кандидатов при малом k	Тяжелее при 5–6 частях
4	Линия или граница разреза	Геометрическая наглядность	Число границ может быть огромным
5	Движения после системы фильтров	Лучший практический гибрид	Имеет вычислительные лимиты

Проект продолжается

Какая математика может появиться дальше?

SAT

Описать всю задачу системой логических ограничений и использовать обучение на конфликтах.

Для узких фигур проводить сканирующую линию и хранить только состояние на текущей границе.

MITM

Для 5–6 частей разделять движения на две группы и склеивать совместимые отпечатки.

Почему на программе 5 история не заканчивается?

Универсальная задача содержит трудные задачи точного покрытия, поэтому одного алгоритма, одинаково лучшего для всех фигур, ожидать не стоит. Разные геометрические классы могут требовать разных методов.

Эта страница задумана как развивающаяся интерактивная глава: новые программы можно добавлять отдельными файлами, не переписывая Tilda-страницу.