Полёмино - Polyomino

«Полимино» перенаправляется сюда. Книгу Соломона Голомба см. Полимино: головоломки, выкройки, задачи и упаковки.
18 односторонних пентамино, в том числе 6 зеркальных пар
35 бесплатных гексомино, окрашенные в соответствии с их симметрией.
Единственный бесплатный домино.

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

Полимино использовались в популярных загадки по крайней мере с 1907 года, а перечень пентамино датируется античностью.[1] Многие результаты с фигурами от 1 до 6 квадратов были впервые опубликованы в Обзор Fairy Chess между 1937 и 1957 годами под названием «проблемы расслоения». Название полимино был изобретен Соломон В. Голомб в 1953 г.,[2] и это было популяризировано Мартин Гарднер в ноябре 1960 г. "Математические игры "столбец в Scientific American.[3]

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

В статистическая физика, изучение полиимино и их многомерных аналогов (которые часто называют решетчатые животные в этой литературе) применяется к задачам физики и химии. Полимино использовались как модели разветвленные полимеры и из просачивание кластеры.[4]

Как и многие головоломки развлекательной математики, полимино поднимает много комбинаторный проблемы. Самый простой - это перечисление полимино заданного размера. Никаких формул не найдено, кроме специальных классов полимино. Известен ряд оценок, и есть алгоритмы для их расчета.

Полимино с дырочками неудобно для некоторых целей, например, для задач укладки плитки. В некоторых случаях исключаются полимино с отверстиями, разрешая только односвязный полимино.[5]

Перечень полимино

Свободные, односторонние и фиксированные полимино

Есть три распространенных способа различения полимино для перечисления:[6][7]

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

В следующей таблице показано количество полимино различных типов с п клетки.

пимя (OEIS последовательность)свободныйодносторонний (A000988 )фиксированный (A001168 )
общий (A000105 )с дырками (A001419 )без дырок (A000104 )
1мономино10111
2домино10112
3Тромино20226
4тетромино505719
5пентамино120121863
6гексомино3503560216
7гептомино1081107196760
8Octomino36963637042,725
9нономино1,285371,2482,5009,910
10Decino4,6551954,4609,18936,446
11ундкомино17,07397916,09433,896135,268
12додекомино63,6004,66358,937126,759505,861

По состоянию на 2004 год, Иван Дженсен перечислил фиксированные полимино до п = 56; количество фиксированных полимино с 56 ячейками составляет примерно 6.915×1031.[8] Бесплатные полимино насчитывают до п = 28 пользователя Tomás Oliveira e Silva.[9]

Симметрии полимино

В группа диэдра D4 это группа из симметрии (группа симметрии ) квадрата. Эта группа содержит четыре поворота и четыре отражения. Он порождается чередующимися размышлениями о Икс-оси и около диагонали. Одно свободное полимино соответствует не более чем 8 фиксированным полимино, которые являются его изображениями при симметриях D4. Однако эти образы не обязательно различны: чем больше симметрии у свободного полимино, тем меньше у него различных фиксированных аналогов. Следовательно, свободное полимино, инвариантное относительно некоторых или всех нетривиальных симметрий D4 может соответствовать только 4, 2 или 1 фиксированным полимино. Математически бесплатные полимино классы эквивалентности фиксированных полимино под группой D4.

Полимино имеют следующие возможные симметрии;[10] наименьшее количество квадратов, необходимых в полимино с такой симметрией, дается в каждом случае:

  • 8 фиксированных полимино для каждого свободного полимино:
    • без симметрии (4)
  • 4 фиксированных полимино для каждого свободного полимино:
    • зеркальная симметрия относительно одного из направлений линий сетки (4)
    • зеркальная симметрия относительно диагональной линии (3)
    • 2-х кратная вращательная симметрия: C2 (4)
  • 2 фиксированных полимино для каждого свободного полимино:
    • симметрия относительно обоих направлений линий сетки и, следовательно, также 2-кратная симметрия вращения: D2 (2)
    • симметрия по отношению к обоим диагональным направлениям, а значит, и двукратная симметрия вращения: D2 (7)
    • 4-кратная вращательная симметрия: C4 (8)
  • 1 фиксированное полимино на каждое свободное полимино:
    • вся симметрия квадрата: D4 (1).

