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

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

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

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

Известные вариации

Площади Мак-Магона

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

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

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

ТетраВекс

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

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

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

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

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

Шестиугольники

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

Три измерения

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

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

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

Часть игры «Каркассон», показывающая совпадающие края.

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

См. также

Ссылки

^ Эрик Д. Демейн , Мартин Л. Демейн . «Головоломки, сопоставление ребер и упаковка полимино: связи и сложность» (PDF) . Проверено 12 августа 2007 г.
^ Jump up to: ^а ^б «Страница головоломки Роба: Сопоставление краев» . Архивировано из оригинала 22 октября 2007 г. Проверено 12 августа 2007 г.
^ Гарднер, Мартин (2009). Сферическая упаковка, Льюис Кэролл и Реверси . Издательство Кембриджского университета.
^ МакМахон, Перси Александр (1921). Новые математические игры . Герштейн – Университет Торонто. Кембридж, Университетское издательство.
^ Стеклз, Кэти. Blackboard Bold: квадраты Мак-Магона . Проверено 10 марта 2021 г.
^ Гай. Кубический корень из 31. Плитки Вана . Проверено 12 апреля 2021 г.
^ Уэйд Филпотт (в титрах). Кадон Энтерпрайзис. Мультиматч . Проверено 12 апреля 2021 г.
^ Уиттум, Кристофер (2013). Активизируйте образование с помощью открытого исходного кода . стр. 32.
^ Ганье, Марсель (2006). Переходим на Ubuntu Linux .
^ «Рождение Visual Basic» . Forestmoon.com . Проверено 11 мая 2010 г.
^ «Лицензия — README» . гномы-игры . gnome.org. 2011 . Проверено 2 октября 2012 г.
^ Такенага, Ясухико; Уолш, Тоби (15 сентября 2006 г.). «TetraVex NP-полна» . Письма об обработке информации . 99 (5). Письма об обработке информации, том 99, выпуск 5, страницы 171–174: 171–174. дои : 10.1016/j.ipl.2006.04.010 . S2CID 7228681 .
^ Линстрем, Скотт Б.; Симс, Брейли (2020). Опрос: Шестьдесят лет Дугласу Рэчфорду. Издательство Кембриджского университета.
^ «Страница головоломок Роба: Пазлы с узорами» . Проверено 22 июня 2009 г.
^ «Kadon Enterprises, больше о Edgematching» . Проверено 22 июня 2009 г.

Внешние ссылки

Коллекция головоломок Эриха на пару
Страница-головоломка Роба , автор Роб Стегманн
Квадраты, совпадающие по краям

Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[Demaine-1] Эрик Д. Демейн , Мартин Л. Демейн . «Головоломки, сопоставление ребер и упаковка полимино: связи и сложность» (PDF) . Проверено 12 августа 2007 г.

[:1-2] Jump up to: ^а ^б «Страница головоломки Роба: Сопоставление краев» . Архивировано из оригинала 22 октября 2007 г. Проверено 12 августа 2007 г.

[3] Гарднер, Мартин (2009). Сферическая упаковка, Льюис Кэролл и Реверси . Издательство Кембриджского университета.

[4] МакМахон, Перси Александр (1921). Новые математические игры . Герштейн – Университет Торонто. Кембридж, Университетское издательство.

[5] Стеклз, Кэти. Blackboard Bold: квадраты Мак-Магона . Проверено 10 марта 2021 г.

[6] Гай. Кубический корень из 31. Плитки Вана . Проверено 12 апреля 2021 г.

[7] Уэйд Филпотт (в титрах). Кадон Энтерпрайзис. Мультиматч . Проверено 12 апреля 2021 г.

[8] Уиттум, Кристофер (2013). Активизируйте образование с помощью открытого исходного кода . стр. 32.

[9] Ганье, Марсель (2006). Переходим на Ubuntu Linux .

[10] «Рождение Visual Basic» . Forestmoon.com . Проверено 11 мая 2010 г.

[11] «Лицензия — README» . гномы-игры . gnome.org. 2011 . Проверено 2 октября 2012 г.

[12] Такенага, Ясухико; Уолш, Тоби (15 сентября 2006 г.). «TetraVex NP-полна» . Письма об обработке информации . 99 (5). Письма об обработке информации, том 99, выпуск 5, страницы 171–174: 171–174. дои : 10.1016/j.ipl.2006.04.010 . S2CID 7228681 .

[13] Линстрем, Скотт Б.; Симс, Брейли (2020). Опрос: Шестьдесят лет Дугласу Рэчфорду. Издательство Кембриджского университета.

[14] «Страница головоломок Роба: Пазлы с узорами» . Проверено 22 июня 2009 г.

[15] «Kadon Enterprises, больше о Edgematching» . Проверено 22 июня 2009 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]