Polyomino
-
Определение и история полимино
- Полимино — это плоская геометрическая фигура, состоящая из квадратов.
- Полимино использовались в головоломках с 1907 года.
- Название «полимино» было введено Соломоном В. Голомбом в 1953 году.
-
Типы полимино
- Свободные полимино: не являются жесткими преобразованиями друг друга.
- Односторонние полимино: не являются вращениями или отражениями друг друга.
- Фиксированные полимино: не являются переводами друг друга.
-
Симметрии полимино
- Группа D4 описывает симметрии квадрата.
- Одно свободное полимино соответствует до 8 фиксированных полимино.
- Полимино могут иметь различные симметрии, такие как отсутствие симметрии, зеркальная симметрия и 2-кратная вращательная симметрия.
-
Алгоритмы перечисления полимино
- Индуктивные алгоритмы: добавление квадратов к полимино для получения новых полимино.
- Метод Редельмейера: рекурсивное добавление квадратов для подсчета полимино.
- Метод трансфер-матрицы: экспоненциально быстрый, но требует много памяти.
-
Асимптотический рост числа полимино
- Теоретические аргументы и численные расчеты поддерживают экспоненциальный рост числа фиксированных полимино.
- Известны нижние и верхние границы для числа полимино.
- Метод конкатенации полимино используется для установления нижних границ.
-
Методы перечисления полимино
- Метод добавления кластеров квадратов вместо одного квадрата за раз.
- Метод доказательства, что каждое n-мино является последовательностью кластеров.
- Метод получения верхней границы числа n-мино.
-
Свободные полимино
- Приближения для числа фиксированных и свободных полимино связаны.
- Число фиксированных полимино приблизительно в 8 раз больше числа свободных полимино.
-
Специальные классы полимино
- Точные формулы для перечисления полимино специальных классов.
- Определение выпуклых полимино.
- Определение направленных полимино.
-
Задачи с полимино
- Задачи на укладку полимино в заданной области.
- Проблемы с укладкой полимино в прямоугольники и другие фигуры.
- Уровни иерархии полимино по укладкой в различные области.
-
Полимино в играх и головоломках
- Игры и головоломки с использованием полимино.
- Примеры: Sudoku, Tetris, Blokus.
-
Этимология
- Слово «полимино» происходит от «домино».
- Полимино используются в различных областях математики и физики.