Точно так же количество односторонних полимино зависит от симметрии полимино следующим образом:

  • 2 односторонних полимино на каждое свободное полимино:
    • нет симметрии
    • 2-х кратная вращательная симметрия: C2
    • 4-х кратная вращательная симметрия: C4
  • 1 одностороннее полимино на каждое свободное полимино:
    • вся симметрия квадрата: D4
    • зеркальная симметрия относительно одного из направлений линий сетки
    • зеркальная симметрия относительно диагональной линии
    • симметрия относительно обоих направлений линий сетки, а значит, и двукратная симметрия вращения: D2
    • симметрия по отношению к обоим диагональным направлениям, а значит, и двукратная симметрия вращения: D2.

В следующей таблице показано количество полимино с п квадраты, отсортированные по группам симметрии.

пникто (A006749 )зеркало (90 °) (A006746 )зеркало (45 °) (A006748 )C2 (A006747 )D2 (90°) (A056877 )D2 (45°) (A056878 )C4 (A144553 )D4 (A142886 )
100000001
200001000
300101000
411011001
552211001
6206252000
7849743100
8316235184111
91,1963826194002
104,4619022738100
1116,750147917310200
1262,8783417927815333

[11]

Алгоритмы перебора фиксированных полимино

Индуктивные алгоритмы

Каждое полимино порядка п+1 можно получить, добавив квадрат к полимино порядка п. Это приводит к алгоритмам индуктивного создания полимино.

Проще говоря, учитывая список полимино порядка п, квадраты могут быть добавлены рядом с каждым полимино в каждой возможной позиции, и результирующий полимино порядка п+1 добавлен в список, если не дубликат уже найденного; уточнения порядка перечисления и маркировки соседних квадратов, которые не следует рассматривать, сокращают количество случаев, которые необходимо проверять на дублирование.[12] Этот метод можно использовать для подсчета как свободных, так и фиксированных полимино.

Более сложный метод, описанный Редельмайером, использовался многими авторами как способ не только подсчета полимино (без требования, чтобы все полимино порядка п храниться в порядке перечисления п+1), но также доказывая верхнюю границу их количества. Основная идея состоит в том, что мы начинаем с одного квадрата, а оттуда рекурсивно добавляем квадраты. В зависимости от деталей может учитываться каждый п-омино п раз, по одному разу с начала каждого из п квадраты, или могут быть расположены так, чтобы подсчитывать каждый только один раз.

Самая простая реализация предполагает добавление по одному квадрату за раз. Начиная с начального квадрата, пронумеруйте соседние квадраты по часовой стрелке сверху: 1, 2, 3 и 4. Теперь выберите число от 1 до 4 и добавьте квадрат в этом месте. Пронумеруйте ненумерованные соседние квадраты, начиная с 5. Затем выберите число, превышающее ранее выбранное, и добавьте этот квадрат. Продолжайте выбирать число, превышающее номер текущего квадрата, добавляя этот квадрат, а затем нумеруя новые соседние квадраты. Когда п созданы квадраты, п-omino был создан.

Этот метод обеспечивает точный подсчет каждого фиксированного полимино. п раз, по одному разу на каждую стартовую клетку. Его можно оптимизировать так, чтобы он считал каждое полимино только один раз, а не п раз. Начиная с начального квадрата, объявите его нижним левым квадратом полимино. Просто не нумеруйте квадраты в нижнем ряду или слева от квадрата в том же ряду. Это версия, описанная Редельмайером.

Если кто-то желает вместо этого подсчитывать свободные полимино, то можно проверить симметрию после создания каждого из них. п-омино. Однако это быстрее[13] отдельно генерировать симметричные полимино (разновидностью этого метода)[14] и таким образом определите количество свободных полимино по формуле Лемма Бернсайда.

