El rompecabezas Eternity II (abreviado E2 o E II) es un rompecabezas de combinación de bordes lanzado el 28 de julio de 2007. [1] [2] Fue desarrollado por Christopher Monckton y comercializado y protegido por derechos de autor por TOMY UK Ltd como sucesor del original Eternity. rompecabezas . El rompecabezas era parte de una competencia en la que se ofreció un premio de $ 2 millones por la primera solución completa. El concurso finalizó al mediodía del 31 de diciembre de 2010, sin que se haya encontrado ninguna solución.
Descripción
El rompecabezas Eternity II es un rompecabezas de combinación de bordes que implica colocar 256 piezas cuadradas en una cuadrícula de 16 × 16, restringida por el requisito de coincidir con los bordes adyacentes. Ha sido diseñado para ser difícil de resolver mediante una búsqueda informática de fuerza bruta.
Cada pieza del rompecabezas tiene sus bordes en un lado marcados con diferentes combinaciones de forma / color (llamados colectivamente aquí "colores"), cada uno de los cuales debe coincidir exactamente con su lado vecino en cada pieza adyacente cuando el rompecabezas esté completo. El otro lado de cada pieza está en blanco, aparte de un número de identificación, y no se usa en el rompecabezas. Por lo tanto, cada pieza se puede utilizar en solo 4 orientaciones. Hay 22 colores, sin incluir los bordes grises. Cinco de los colores se encuentran exclusivamente en los 60 pares de bordes ("diamantes") en el anillo más externo, es decir, entre el borde y las piezas de las esquinas, mientras que los otros 17 se utilizan en los 420 pares de bordes "interiores" restantes. Los colores se utilizan de manera uniforme, con cada uno de los 5 colores de borde utilizado en exactamente 12 pares de bordes, y cada uno de los 17 colores internos se utiliza para 24 pares de bordes (5 colores) o 25 pares de bordes (12 colores). El número total de pares de aristas es 480. Uno de los cinco colores de borde no se encuentra en ninguna pieza de esquina, mientras que los 17 colores internos se utilizan al menos una vez en una pieza de borde.
Hay 4 piezas de esquina (con dos lados grises), 56 piezas de borde (con un lado gris) y 14 2 = 196 piezas interiores (con cuatro lados de color). Cada pieza tiene una disposición de colores única, y ninguna de las piezas es rotacionalmente simétrica, por lo que cada una de las opciones de pieza y orientación de 256 × 4 = 1024 da como resultado un patrón diferente de colores de borde.
El rompecabezas se diferencia del primer rompecabezas de Eternity en que hay una pieza inicial no opcional (una pista obligatoria) que debe colocarse en una posición y orientación específicas cerca del centro del tablero. [3]
Dos acertijos de pistas estaban disponibles con el lanzamiento del producto, que, si se resuelven, cada uno da una posición de pieza (pista) en el rompecabezas principal de 256 piezas. Clue Puzzle 1 es un rompecabezas cuadrado de 36 piezas (6 × 6) y Clue Puzzle 2 es un rompecabezas rectangular de 72 piezas (12 × 6). En 2008 se pusieron a disposición dos rompecabezas de pistas adicionales de las mismas dimensiones: el Clue Puzzle 3 de 36 piezas y el Clue Puzzle 4 de 72 piezas. El libro de reglas establece que el rompecabezas se puede resolver sin usar las pistas. [3]
Complejidad
¡El número de configuraciones posibles para el rompecabezas Eternity II, asumiendo que todas las piezas son distintas e ignorando las piezas fijas con posiciones predeterminadas, es 256! × 4 256 , aproximadamente 1,15 × 10 661 . Se puede lograr un límite superior más ajustado al número posible de configuraciones teniendo en cuenta la pieza fija en el centro y las restricciones establecidas en las piezas del borde: ¡1 × 4! × 56! × 195! × 4 195 , aproximadamente 1,12 × 10 557 . Se puede obtener un límite superior adicional considerando la posición y orientación de las piezas de pista obtenidas a través de los rompecabezas de pistas. En este caso, se conoce la posición y orientación de cinco piezas, ¡lo que da un límite superior de 4! × 56! × 191! × 4 191 = 3,11 × 10 545 , lo que arroja un espacio de búsqueda 3,70 × 10 115 veces más pequeño que la primera aproximación.
Para una primera aproximación, la restricción de coincidencia de bordes reduce el número de configuraciones válidas en un factor de (1/5) para cada par de bordes de bordes y (1/17) para cada par de bordes internos. ¡El número de configuraciones válidas se aproxima entonces a 4! × 56! × 196! × 4 196 × (1/5) 60 × (1/17) 420 ≈ 16,4, que está muy cerca de la unidad. Esto indica que es probable que el rompecabezas haya sido diseñado para tener solo una o unas pocas soluciones, [4] [5] lo que maximiza la dificultad: más soluciones (restricciones más flexibles, por ejemplo, menos colores) facilitarían la búsqueda de una solución (una de muchas ), mientras que las restricciones más estrictas reducen el espacio de búsqueda, lo que facilita la localización de la solución (única). La optimización del número de colores se ha investigado empíricamente para rompecabezas más pequeños, lo que confirma esta observación. [6]
Competencia y solución
Después de la primera fecha de escrutinio el 31 de diciembre de 2008, se anunció que no se había encontrado una solución completa. Louis Verhaard de Lund en Suecia recibió un premio de $ 10,000 por una solución parcial [7] con 467 bordes coincidentes de 480. [8] Verhaard publicó tres soluciones parciales más con el mismo número de bordes coincidentes. [7]
Desde el 30 de enero de 2011, el sitio oficial de Eternity II anuncia que "La fecha final para la solución correcta del rompecabezas de Eternity II pasa sin un ganador, y el premio de $ 2 millones por una solución correcta del rompecabezas de Eternity II no se reclama". [9]
Nunca se ha publicado una solución completa verificada para el rompecabezas de Eternity 2. Esto incluye la solución prevista de Christopher Monckton, que permanece inédita. Se sabe que han circulado en línea varias soluciones falsas.
Historia y diseño
El rompecabezas original de Eternity era un rompecabezas de mosaico con un premio de un millón de libras , creado por Monckton . Lanzado en junio de 1999, fue resuelto por un algoritmo de búsqueda por computadora diseñado por Alex Selby y Oliver Riordan , que explotó las debilidades combinatorias del diseño original del rompecabezas. [10] El dinero del premio se pagó en su totalidad a Selby y Riordan.
Un rompecabezas con sorprendentes similitudes con ambos rompecabezas de la eternidad, el Dilema del Diamante, con fecha límite en 1990, 10 años antes de la fecha límite del rompecabezas original de la eternidad, tiene menos piezas del rompecabezas, 160 en comparación con 209 y 256 para los dos primeros rompecabezas de la eternidad respectivamente. y, sin embargo, Diamond Dilemma aún no se ha resuelto en más de 25 años.
El rompecabezas Eternity II fue diseñado por Monckton en 2005, esta vez en colaboración con Selby y Riordan, quienes diseñaron un programa de computadora que generó el diseño final de Eternity II. [11] Según el entusiasta de los juegos matemáticos Brendan Owen, el rompecabezas Eternity II parece haber sido diseñado para evitar los defectos combinatorios del rompecabezas anterior, con parámetros de diseño que parecen haber sido elegidos para hacer que el rompecabezas sea lo más difícil de resolver posible. . En particular, a diferencia del rompecabezas original de la eternidad, es probable que solo haya una pequeña cantidad de posibles soluciones al problema. [4] Owen estima que una búsqueda de retroceso por fuerza bruta podría tomar alrededor de 2 × 10 47 pasos para completarse. [12]
Monckton fue citado por The Times en 2005 diciendo:
- "Nuestros cálculos son que si usas la computadora más poderosa del mundo y la dejas funcionar desde ahora hasta el fin proyectado del universo, es posible que no tropiece con una de las soluciones". [11]
Aunque se ha demostrado que la clase de rompecabezas de emparejamiento de bordes , de los cuales Eternity II es un caso especial, es en general NP-completo , [13] lo mismo puede decirse de la clase general de problemas de empaquetamiento de polígonos, de los cuales el El rompecabezas original de la eternidad era un caso especial.
Al igual que el rompecabezas original de Eternity, es fácil encontrar un gran número de formas de colocar una cantidad sustancial de piezas en el tablero cuyos bordes coincidan, lo que hace que parezca que el rompecabezas es fácil. Sin embargo, dado el bajo número esperado de posibles soluciones, es presumiblemente astronómicamente improbable que cualquier solución parcial dada conduzca a una solución completa.
Ver también
- Percy Alexander MacMahon
- Problema de satisfacción
- TetraVex , un juego de rompecabezas de combinación de bordes similar más simple (sin rotación de piezas ni piezas de borde) del Microsoft Entertainment Pack , [14] demostrado ser NP-completo . [15]
- Baldosa Wang
Referencias
- ^ PRNewswire (26 de julio de 2007). "Investegate | TOMY Announcements | TOMY: Lanzamiento global de Eternity II en Hamleys con US $ 2 ..." www.investegate.co.uk . Consultado el 5 de octubre de 2020 .
- ^ "Entrevista televisiva con Christopher Monckton y Brendan Owen" . Mañanas con Kerri-Anne, canal de Brendan Owen, YouTube . 26 de julio de 2007.
- ^ a b Folleto de instrucciones (PDF, archivado) , publicado en el sitio web oficial
- ^ a b Owen, Brendan (2007). "Eternidad II - Diseño" . Sitio web Eternity II de Brendan Owen . Archivado desde el original el 10 de diciembre de 2007 . Consultado el 9 de noviembre de 2007 .
- ^ Ansótegui, Carlos; Béjar, Ramon; Fernández, Cèsar; Mateu, Carles (3 de julio de 2008). "Qué tan difícil es un rompecabezas comercial: el desafío Eternity II" . Actas de la conferencia 2008 sobre Investigación y Desarrollo de la Inteligencia Artificial: Actas de la XI Conferencia Internacional de la Asociación Catalana de Inteligencia Artificial . NLD: IOS Press: 99–108. doi : 10.3233 / 978-1-58603-925-7-99 . ISBN 978-1-58603-925-7.
- ^ Willems, Daysel (24 de junio de 2016). "Sobre la dureza de los rompecabezas enmarcados de combinación de bordes" (PDF) . Tesis de Licenciatura, Facultad de Ciencias, Universidad de Amsterdam .
- ^ a b Verhaard, Louis. "EII Solver - Mejores resultados" . www.shortestpath.se . Consultado el 9 de octubre de 2020 .
- ^ http://www.sydsvenskan.se/2009-01-20/lundafamilj-bast-i-varlden-pa-svarknackt-pussel Enlace en sueco
- ^ "Eternidad II" . Archivado desde el original (sitio web oficial) el 8 de febrero de 2010 . Consultado el 30 de enero de 2011 .
- ^ "Descripción del método de resolución Eternity I de Selby y Riordan" . Alex Selby (y Oliver Riordan) . 16 de junio de 2007 . Consultado el 16 de junio de 2007 .
- ^ a b Elliott, John (4 de diciembre de 2005). "£ 1 millón dice que este es realmente el rompecabezas más difícil" . Londres: Times Online . Consultado el 9 de noviembre de 2007 .
- ^ " Página " Resolver "en el sitio web de Brendan Owen's Eternity II" . Archivado desde el original el 10 de diciembre de 2007 . Consultado el 9 de noviembre de 2007 .
- ^ Erik D. Demaine , Martin L. Demaine . "Rompecabezas, emparejamiento de bordes y embalaje Polyomino: conexiones y complejidad" (PDF) . Consultado el 12 de agosto de 2007 .
- ^ "LGR - TetraVex y el rompecabezas sin solución" . YouTube . 5 de febrero de 2016.
- ^ Takenaga, Yasuhiko; Walsh, Toby (15 de septiembre de 2006). "Tetravex es NP-completo" . Cartas de procesamiento de información . 99 (5): 171-174. doi : 10.1016 / j.ipl.2006.04.010 . ISSN 0020-0190 .
enlaces externos
- Sitio web oficial (archivado)
- Demostración en flash de un rompecabezas 4x4 del sitio web original (ahora desaparecido)
- Visualizador de soluciones en línea
- Foro de discusión de Eternity II (Groups.io)
- Descripción de Eternity II y discusión de solucionadores
- Descripción del solucionador Eternity II de Louis Verhaard utilizado por Anna Karlsson
Software:
- Solucionador de código abierto Matlab Eternity II
- Software editor / solucionador de código abierto Eternity II
- Software de rompecabezas Open Source Eternity II
- E2Lab: software gratuito Eternity II Editor / Solver
- E2Solver: solucionador de acertijos de Open Source Eternity II
- Aplicación de Android para rompecabezas de combinación de bordes tipo Eternity II.
- Aplicación para iPhone y iPad para rompecabezas de combinación de bordes tipo Eternity II.