Eternity era un puzzle de 209 piezas planas al estilo tradicional, que se vendía en las tiendas y con el que había que construir un gigantesco dodecágono.
Su autor, Christopher Monckton, ofreció en 1999 un premio de un millón de libras (unos dos millones de dólares) a quien encontrara la solución. Fue uno de los puzzles más exitosos en el Reino Unido ese año y superó el medio millón de unidades vendidas, a 35 libras cada uno. En mayo de 2000, casi cuando se iba a complir la fecha límite del concurso, un par de matemáticos de Cambridge enviaron la solución y ganaron el premio.
Se creía que Eternity era realmente difícil de analizar y resolver incluso por «fuerza bruta» con la ayuda de un ordenador y que había, según los expertos, no menos de 1095 combinaciones, hasta 10500 según otros. Alex Selby y Oliver Riordan emplearon ingeniosas ideas y técnicas para reducir las posiciones a estudiar y con la ayuda de un ordenador probaron todos los posicionamientos y giros posibles de las piezas en las «fases finales» de la construcción del puzzle hasta que dieron con la solución. Por suerte Monckton, su creador, había contratado un seguro para esta eventualidad y pagó el premio sin problemas.
Curiosamente, apareció una segunda solución que encontró Guenter Stertenbrink por otro sistema. Ninguna de las dos que se conocen empleaba las seis «pistas» que el creador del puzzle fue publicando para ayudar a los aficionados. Hay una explicación completísima y detallada de Alex Selvy sobre cómo afrontaron el problema y encontraron la solución en Notes from a talk on solving Eternity.
Eternity II
Este próximo verano, en julio, verá la luz Eternity II, una nueva versión del puzzle, del mismo creador y con un premio de dos millones de dólares (millón y medio de euros) para la primera persona que lo resuelva.
Mientras los aficionados a los rompecabezas afinan sus garras y los matemáticos y programadores preparan sus algoritmos y programas para atacar a la nueva bestia, esto es lo que se sabe o se «intuye» sobre esta nueva versión de Eternity, en base a la nota de prensa oficial, la foto y la web oficial:
- Eternity II es un puzzle plano de 256 piezas cuadradas que encajan en un tablero cuadrado de 16×16 casillas.
- Cada pieza tiene bordes coloreados con ciertos patrones que seguramente hay que hacer coincidir. Además de reglas sobre los colores (parece que hay ocho colores posibles) probablemente también habrá ciertas reglas que cumplir para que encajen «legalmente» unas piezas con otras.
- Parece que todas las piezas son distintas y que tienen una sola cara.
- La solución es única.
- El precio de Eternity II será de 35 libras (~ 53 euros).
- Habrá algunos puzzles extra a modo de «pistas».
- Parece fácil (especialmente simularlo en un ordenador), pero seguro que no es tan fácil…
- Yo voy a pedirme uno en cuanto se pueda ;-)
Un cálculo rápido de servilleta sobre un ataque por «fuerza bruta»: las 256 piezas del puzzle tienen todas la misma forma cuadrada (y parecen todas diferentes), de modo que podrían colocarse de 256! (factorial de 256) formas distintas sobre las casillas del tablero. Eso es un número de más de 500 cifras, aproximadamente 10507. Esas combinaciones habría que multiplicarlas por los cuatro giros posibles por cada una de las 256 piezas cuadradas, es decir 4256 variaciones más (eso equivale más o menos a 10154). Multiplicando ambos números, la cifra total indica que existirían unas 10661 formas de colocar y girar las piezas (un poco menos si se ignoran giros del tablero en su conjunto). Naturalmente, las reglas del puzzle sobre cómo colocar las piezas de forma válida no permitirán la mayoría de esas posiciones, dado que la solución es única.
Comparativamente, incluso si fuera un puzzle tan pequeño como 2×2 cuadraditos, habría (4! × 44) = 6144 formas posibles de situarlas y girarlas (o bien 1536 sin contar giros del tablero completo); para un puzzle similar de 4×4 ya habría hasta 1023 permutaciones totales de piezas y giros.
[Si hay algún matemático en la sala y puede comprobar estos cálculos, que son aproximados, se lo agradeceré.]
Si se programa un ordenador para comprobar todo esto pieza a pieza, parece claro que necesitará bastante tiempo… ¡Una eternidad!
(Vía puzzlinks.com; también hay información en Su.doku.es)
Actualización: Ernesto ha comprobado con Mathematica los factoriales y potencias y los he corregido por mejores aproximaciones. (¡Gracias!) Más: Elías nos envió una referencia a las Wang Tiles (Dominós de Wang), otras curiosas bestias matemáticas que datan de 1961 y que encierran otros misterios complejos, relacionados con cubrir un plano siguiendo ciertas reglas, además de que pueden usarse para computar al estilo de las máquinas de Turing. Esas piezas son parecidas a las de Eternity II pero también muy distintas: no se pueden girar; el problema matemático se refiere a un tablero infinito y a determinar si un conjunto de dominós concreto puede «rellenarlo» o no, ya sea de forma periódica o aperiódica.
Más números (27 de enero de 2007): Casualmente terminé hoy de leer sobre Deep Blue que era el ordenador de IBM dedicado a jugar al ajedrez, con mútiples procesadores masivos paralelos y chips especializados en generación de «posiciones del tablero», algo parecido a lo que aquí serían las posiciones «posibles» del puzzle. Se me ocurrió calcular qué pasaría si Deep Blue intentara analizar el puzzle por fuerza bruta. Ese ordenador era capaz de calcular unos 200 millones de posiciones por segundo en 1997. Supongamos que en 2007 su potencia se ha ido duplicando cada año, de modo que ahora serían unas magníficas 200.000 millones de posiciones por segundo. Multiplicando eso por los segundos que hay en un año resulta que podría calcular unas 1013 posiciones distintas en doce meses funcionando de forma ininterrumpida. ¡Pero Eternity 2 tiene ni más ni menos que 10661 posiciones posibles! Incluso suponiendo que la simplicidad de ese puzzle hiciera un millón de veces más fácil calcular las posiciones que en ajedrez esa poderosa máquina sólo podría comprobar unas 1019 posiciones – lo cual sigue tremendamente lejos de las 10661 posiciones posibles, tan lejos, tan lejos como el cero del infinito prácticamente. Curiosamente, 4,3x1019 es el número de posiciones posibles de un cubo de Rubik, así que se podría estimar que aunque esa bestia imaginaria podría resolver un cubo en unos cuatro años simplemente «girándolo al azar» (lo cual se consideraría de otro modo imposible, aparte de carente de practicidad). Pero seguiría «eternamente» lejos de solucionar el Eternity II. Ni aunque cada ordenador conectado a Internet fuera un Deep Blue moderno dedicado a la tarea se avanzaría mucho: con 100 millones de máquinas se examinarían 1027 posiciones únicamente. Definitivamente, la fuerza bruta no sirve aquí. El ataque a la solución del puzzle requerirá por tanto examinar técnicas e ideas que simplifiquen el número de posiciones posibles y la forma de examinarlas, del mismo modo que los ordenadores resuelven cubos de Rubik o juegan al ajedrez, en cuestión de segundos.
Si se mira de otro modo: existen puzzles convencionales con dibujos de 1.000, 5.000, 10.000 piezas e incluso más. También cada pieza puede ir teóricamente en cualquier posición y girarse de cuatro formas distintas. ¡Las posibles combinaciones son incluso más que aquí! Pero la gente resuelve esos puzzsles en cuestión de días, gracias a que hay excepciones obvias (las piezas de lados rectos van en los bordes, ciertas formas sólo encajan con ciertas otras, etc.) pero sobre todo, hay patrones visuales que reducen las zonas: «lo blanco con lo blanco, lo verde con lo verde». No está claro cuánto de excepciones y patrones va a haber en Eternity II, pero va a ser una de las claves sin duda.
Más: En el grupo de Yahoo Eternity II ya se está trabajando sobre el Puzzle, teorías sobre cómo va a ser, lo que se ve en las fotos (incluyendo algunas unas piezas… triangulares, WTF! ¿falsa? casi seguro), código para generar puzzles similares, de todo… en fin: ¡dos millones de dólares atraen a mucha gente!
Actualización (27 de julio de 2007): Eternity II ya está a la venta.
