Загадка Вечности II - Eternity II puzzle

"E II" перенаправляется сюда. Для использования в других целях см. EII (значения).
Загадка Вечности II

В Загадка Вечности II (сокращенно E2 или же E II) является головоломка с подбором краев запущен 28 июля 2007 г.[1][2] Он был разработан Кристофер Монктон и продается и охраняется авторским правом Томи UK Ltd как преемник оригинального Загадка вечности. Головоломка была частью конкуренция в котором за первое полное решение был предложен приз в размере 2 миллионов долларов. Конкурс завершился в полдень 31 декабря 2010 г., и решения не было найдено.

Описание

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

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

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

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

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

Сложность

Количество возможных конфигураций для головоломки Eternity II, если предположить, что все части различны и игнорировать фиксированные части с заранее определенными положениями, составляет 256! × 4256, примерно 1,15 × 10661. Более точная верхняя граница возможного количества конфигураций может быть достигнута с учетом фиксированной детали в центре и ограничений, установленных для деталей по краю: 1 × 4! × 56! × 195! × 4195, примерно 1,12 × 10557. Дальнейшую верхнюю границу можно получить, рассматривая положение и ориентацию подсказок, полученных с помощью загадок. В этом случае положение и ориентация пяти фигур известны, что дает верхнюю границу 4! × 56! × 191! × 4191 = 3.11 × 10545, что дает пространство поиска 3.70 × 10115 раз меньше, чем в первом приближении.

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

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

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

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

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

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

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

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

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

Монктона цитирует Времена в 2005 году, как говорится:

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

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

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

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

Рекомендации

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

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

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