🔷 Разрезание клетчатых фигур на равные части
Часть 1: Делим фигуру на две одинаковые половинки
💭 Как мы думаем, когда решаем такие задачи?
Представьте: перед вами фигурка из клеточек — похожа на тетрис или пазл.
Задание простое на вид: разрежьте её на две равные части.
Но что значит «равные»? И с чего вообще начать?
Опытный решатель действует как детектив:
- Шаг 1: Считает общее количество клеток. Если их нечётное число — задача не имеет решения. Делить нечестно!
- Шаг 2: Представляет, какой формы может быть половина. Если всего 10 клеток, то каждая часть должна содержать ровно 5.
- Шаг 3: Ищет «неудобные» места — выступы, уголки, которые явно должны попасть в одну из частей. Иногда сразу видно: «Ага, этот отросток никуда не денешь!»
- Шаг 4: Пробует мысленно «прикладывать» одну часть к другой — как пазл. Если после поворота или отражения фигуры совпадают — bingo!
Но что делать, если фигура сложная, а вариантов — сотни? Здесь на сцену выходит компьютер.
🌳 Дерево перебора: на конкретном примере
Давайте разберём всё на конкретной фигуре из 8 клеток:
Наша фигура (8 клеток)
Нужно: 2 части по 4 клетки
Как нумеруются клетки
Клетка 1 — всегда в части A
Остальные перебираются
📋 Как программа выбирает клетки?
Порядок фиксирован: программа идёт слева направо, сверху вниз.
Первую клетку она всегда отдаёт части A (это убирает зеркальные дубликаты).
Далее для каждой следующей клетки есть два варианта:
- Добавить в часть A
- Добавить в часть B
Для нашей фигуры из 8 клеток нужно выбрать ещё 3 клетки в часть A
(кроме первой). Всего вариантов: C(7,3) = 35
Дерево перебора (первые шаги):
Старт
/ \
Клетка 2 Клетка 2
в A в B
/ \ / \
Клетка3 Клетка3 Клетка3 Клетка3
в A в B в A в B
... ... ... ...
Пример одной ветви:
Клетка 1 → A (фиксировано)
Клетка 2 → A
Клетка 3 → A
Клетка 4 → A ✓ Часть A набрана (4 клетки)!
Клетка 5 → B (автоматически)
Клетка 6 → B
Клетка 7 → B
Клетка 8 → B
↓
Проверяем: равны ли части по форме?
✂️ Отсечение ветвей: три правила с примерами
1 Правило количества клеток
«Если в одной части уже набралось 4 клетки, остальные автоматически идут в другую»
✓ Продолжаем
В части A: 2 клетки
Нужно ещё: 2
Можно продолжать!
✗ Отсекаем
В части A: 5 клеток
Нужно: 4
Слишком много! Отсекаем.
2 Правило связности
«Части должны быть цельными, не распадаться на кусочки»
Как программа проверяет связность? Она идёт по клеткам последовательно.
Представьте: мы уже добавили 2 клетки в часть A, и они соединены. Теперь рассматриваем следующую клетку:
✓ Связная часть
Клетки 1 и 2 соединены.
Добавляем клетку 3 — она соседствует
с клеткой 1 → Все 3 связны!
✗ Потеряна связность
Клетки 1 и 2 соединены.
Но клетка 6 (внизу) не соседствует
ни с одной из них →
Часть распалась! Отсекаем!
3 Проверка равенства форм
«Фигуры должны совпадать после поворота или отражения»
Когда обе части набраны, программа пробует 8 способов наложения одной на другую:
💡 Эффект отсечения:
Без отсечения программа проверила бы все 35 вариантов.
С отсечением — только 10-15 перспективных ветвей.
Для больших фигур экономия времени достигает 90-95%!
🎯 Как программа «видит» фигуры: система координат
📐 Как присваиваются координаты?
Программа использует матричную систему координат:
- Первое число — номер строки (считаем сверху вниз, начиная с 0)
- Второе число — номер столбца (считаем слева направо, начиная с 0)
(0,0)
(0,1)
(0,2)
(0,3)
(1,0)
(1,1)
(1,2)
(1,3)
(2,0)
(2,1)
(2,2)
(2,3)
Пример: клетка в левом верхнем углу имеет координаты (0,0),
клетка справа от неё — (0,1), клетка под первой — (1,0).
Компьютер не понимает картинки. Для него фигура — это список координат.
Давайте посмотрим, как фигуры выглядят для программы:
Пример 1: Квадрат 2×2
// Координаты:
[(0,0), (0,1),
(1,0), (1,1)]
Пример 2: L-фигура
// Координаты:
[(0,0), (1,0), (2,0),
(2,1)]
🔄 Нормализация: как программа сравнивает формы
Когда программа проверяет, равны ли две части, она приводит их к
стандартному виду (нормализует). Вот как это работает:
Шаг 1: Сдвиг к началу координат
Программа находит минимальные координаты и вычитает их из всех клеток:
Было:
[(3,5), (3,6), (4,5)]
minRow = 3, minCol = 5
→
Стало:
[(0,0), (0,1), (1,0)]
Вычли (3,5) из каждой
Шаг 2: Сортировка координат
Программа сортирует координаты по возрастанию (сначала по строке, потом по столбцу):
// Было (в случайном порядке):
[(2,1), (0,0), (1,0), (0,1)]
// После сортировки:
[(0,0), (0,1), (1,0), (2,1)]
🎪 Пример проверки равенства форм
Допустим, программа нашла такое разделение нашей фигуры из 8 клеток:
Часть A (красная)
[(0,0), (1,0), (2,0), (2,1)]
Часть B (зелёная)
[(0,2), (1,2), (2,1), (2,2)]
Программа пробует все 8 трансформаций для части B:
Проверка 8 трансформаций для части B:
1. Исходная: [(0,2), (1,2), (2,1), (2,2)] → "0,2;1,2;2,1;2,2" ✗
2. Поворот 90°: [(0,0), (0,1), (0,2), (1,0)] → "0,0;0,1;0,2;1,0" ✗
3. Поворот 180°: [(0,0), (0,1), (1,1), (2,1)] → "0,0;0,1;1,1;2,1" ✗
4. Поворот 270°: [(0,2), (1,0), (1,1), (1,2)] → "0,2;1,0;1,1;1,2" ✗
5. Отражение: [(0,0), (1,0), (2,0), (2,1)] → "0,0;1,0;2,0;2,1" ✓ СОВПАЛО!
Часть A: "0,0;1,0;2,0;2,1"
Часть B (отраж.): "0,0;1,0;2,0;2,1"
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
Идентичны! Решение найдено! 🎉
🚀 Как работает программа
1 Проверка: чётное число клеток, фигура связная
2 Подсчёт вариантов по формуле сочетаний
3 Перебор в фоне (Web Worker) с отсечением бесперспективных ветвей
4 Визуализация: раскраска частей красным и зелёным
🧩 Попробуйте сами!
Нарисуйте фигуру ниже и нажмите «Найти разделение».
Наблюдайте, как программа перебирает варианты и находит решение!
Совет: начните с фигурок из 6-8 клеток — так вы увидите процесс в действии.
В следующей части: алгоритм поиска осей симметрии и эвристические методы
для ускорения перебора