Головоломка с подбором краев

Частично завершенная головоломка Eternity II.

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

Головоломки с сопоставлением краев, как известно, являются NP-полными и способны преобразовываться в эквивалентные головоломки и головоломки с упаковкой полимино и обратно . ^[1]

Первые головоломки с сопоставлением кромок были запатентованы в США Э.Л. Терстоном в 1892 году. ^[2] Текущие примеры коммерческих головоломок с сопоставлением кромок включают головоломку Eternity II , Tantrix , линейку головоломок Kadon Enterprises с сопоставлением кромок и Edge Match. Приложение "Пазлы" для iPhone.

Известные варианты [ править ]

Площади Мак-Магона [ править ]

Решение квадратов Мак-Магона с наибольшей одноцветной областью ^[3]

Квадраты Мак-Магона - это название развлекательной математической головоломки, предложенной британским математиком Перси Мак-Магоном , который опубликовал трактат о раскраске краев различных форм в 1921 году. ^{[4] В} этой конкретной головоломке используются 24 плитки, состоящие из всех перестановок трех цветов. для краев квадрата. Плитки должны быть расположены в прямоугольной области 6 × 4 так, чтобы все края совпадали, и, кроме того, для внешнего края прямоугольника использовался только один цвет. ^[5]

Эта головоломка может быть расширена до плиток с перестановками из 4 цветов, расположенных в 10 × 7. ^[6] В любом случае квадраты являются подмножеством плиток Ванга , уменьшая плитки, которые похожи при вращении. Решения исчисляются тысячами. ^[7]

MacMahon Squares, вместе с вариациями идеи, был коммерциализирован как Multimatch.

TetraVex [ править ]

GNOME Tetravex .

TetraVex - это компьютерная игра, которая представляет игроку квадратную сетку и набор плиток, по умолчанию девять квадратных плиток для сетки 3 × 3. Каждая плитка имеет четыре однозначных числа, по одному на каждом краю. Цель игры - разместить плитки в сетке в нужном месте, решив эту головоломку как можно быстрее. Плитки нельзя повернуть, и две можно разместить рядом друг с другом, только если числа на соседних краях совпадают. ^{[8] [9]}

TetraVex был вдохновлен «проблемой мозаики плоскости», описанной Дональдом Кнутом на странице 382 тома 1: Основные алгоритмы , первой книги из его серии «Искусство компьютерного программирования» . Он был назван Скоттом Фергюсоном, руководителем разработки и архитектором первой версии Visual Basic, написавшим его для Windows Entertainment Pack 3 . ^[10]

TetraVex также доступен как игра с открытым исходным кодом в коллекции GNOME Games . ^[11]

Возможное количество TetraVex можно подсчитать. На доске есть горизонтальные и вертикальные пары, которые должны совпадать, и числа по краям, которые можно выбирать произвольно. Следовательно, есть выбор из 10 цифр, то есть возможных плат.${\ Displaystyle п \ раз {} п}$${\ Displaystyle п (п-1)}$${\ displaystyle 4n}$${\ Displaystyle 2n (N-1) + 4n = 2n (N + 1)}$${\ displaystyle 10 ^ {2n (n + 1)}}$

Решение о том, есть ли у головоломки TetraVex решение, обычно является NP-полным . ^[12] Его вычислительный подход включает алгоритм Дугласа-Рачфорда . ^{[13] [14]}

Шестиугольники [ править ]

Змеи - это шестиугольные плитки, используемые в различных абстрактных стратегических играх, таких как Psyche-Paths, Kaliko и Tantrix . Внутри каждого змеевика края объединены в пары, таким образом ограничивая набор плиток таким образом, чтобы цвет краев не встречался нечетное количество раз в шестиугольнике.

Три измерения [ править ]

Математически головоломки с сопоставлением краев двумерны . 3D - край сопоставление головоломка такой головоломка , которая не является плоским в евклидове пространства , так что включает черепицу трехмерный области , такие как поверхности правильного многогранника . Как и раньше, многоугольные части имеют выделенные края, чтобы края соседних частей совпадали.

Трехмерные головоломки с согласованием краев в настоящее время не находятся под прямой патентной защитой США, так как срок действия патента 1892 года, выданного Э.Л. Терстоном, истек. ^[15] Текущие примеры коммерческих головоломок включают в себя Dodek Duo , The Enigma, Mental Misery, ^[16] и линейку трехмерных головоломок Kadon Enterprises. ^[17]

Включение согласования кромок [ править ]

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

См. Также [ править ]

• Домино черепица
• Домино Ван

Ссылки [ править ]

Внешние ссылки [ править ]

• Коллекция подходящих пазлов Эриха
• Полигоны с совпадающими цветами и краями , Питер Эссер ^{[ мертвая ссылка ]}
• Страница головоломки Роба от Роба Стегманна
• Квадраты с совпадением краев