Пазл Вечность II

Пазл Eternity II ( E2 или E II ) — это головоломка с сопоставлением краев, выпущенная 28 июля 2007 года. ^{[ 1 ]}^{[ 2 ]} Она была разработана Кристофером Монктоном и продана и защищена авторскими правами TOMY UK Ltd как преемник оригинальной головоломки Eternity . Эта головоломка была частью конкурса , в котором за первое полное решение предлагался приз в 2 миллиона долларов. Соревнование завершилось в полдень 31 декабря 2010 г., но решение не было найдено.

Описание

Пазл Eternity II представляет собой головоломку с сопоставлением краев , которая включает в себя размещение 256 квадратных частей головоломки в сетку 16 × 16, ограниченную требованием совмещения соседних краев. Задача была разработана таким образом, чтобы ее было трудно решить с помощью грубого компьютерного поиска.

Края каждой части головоломки на одной стороне отмечены различными комбинациями формы и цвета (здесь они называются «цветами»), каждая из которых должна точно совпадать с соседней стороной на каждой соседней части, когда головоломка завершена. Другая сторона каждой детали пуста, за исключением идентификационного номера, и не используется в головоломке. Таким образом, каждую деталь можно использовать только в 4 направлениях. Имеется 22 цвета, не считая серых краев. Пять цветов встречаются исключительно в 60 парах ребер («ромбах») самого внешнего кольца, то есть между границей и угловыми частями, а остальные 17 используются в остальных 420 «внутренних» парах ребер. Цвета используются равномерно: каждый из 5 цветов границ используется ровно в 12 парах краев, а каждый из 17 внутренних цветов используется либо для 24 пар краев (5 цветов), либо для 25 пар краев (12 цветов). Общее количество пар ребер — 480. Один из пяти цветов границы не найден ни на одном угловом элементе, в то время как все 17 внутренних цветов используются на элементе границы хотя бы один раз.

В наборе 4 угловых элемента (с двумя серыми сторонами), 56 бордюров (с одной серой стороной) и 14 ² = 196 внутренних деталей (с четырьмя цветными сторонами). Каждая деталь имеет уникальное расположение цветов, и ни одна из фигур не является вращательно-симметричной, поэтому каждый из 256 × 4 = 1024 вариантов выбора фигуры и ориентации приводит к разному рисунку цветов краев.

Головоломка отличается от первой головоломки Eternity тем, что в ней есть необязательный стартовый элемент (обязательная подсказка), который необходимо разместить в определенном положении и ориентации рядом с центром доски. ^{[ 3 ]}

С запуском продукта были доступны две головоломки с подсказками, каждая из которых в случае решения дает положение части (подсказку) в основной головоломке из 256 частей. Головоломка-подсказка 1 представляет собой квадратную головоломку из 36 частей (6 × 6), а головоломка-подсказка 2 — прямоугольную головоломку из 72 частей (12 × 6). В 2008 году были доступны две дополнительные головоломки с подсказками тех же размеров: головоломка-подсказка из 36 частей и головоломка-подсказка из 72 частей 4. В книге правил указано, что головоломку можно решить без использования подсказок. ^{[ 3 ]}

Сложность

Число возможных конфигураций головоломки Eternity II, если предположить, что все части различны, и игнорировать фиксированные части с заранее определенным положением, составляет 256! × 4 ²⁵⁶, примерно 1,15 × 10 ⁶⁶¹. Более точную верхнюю границу возможного количества конфигураций можно получить, приняв во внимание фиксированную часть в центре и ограничения, установленные для частей по краям: 1 × 4! × 56! × 195! × 4 ¹⁹⁵, примерно 1,12 × 10 ⁵⁵⁷. Дополнительную верхнюю границу можно получить, рассмотрев положение и ориентацию частей подсказки, полученных при решении головоломок. В этом случае известно положение и ориентация пяти фигур, что дает верхнюю границу 4! × 56! × 191! × 4 ¹⁹¹ = 3.11 × 10 ⁵⁴⁵, что дает пространство поиска 3,70 × 10 ¹¹⁵ раз меньше, чем в первом приближении.

В первом приближении ограничение соответствия ребер уменьшает количество допустимых конфигураций в коэффициент (1/5) для каждой пары граничных ребер и (1/17) для каждой пары внутренних ребер. Тогда количество допустимых конфигураций увеличивается до 4! × 56! × 196! × 4 ¹⁹⁶ × (1/5) ⁶⁰ × (1/17) ⁴²⁰ ≈ 16,4, что очень близко к единице. Это указывает на то, что головоломка, вероятно, была разработана так, чтобы иметь только одно или несколько решений. ^{[ 4 ]}^{[ 5 ]} что максимизирует сложность: больше решений (более слабые ограничения, например, меньше цветов) облегчит поиск решения (одного из многих), в то время как более жесткие ограничения уменьшат пространство поиска, упрощая поиск (уникального) решения. Оптимизация количества цветов была исследована эмпирически для небольших головоломок, что подтвердило это наблюдение. ^{[ 6 ]}

