Rompecabezas de la eternidad II

El rompecabezas Eternity II ( 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 registrado por TOMY UK Ltd como sucesor del rompecabezas Eternity original . El rompecabezas fue parte de una competencia en la que se ofreció un premio de $2 millones para la primera solución completa. La competencia finalizó al mediodía del 31 de diciembre de 2010, sin que se encontrara ninguna solució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, con la limitación de que los bordes adyacentes coincidan. Ha sido diseñado para que sea 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 (colectivamente llamados 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, salvo un número de identificación, y no se usa en el rompecabezas. Por lo tanto, cada pieza se puede usar 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 ("rombos") en el anillo más externo, es decir, entre las piezas del borde y las esquinas, mientras que los otros 17 se usan en los 420 pares de bordes "interiores" restantes. Los colores se usan de manera uniforme, con cada uno de los 5 colores del borde utilizados en exactamente 12 pares de bordes, y cada uno de los 17 colores interiores utilizados para 24 pares de bordes (5 colores) o 25 pares de bordes (12 colores). El número total de pares de bordes es 480. Uno de los cinco colores del 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 ² = 196 piezas interiores (con cuatro lados de color). Cada pieza tiene una disposición única de colores y ninguna de las piezas es simétrica rotacionalmente, por lo que cada una de las 256 × 4 = 1024 opciones de pieza y orientación da como resultado un patrón diferente de colores de borde.

El rompecabezas se diferencia del primer rompecabezas 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]

Con el lanzamiento del producto, se ofrecieron dos rompecabezas de pistas que, si se resuelven, dan 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: Clue Puzzle 3 de 36 piezas y Clue Puzzle 4 de 72 piezas. El libro de reglas establece que el rompecabezas se puede resolver sin usar las pistas. ^[3]

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 ²⁵⁶ , aproximadamente 1,15 × 10 ⁶⁶¹ . Se puede lograr un límite superior más estricto para el número posible de configuraciones teniendo en cuenta la pieza fija en el centro y las restricciones establecidas en las piezas en el borde: 1 × 4! × 56! × 195! × 4 ¹⁹⁵ , aproximadamente 1,12 × 10 ⁵⁵⁷ . 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 ¹⁹¹ = 3,11 × 10 ⁵⁴⁵ , lo que produce un espacio de búsqueda 3,70 × 10 ¹¹⁵ veces más pequeño que la primera aproximación.

En una primera aproximación, la restricción de coincidencia de aristas reduce el número de configuraciones válidas en un factor de (1/5) para cada par de aristas de borde y (1/17) para cada par de aristas internas. El número de configuraciones válidas se aproxima entonces a 4! × 56! × 196! × 4 ¹⁹⁶ × (1/5) ⁶⁰ × (1/17) ⁴²⁰ ≈ 16,4, que es muy cercano a 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 restricciones más estrictas disminuyen 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]

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. Se otorgó un premio de $10,000 a Louis Verhaard de Lund, Suecia, por una solución parcial ^[7] con 467 aristas coincidentes de 480. ^[8] Verhaard publicó tres soluciones parciales más con el mismo número de aristas coincidentes. ^[7]

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 la solución correcta del rompecabezas de Eternity II no ha sido reclamado". ^[9]

Nunca se ha publicado una solución completa y verificada del rompecabezas de Eternity 2. Esto incluye la solución propuesta por Christopher Monckton, que sigue sin publicarse. Se sabe que han circulado varias soluciones falsas en Internet.

El rompecabezas original Eternity era un rompecabezas de mosaicos con un premio de un millón de libras, creado por Monckton . Lanzado en junio de 1999, se resolvió mediante un algoritmo de búsqueda por computadora diseñado por Alex Selby y Oliver Riordan , que explotó las debilidades combinatorias del diseño del rompecabezas original. ^[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 de la eternidad original, tiene menos piezas de rompecabezas, 160 en comparación con 209 y 256 de los dos primeros rompecabezas de la eternidad respectivamente, y sin embargo, el Dilema del Diamante 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 posible de resolver. En particular, a diferencia del rompecabezas Eternity original, es probable que solo haya un número muy pequeño de posibles soluciones al problema. ^[4] Owen estima que una búsqueda de retroceso por fuerza bruta podría tomar alrededor de 2 × 10⁴⁷ pasos para completar. ^[12]

En 2005, The Times citó a Monckton diciendo:

"Nuestros cálculos indican que si se utilizara el ordenador más potente del mundo y se lo dejara funcionando desde ahora hasta el fin proyectado del universo, es posible que no se topara con ninguna de las soluciones". ^[11]

Aunque se ha demostrado que la clase de rompecabezas de coincidencia de aristas , 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 rompecabezas Eternity original era un caso especial.

Al igual que en el rompecabezas original de la Eternidad, 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 conduzca a una solución completa.

• TetraVex , un juego de rompecabezas de combinación de bordes similar y más simple (sin rotación de piezas ni piezas de borde) del Microsoft Entertainment Pack , ^[14] que ha demostrado ser NP-completo . ^[15]

• 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 los solucionadores
• Descripción del solucionador Eternity II de Louis Verhaard utilizado por Anna Karlsson

Software:

• Solucionador Matlab Eternity II de código abierto
• Software editor/solucionador de código abierto Eternity II
• Software de rompecabezas de código abierto Eternity II
• E2Lab: software gratuito de edición y resolución de problemas de Eternity II
• E2Solver: solucionador de rompecabezas de código abierto 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.