Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Головоломка Eternity II (сокращенно E2 или E II) представляет собой ребро сопоставления головоломка запущен 28 июля 2007 года [1] [2] Он был разработан Кристофером Монктон и на рынке и защищены TOMY 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 граничных элементов (с одной серой стороной) и 14 2 = 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! × 4 256 , примерно 1,15 × 10 661 . Более точная верхняя граница возможного количества конфигураций может быть достигнута с учетом фиксированной детали в центре и ограничений, установленных для деталей по краю: 1 × 4! × 56! × 195! × 4 195 , примерно 1,12 × 10 557 . Дополнительную верхнюю границу можно получить, рассмотрев положение и ориентацию подсказок, полученных с помощью загадок. В этом случае положение и ориентация пяти фигур известны, что дает верхнюю границу 4! × 56! × 191! × 4 191 = 3,11 × 10 545, что дает пространство поиска в 3,70 × 10 115 раз меньше, чем в первом приближении.

В первом приближении ограничение соответствия кромок уменьшает количество допустимых конфигураций в (1/5) раз для каждой пары кромок и (1/17) для каждой внутренней пары кромок. В этом случае количество допустимых конфигураций приблизительно равно 4! × 56! × 196! × 4 196 × (1/5) 60 × (1/17) 420 ≈ 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 47 шагов. [12]

В 2005 году газета The Times цитирует Монктона :

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

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

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

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

  • Перси Александр МакМахон
  • Проблема выполнимости
  • Tetravex , подобное проще (не кусок вращения или пограничные части) край сопоставления игра - головоломка от Microsoft Entertainment пакета , [14] показано, что NP-полной . [15]
  • Ванга плитка

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

  1. ^ PRNewswire (26 июля 2007). «Investegate | Объявления TOMY | TOMY: Глобальный запуск Eternity II в Hamleys с 2 долл. США ...» www.investegate.co.uk . Дата обращения 5 октября 2020 .
  2. ^ "Телевизионное интервью с Кристофером Монктоном и Бренданом Оуэном" . Утро с Керри-Энн, канал Брендана Оуэна, YouTube . 26 июля 2007 г.
  3. ^ a b Брошюра с инструкциями (PDF, в архиве) , опубликованная на официальном сайте
  4. ^ a b Оуэн, Брендан (2007). «Вечность II - Дизайн» . Веб-сайт Брендана Оуэна Eternity II . Архивировано из оригинала 10 декабря 2007 года . Проверено 9 ноября 2007 года .
  5. ^ Ансотеги, Карлос; Бехар, Рамон; Фернандес, Сезар; Матеу, Карлес (3 июля 2008 г.). «Насколько сложна коммерческая головоломка: испытание Eternity II» . Материалы конференции 2008 г. по исследованиям и разработкам в области искусственного интеллекта: материалы 11-й Международной конференции Каталонской ассоциации искусственного интеллекта . NLD: IOS Press: 99–108. DOI : 10.3233 / 978-1-58603-925-7-99 . ISBN 978-1-58603-925-7.
  6. ^ Виллемс, Daysel (24 июня 2016). «О сложности головоломок с совпадающими краями в рамке» (PDF) . Бакалаврская диссертация, факультет естественных наук, Амстердамский университет .
  7. ^ a b Верхар, Луи. «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. ^ a b Эллиотт, Джон (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. DOI : 10.1016 / j.ipl.2006.04.010 . ISSN 0020-0190 . 

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

  • Официальный сайт (в архиве)
  • Флэш-демонстрация головоломки 4x4 с исходного (ныне несуществующего) веб-сайта
  • Визуализатор онлайн-решений
  • Дискуссионный форум Eternity II (Groups.io)
  • Описание Eternity II и обсуждение решателей
  • Описание решателя Eternity II Луи Верхаарда, используемого Анной Карлссон

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

  • Открытый исходный код Matlab Eternity II Solver
  • Программное обеспечение Eternity II Editor / Solver с открытым исходным кодом
  • Программное обеспечение Eternity II с открытым исходным кодом
  • E2Lab: Бесплатное программное обеспечение Eternity II Editor / Solver
  • E2Solver: программа для решения головоломок Eternity II с открытым исходным кодом
  • Android-приложение для головоломок типа Eternity II.
  • Приложение для iPhone и iPad для головоломок типа Eternity II.