Конкуренция и решение

После первой даты проверки 31 декабря 2008 г. было объявлено, что полного решения найдено не было. Премия в размере 10 000 долларов была присуждена Луи Верхаарду из Лунда в Швеции за частичное решение проблемы. ^{[ 7 ]} с 467 совпадающими ребрами из 480. ^{[ 8 ]} Верхаард опубликовал еще три частичных решения с таким же количеством совпадающих ребер. ^{[ 7 ]}

По состоянию на 30 января 2011 года официальный сайт Eternity II объявляет, что «Окончательная дата правильного решения головоломки Eternity II проходит без победителя, а приз в 2 миллиона долларов за правильное решение головоломки Eternity II остается невостребованным». ^{[ 9 ]}

Ни одно проверенное полное решение головоломки Eternity 2 никогда не публиковалось. Сюда входит предполагаемое решение Кристофера Монктона, которое остается неопубликованным. Известно, что в сети было распространено несколько фейковых решений.

История и дизайн

Оригинальная головоломка Eternity представляла собой мозаику с призом в миллион фунтов, созданную Монктоном . Запущенная в июне 1999 года, она была решена с помощью алгоритма компьютерного поиска, разработанного Алексом Селби и Оливером Риорданом , который использовал комбинаторные недостатки оригинального дизайна головоломки. ^{[ 10 ]} Призовые были полностью выплачены Селби и Риордану.

Головоломка, поразительно похожая на обе головоломки вечности, «Алмазная дилемма», крайний срок которой приходится на 1990 год, то есть на 10 лет раньше крайнего срока исходной головоломки вечности, имеет меньше частей — 160 по сравнению с 209 и 256 в первых двух головоломках вечности соответственно. и тем не менее, алмазная дилемма так и не была решена вот уже более 25 лет.

Головоломка Eternity II была разработана Монктоном в 2005 году, на этот раз в сотрудничестве с Селби и Риорданом, которые разработали компьютерную программу, которая создала окончательный дизайн Eternity II. ^{[ 11 ]} По словам энтузиаста математических игр Брендана Оуэна, головоломка Eternity II, похоже, была разработана, чтобы избежать комбинаторных недостатков предыдущей головоломки, а параметры конструкции, похоже, были выбраны так, чтобы сделать головоломку максимально сложной для решения. В частности, в отличие от оригинальной головоломки Eternity, вероятно, будет очень небольшое количество возможных решений проблемы. ^{[ 4 ]} По оценкам Оуэна, поиск с возвратом методом грубой силы может занять около 2 × 10 ⁴⁷ шаги для завершения. ^{[ 12 ]}

процитировала Монктона В 2005 году The Times :

«Наши расчеты заключаются в том, что если вы воспользуетесь самым мощным в мире компьютером и позволите ему работать с этого момента и до предполагаемого конца Вселенной, он, возможно, не наткнется ни на одно из решений». ^{[ 11 ]}

Хотя было продемонстрировано, что класс головоломок с сопоставлением ребер , частным случаем которого является Eternity II, в целом является NP-полным , ^{[ 13 ]} то же самое можно сказать и об общем классе задач об упаковке многоугольников, частным случаем которых была оригинальная головоломка Eternity.

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

См. также

TetraVex , аналогичная, более простая (без вращения частей и рамок) игра-головоломка с сопоставлением краев из Microsoft Entertainment Pack , ^{[ 14 ]} показано, что NP-полна . ^{[ 15 ]}

Ссылки