Трансферно-матричный метод

Самый современный алгоритм для подсчета фиксированных полимино был открыт Иван Дженсен.[15] Улучшение метода Эндрю Конвея,[16] он экспоненциально быстрее, чем предыдущие методы (однако время его работы все еще экспоненциально в п).

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

Хотя у него отличное время работы, компромисс заключается в том, что этот алгоритм использует экспоненциальный объем памяти (многие гигабайты памяти необходимы для п выше 50), гораздо сложнее запрограммировать, чем другие методы, и в настоящее время не может использоваться для подсчета бесплатных полимино.

Асимптотический рост числа полимино

Фиксированные полимино

Теоретические аргументы и численные расчеты подтверждают оценку количества фиксированных полимино размера n.

куда λ = 4,0626 и c = 0.3169.[17] Однако этот результат не доказан, и значения λ и c это только оценки.

Известные теоретические результаты далеко не так конкретны, как эта оценка. Было доказано, что

существуют. Другими словами, Ап растет экспоненциально. Самая известная нижняя оценка для λ равно 4.00253.[18] Самая известная верхняя граница, не улучшавшаяся с 1970-х годов, - это λ < 4.65.[19]

Простым, но очень эффективным методом определения нижней границы является соединение полимино. Определите верхний правый квадрат как крайний правый квадрат в самом верхнем ряду полимино. Аналогичным образом определите нижний левый квадрат. Затем верхний правый квадрат любого полимино размера п может быть прикреплен к нижнему левому квадрату любого полимино размера м произвести уникальный (п+м) -омино. Это доказывает АпАм ≤ Ап+м. Используя это уравнение, можно показать λ ≥ (Ап)1/п для всех п. Уточнения этой процедуры в сочетании с данными для Ап произведите нижнюю границу, указанную выше.

Верхняя оценка достигается путем обобщения индуктивного метода перечисления полимино. Вместо того, чтобы добавлять по одному квадрату за раз, каждый раз добавляет кластер квадратов. Это часто называют добавлением веточки. Доказав, что каждый п-омино - это последовательность веточек, и, доказывая ограничения на комбинации возможных веточек, можно получить верхнюю границу количества веточек. п-омино. Например, в алгоритме, описанном выше, на каждом шаге мы должны выбирать большее число, и добавляются не более трех новых чисел (так как не более трех ненумерованных квадратов соседствуют с любым пронумерованным квадратом). Это можно использовать для получения верхней границы 6,75. Используя 2,8 миллиона веточек, Кларнер и Ривест получил верхнюю оценку 4,65.

Бесплатные полимино

Приближенные значения количества фиксированных и свободных полимино связаны простым способом. Бесплатное полимино без симметрии (вращение или отражение) соответствует 8 отдельным фиксированным полимино, а для большого п, наиболее п-омино не имеют симметрии. Следовательно, количество фиксированных п-омино примерно в 8 раз превышает количество бесплатных п-омино. Более того, это приближение экспоненциально точнее, поскольку п увеличивается.[10]

Специальные классы полимино

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

Определение выпуклый полимино отличается от обычного определения выпуклость, но похоже на определение, используемое для ортогональная выпуклая оболочка. Полимино называется вертикально или же столбец выпуклый если его пересечение с любой вертикальной линией выпукло (другими словами, в каждом столбце нет отверстий). Аналогично, полимино называется по горизонтали или же ряд выпуклый если его пересечение с любой горизонтальной линией выпукло. Полимино называется выпуклый если это выпуклая строка и столбец.[20]

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

Направленные полимино,[21] столбчатые (или рядные) выпуклые полимино,[22] и выпуклые полимино[23] были эффективно пронумерованы по площади п, а также некоторыми другими параметрами, такими как периметр, используя производящие функции.

Полимино - это уравновешенный если его площадь равна периметру. Ровный полимино должен быть сделан из четное число квадратов; возможно любое четное число больше 15. Например, 16-омино в форме квадрата 4 × 4 и 18-омино в форме прямоугольника 3 × 6 равны. Для полимино с менее чем 15 квадратами периметр всегда превышает площадь.[24]

Плитка с полимино

В развлекательная математика, проблемы часто ставятся перед черепица заданная область или вся плоскость с полимино,[25] и связанные с этим проблемы исследуются в математика и Информатика.

Мозаичные области с наборами полимино

Головоломки обычно требуют разбить данную область мозаикой с заданным набором полимино, например, 12 пентамино. В книгах Голомба и Гарднера есть много примеров. Типичная головоломка состоит в том, чтобы выложить прямоугольник 6 × 10 плиткой из двенадцати пентамино; 2339 решений этой проблемы были найдены в 1960 году.[26] Если разрешено несколько копий полимино в наборе, Голомб определяет иерархию различных регионов, которые набор может быть разделен на мозаику, таких как прямоугольники, полосы и вся плоскость, и показывает, могут ли полимино из данного набора мозаить самолет неразрешимый, отображая множества Ванская плитка к наборам полимино.[27]

В Пазл Судокус квадратная сетка выложена полиноминообразными областями (последовательность A172477 в OEIS ).

Мозаичные области с копиями одного полимино

Другой класс задач спрашивает, могут ли копии данного полимино замощить прямоугольник, и если да, то какие прямоугольники они могут выложить.[28] Эти проблемы были тщательно изучены для конкретных полимино,[29] и таблицы результатов для отдельных полимино доступны.[30] Кларнер и Гёбель показал, что для любого полимино существует конечное множество основной прямоугольники, которые он плитки, так что все другие прямоугольники, которые он плитки может быть мозаикой, эти простые прямоугольники.[31][32] Каменецкий и Кук показали, как различные непересекающиеся (так называемые «дырявые») полимино могут мозаить прямоугольники.[33]

Помимо прямоугольников, Голомб дал свою иерархию для одиночных полимино: полимино может выложить прямоугольник, половину полосы, изогнутую полосу, увеличенную копию самого себя, квадрант, полосу, полосу полуплоскость, весь самолет, определенные комбинации или ничего из этого. Среди них есть определенные последствия, как очевидные (например, если полимино кладет плитку в полуплоскость, то она покрывает всю плоскость), так и меньшие (например, если полимино кладет плитку на увеличенную копию самого себя, то он кладет мозаику в квадрант) . В этой иерархии охарактеризованы полиомино порядков до 6 (со статусом одного гексомино, позже обнаруженного для мозаичного прямоугольника, неразрешенного в то время).[34]

В 2001 Кристофер Мур и Джон Майкл Робсон показали, что проблема мозаики одного полимино копиями другого является НП-полный.[35][36]

Укладка плоскости копиями одного полимино

Два мозаичных нономино, не удовлетворяющих критерию Конвея.

Также много обсуждалось мозаичное размещение на плоскости копий одного полимино. В 1965 году было отмечено, что все полимино вплоть до гексомино[37] и все, кроме четырех гептамино, покрывают самолет.[38] Затем Дэвид Берд установил, что все, кроме 26 октамино, покрывают самолет.[39] Роусхорн обнаружил, что все, кроме 235 полимино 9-го порядка,[40] и такие результаты были распространены на более высокие порядки Роадсом (до 14-го)[41] и другие. Полимино, покрывающие плоскость, классифицируются по симметрии их мозаик и по количеству аспектов (ориентаций), в которых плитки появляются в них.[42][43]

Изучение того, какие полимино могут выложить плоскость, было облегчено с помощью Критерий Конвея: за исключением двух нонимино, все мозаичные полимино до порядка 9 образуют фрагмент по крайней мере из одной плитки, удовлетворяющей ему, с более частыми исключениями более высокого порядка.[44]