^ «Investegate | Объявления TOMY | TOMY: Глобальный запуск Eternity II в Hamleys за 2 доллара США…» Investegate.co.uk . Новостная лента по связям с общественностью. 26 июля 2007 года . Проверено 5 октября 2020 г.
^ «Телевизионное интервью с Кристофером Монктоном и Бренданом Оуэном» . Утро с Керри-Энн, канал Брендана Оуэна, YouTube . 26 июля 2007 г. Архивировано из оригинала 21 декабря 2021 г.
^ Перейти обратно: ^а ^б Буклет с инструкцией (PDF, в архиве) , опубликован на официальном сайте.
^ Перейти обратно: ^а ^б Оуэн, Брендан (2007). «Вечность II – Дизайн» . Веб-сайт Брендана Оуэна Eternity II . Архивировано из оригинала 10 декабря 2007 года . Проверено 9 ноября 2007 г.
^ Ансотеги, Карлос; Бежар, Рамон; Фернандес, Сезар; Матеу, Карлес (3 июля 2008 г.). «Насколько сложна коммерческая головоломка: вызов Eternity II» . Материалы конференции 2008 года по исследованиям и разработкам искусственного интеллекта: материалы 11-й Международной конференции Каталонской ассоциации искусственного интеллекта . НЛД: IOS Press: 99–108. дои : 10.3233/978-1-58603-925-7-99 . ISBN 978-1-58603-925-7 .
^ Виллемс, Дэйсел (24 июня 2016 г.). «О твердости головоломок с совпадением краев в рамке» (PDF) . Бакалаврская диссертация, факультет естественных наук, Амстердамский университет .
^ Перейти обратно: ^а ^б Верхаард, Луи. «EII Solver – Лучшие результаты» . кратчайший путь.se . Проверено 9 октября 2020 г.
^ http://www.sydsvenskan.se/2009-01-20/lundafamilj-bast-i-varlden-pa-svarknackt-pussel Ссылка на шведском языке.
^ «Вечность II» . Архивировано из оригинала (официального сайта) 8 февраля 2010 года . Проверено 30 января 2011 г.
^ «Описание метода решения Eternity I Селби и Риордана» . Алекс Селби (и Оливер Риордан) . 16 июня 2007 года . Проверено 16 июня 2007 г.
^ Перейти обратно: ^а ^б «1 миллион фунтов говорит о том, что это действительно самая сложная головоломка» . США: Вуд Трик. 4 апреля 2023 г. Проверено 4 апреля 2023 г.
^ « Страница «Решение» на веб-сайте Брендана Оуэна Eternity II» . Архивировано из оригинала 10 декабря 2007 года . Проверено 9 ноября 2007 г.
^ Эрик Д. Демейн , Мартин Л. Демейн . «Головоломки, сопоставление ребер и упаковка полимино: связи и сложность» (PDF) . Проверено 12 августа 2007 г.
^ «LGR – ТетраВекс и неразрешимая загадка» . 5 февраля 2016 г. Архивировано из оригинала 21 декабря 2021 г. – на YouTube.
^ Такенага, Ясухико; Уолш, Тоби (15 сентября 2006 г.). «Тетравекс NP-полный» . Письма об обработке информации . 99 (5): 171–174. дои : 10.1016/j.ipl.2006.04.010 . ISSN 0020-0190 . S2CID 7228681 .

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

Программное обеспечение:

[1] «Investegate | Объявления TOMY | TOMY: Глобальный запуск Eternity II в Hamleys за 2 доллара США…» Investegate.co.uk . Новостная лента по связям с общественностью. 26 июля 2007 года . Проверено 5 октября 2020 г.

[2] «Телевизионное интервью с Кристофером Монктоном и Бренданом Оуэном» . Утро с Керри-Энн, канал Брендана Оуэна, YouTube . 26 июля 2007 г. Архивировано из оригинала 21 декабря 2021 г.

[:0-3] Перейти обратно: ^а ^б Буклет с инструкцией (PDF, в архиве) , опубликован на официальном сайте.

[:2-4] Перейти обратно: ^а ^б Оуэн, Брендан (2007). «Вечность II – Дизайн» . Веб-сайт Брендана Оуэна Eternity II . Архивировано из оригинала 10 декабря 2007 года . Проверено 9 ноября 2007 г.

[5] Ансотеги, Карлос; Бежар, Рамон; Фернандес, Сезар; Матеу, Карлес (3 июля 2008 г.). «Насколько сложна коммерческая головоломка: вызов Eternity II» . Материалы конференции 2008 года по исследованиям и разработкам искусственного интеллекта: материалы 11-й Международной конференции Каталонской ассоциации искусственного интеллекта . НЛД: IOS Press: 99–108. дои : 10.3233/978-1-58603-925-7-99 . ISBN 978-1-58603-925-7 .

[6] Виллемс, Дэйсел (24 июня 2016 г.). «О твердости головоломок с совпадением краев в рамке» (PDF) . Бакалаврская диссертация, факультет естественных наук, Амстердамский университет .

[:1-7] Перейти обратно: ^а ^б Верхаард, Луи. «EII Solver – Лучшие результаты» . кратчайший путь.se . Проверено 9 октября 2020 г.

[8] ttp://www.sydsvenskan.se/2009-01-20/lundafamilj-bast-i-varlden-pa-svarknackt-pussel Ссылка на шведском языке.

[officialsite-9] «Вечность II» . Архивировано из оригинала (официального сайта) 8 февраля 2010 года . Проверено 30 января 2011 г.

[archduke061607-10] «Описание метода решения Eternity I Селби и Риордана» . Алекс Селби (и Оливер Риордан) . 16 июня 2007 года . Проверено 16 июня 2007 г.

[times2005-11] Перейти обратно: ^а ^б «1 миллион фунтов говорит о том, что это действительно самая сложная головоломка» . США: Вуд Трик. 4 апреля 2023 г. Проверено 4 апреля 2023 г.

[12] « Страница «Решение» на веб-сайте Брендана Оуэна Eternity II» . Архивировано из оригинала 10 декабря 2007 года . Проверено 9 ноября 2007 г.

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

[14] «LGR – ТетраВекс и неразрешимая загадка» . 5 февраля 2016 г. Архивировано из оригинала 21 декабря 2021 г. – на YouTube.

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]