Несколько полимино могут размещать более крупные копии самих себя, и рекурсивное повторение этого процесса дает реплика облицовка плоскости. Например, для каждого положительного целого числа п, можно комбинировать п2 копии L-тромино, L-тетромино или P-пентомино в единую большую форму, подобную меньшей полимино, из которой оно было образовано.[45]

Укладка общей фигуры мозаикой из различных полимино

Минимальный показатель совместимости для T и W пентамино.

В проблема совместимости состоит в том, чтобы взять два или более полимино и найти фигуру, которую можно выложить плиткой с каждым из них. Совместимость с полиомино широко изучается с 1990-х годов. Хорхе Луис Мирелес и Джованни Реста опубликовали веб-сайты с систематическими результатами,[46][47] а Ливио Зукка показывает результаты для некоторых сложных случаев, таких как три разных пентамино.[48] Общая проблема может быть сложной. Первый показатель совместимости пентамино L и X был опубликован в 2005 году и состоял из 80 плиток каждого вида.[49] Было доказано, что многие пары полимино несовместимы систематическим исчерпанием. Неизвестно ни одного алгоритма для определения совместимости двух произвольных полимино.

Полимино в головоломках и играх

В дополнение к задачам, связанным с мозаикой, описанным выше, существуют развлекательные математические головоломки, которые требуют складывания полимино для создания других фигур. Гарднер предложил несколько простых игр с набором бесплатных пентамино и шахматной доской. Некоторые варианты Судоку головоломка использует некоминообразные области на сетке. Видеоигра Тетрис основан на семи односторонних тетромино (в игре пишется «Tetriminos») и настольной игре Блокус использует все бесплатные полимино вплоть до пентамино.

Этимология

Слово полимино и названия различных отрядов полимино являются производными от слова домино, обычная игровая фишка, состоящая из двух квадратов, первая буква d- причудливо интерпретируется как версия приставки ди- что означает «два». Название домино потому что игровая фишка, как полагают, происходит от пятнистой маскарадной одежды домино, от латинского доминус.[50]

Большинство из числовые префиксы греческие. Полимино 9 и 11 порядка чаще принимают латинские префиксы. нона- (нономино) и undeca- (ундекомино), чем греческие префиксы ennea- (эннеомино) и hendeca- (хендекомино).

Смотрите также

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

Примечания

  1. ^ Голомб (Полимино, Предисловие к первому изданию) пишет «наблюдение о том, что существует двенадцать отличительных узоров (пентамино), которые могут быть образованы пятью соединенными камнями на Идти доска… приписывается древнему мастеру той игры ».
  2. ^ Голомб, Соломон В. (1994). Полимино (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN  978-0-691-02444-8.
  3. ^ Гарднер, М. (ноябрь 1960 г.). «Подробнее о формах, которые можно сделать сложными домино (математические игры)». Scientific American. 203 (5): 186–201. Дои:10.1038 / Scientificamerican1160-186. JSTOR  24940703.
  4. ^ Whittington, S.G .; Сотерос, К.Э. (1990). «Решетчатые животные: точные результаты и дикие догадки». В Grimmett, G .; Уэлш, Д. (ред.). Беспорядок в физических системах. Издательство Оксфордского университета.
  5. ^ Грюнбаум, Бранко; Шепард, Г. (1987). Плитки и узоры. Нью-Йорк: W.H. Фримен и компания. ISBN  978-0-7167-1193-3.
  6. ^ Редельмайер, Д. Хью (1981). «Подсчет полимино: еще одна атака». Дискретная математика. 36 (2): 191–203. Дои:10.1016 / 0012-365X (81) 90237-5.
  7. ^ Голомб, глава 6
  8. ^ Иван Дженсен. «Серия для решетчатых зверюшек или полимино». В архиве из оригинала от 12.06.2007. Получено 2007-05-06.
  9. ^ Томас Оливейра и Сильва. "Перечисления животных на {4,4} евклидовой плитке". В архиве из оригинала от 23.04.2007. Получено 2007-05-06.
  10. ^ а б Редельмайер, секция 3
  11. ^ Подсчет полимино: еще одна атака
  12. ^ Голомб, стр. 73–79.
  13. ^ Редельмайер, секция 4
  14. ^ Редельмайер, секция 6
  15. ^ Дженсен, Иван (февраль 2001 г.). «Перечисления решетчатых животных и деревьев». Журнал статистической физики. 102 (3–4): 865–881. arXiv:cond-mat / 0007239. Bibcode:2001JSP ... 102..865J. Дои:10.1023 / А: 1004855020556.
  16. ^ Конвей, Эндрю (1995). «Перечисление 2D перколяционных рядов методом конечных решеток: теория». Журнал физики A: математические и общие. 28 (2): 335–349. Bibcode:1995JPhA ... 28..335C. Дои:10.1088/0305-4470/28/2/011. Zbl  0849.05003.
  17. ^ Дженсен, Иван; Гуттманн, Энтони Дж. (2000). «Статистика решетчатых зверей (полимино) и многоугольников». Журнал физики A: математические и общие. 33 (29): L257 – L263. arXiv:cond-mat / 0007238v1. Bibcode:2000JPhA ... 33L.257J. Дои:10.1088/0305-4470/33/29/102.
  18. ^ Барекет, Джилл. «λ> 4: улучшенная нижняя граница константы роста полимино». Получено 2017-02-02. Цитировать журнал требует | журнал = (помощь)
  19. ^ Klarner, D.A .; Ривест, Р.Л. (1973). "Процедура улучшения верхней границы количества п-омино » (PDF). Канадский математический журнал. 25 (3): 585–602. CiteSeerX  10.1.1.309.9151. Дои:10.4153 / CJM-1973-060-4. Архивировано из оригинал (PDF версии технического отчета) на 2006-11-26. Получено 2007-05-11.
  20. ^ Уилф, Герберт С. (1994). Генерацияфункционологии (2-е изд.). Бостон, Массачусетс: Academic Press. п. 151. ISBN  978-0-12-751956-2. Zbl  0831.05001.
  21. ^ Буске-Мелу, Мирей (1998). «Новые результаты подсчета двумерных животных». Дискретная математика. 180 (1–3): 73–106. Дои:10.1016 / S0012-365X (97) 00109-X.
  22. ^ Делест, М.-П. (1988). «Производящие функции для столбчато-выпуклых полимино». Журнал комбинаторной теории, серия А. 48 (1): 12–31. Дои:10.1016/0097-3165(88)90071-4.
  23. ^ Буске-Мелу, Мирей; Феду, Жан-Марк (1995). "Производящая функция выпуклых полимино: разрешение q-дифференциальная система ». Дискретная математика. 137 (1–3): 53–75. Дои:10.1016 / 0012-365X (93) E0161-V.
  24. ^ Пиччиотто, Анри (1999), Лаборатория геометрии, MathEducationPage.org, стр. 208.
  25. ^ Мартин, Джордж Э. (1996). Полимино: Путеводитель по головоломкам и проблемам при укладке плитки (2-е изд.). Математическая ассоциация Америки. ISBN  978-0-88385-501-0.
  26. ^ C.B. Haselgrove; Дженифер Хазелгроув (октябрь 1960 г.). «Компьютерная программа для пентамино». Эврика. 23: 16–18.
  27. ^ Голомб, Соломон В. (1970). «Плитка с наборами полимино». Журнал комбинаторной теории. 9: 60–71. Дои:10.1016 / S0021-9800 (70) 80055-2.
  28. ^ Голомб, Полимино, глава 8
  29. ^ Рид, Майкл. «Ссылки на выпрямляемые полиомино». Архивировано из оригинал на 2004-01-16. Получено 2007-05-11.
  30. ^ Рид, Майкл. «Список известных простых прямоугольников для различных полимино». Архивировано из оригинал на 2007-04-16. Получено 2007-05-11.
  31. ^ Кларнер, Д.А.; Гебель, Ф. (1969). «Упаковочные коробки с одинаковыми фигурами». Indagationes Mathematicae. 31: 465–472.
  32. ^ Кларнер, Дэвид А. (февраль 1973 г.). «Возвращение к теореме о конечном базисе» (PDF). Технический отчет Стэнфордского университета STAN-CS-73–338. Архивировано из оригинал (PDF) на 2007-10-23. Получено 2007-05-12.
  33. ^ Каменецкий Дмитрий; Кук, Тристром (2015). «Укладка прямоугольников дырявыми полимино». arXiv:1411.2699 [cs.CG ].
  34. ^ Голомб, Соломон В. (1966). «Плитка из полимино». Журнал комбинаторной теории. 1 (2): 280–296. Дои:10.1016 / S0021-9800 (66) 80033-9.
  35. ^ Мур, Кристофер; Робсон, Джон Майкл (2001). «Проблемы с жесткой плиткой с помощью простых плиток» (PDF). Архивировано из оригинал (PDF) на 2013-06-17.
  36. ^ Петерсен, Иварс (25 сентября 1999 г.), "Математический путь: мозаика с помощью полимино", Новости науки, в архиве с оригинала 20 марта 2008 г., получено Одиннадцатое марта, 2012.
  37. ^ Гарднер, Мартин (июль 1965 г.). «О соотношении математики и упорядоченных образцов оп-арта». Scientific American. 213 (1): 100–104. Дои:10.1038 / scientificamerican1265-100.
  38. ^ Гарднер, Мартин (август 1965). «Мысли о задаче общения с разумными организмами в иных мирах». Scientific American. 213 (2): 96–100. Дои:10.1038 / scientificamerican0865-96.
  39. ^ Гарднер, Мартин (август 1975). «Еще о мозаике плоскости: возможности полимино, полиалмазов и полигексов». Scientific American. 233 (2): 112–115. Дои:10.1038 / scientificamerican0875-112.
  40. ^ Росторн, Дэниел А. (1988). «Сложность плитки малая п-омино
    (п<10)"    . Дискретная математика. 70: 71–75. Дои:10.1016 / 0012-365X (88) 90081-7.
  41. ^ Роадс, Гленн С. (2003). Плоские мозаики и поиск апериодического прототила. Кандидатская диссертация, Университет Рутгерса.
  42. ^ Грюнбаум и Шепард, раздел 9.4
  43. ^ Китинг, К .; Винс, А. (1999). "Изоэдральная мозаика Полимино плоскости". Дискретная и вычислительная геометрия. 21 (4): 615–630. Дои:10.1007 / PL00009442.
  44. ^ Роадс, Гленн С. (2005). «Плоские мозаики из полимино, полигексов и полиалмазов». Журнал вычислительной и прикладной математики. 174 (2): 329–353. Дои:10.1016 / j.cam.2004.05.002.
  45. ^ Niică, Виорел (2003). «Повторение плитки». МАССА selecta. Провиденс, Род-Айленд: Американское математическое общество. С. 205–217. МИСТЕР  2027179.
  46. ^ Мирелес, Дж. Л., "Поли2омино "
  47. ^ "Реста, Г." Полиполёмино."". В архиве из оригинала от 22.02.2011. Получено 2010-07-02.
  48. ^ "Zucca, L." Воспоминания о программном прошлом"". В архиве из оригинала от 15.03.2012. Получено 2011-12-15.
  49. ^ Барбанс, Улдис; Цибулис, Андрис; Ли, Гилберт; Лю, Энди; Уэйнрайт, Роберт (2005). «Теория чисел Полимино (III)». В Сипра, Барри Артур; Demaine, Erik D .; Demaine, Martin L .; Роджерс, Том (ред.). Дань математику. Уэллсли, Массачусетс: А.К. Питерс. С. 131–136. ISBN  978-1-56881-204-5.
  50. ^ Оксфордский словарь английского языка, 2-е издание, запись домино

внешняя ссылка

Онлайн-решатели полимино

Публикации