Ir al contenido principal

El Puzzle Interminable

Era verano del 2007 cuando navegando entre locuras por Yonkis.com me encontré una entrada que anunciaba un puzzle en el cual se podían ganar 2.000.000$ para la primera persona que lo resolviera. 

Como soy adicto a comerme la cabeza simplemente por entretenimiento y en esta ocasión había una suculenta recompensa de $2m realicé un repentino cambio de verbo pasando de mirar cocos a romperme el coco en un periquete. 

Yonkis.com enlazaba a Microsiervos.com y fue allí donde obtuve la primera información sobre este puzzle cuyo nombre es Eternity II, un juego comercializado por Tomy.

Lanzamiento (julio 2007)

Gracias a Microsiervos me puse al día en la historia de este puzzle enterándome de que ya había existido un puzzle precursor llamado Eternity del mismo creador Christopher Monckton. 

El puzzle Eternity II es tan fácil de entender como difícil de resolver, muy resumido consiste en un tablero de 16 por 16 casillas en las cuales hay que colocar las 256 piezas de forma que los 4 lados de cada una de las piezas coincidan en su dibujo con el de sus piezas adyacentes, en total son 480 lados a emparejar. -Sencillo, sólo algo más complejo que enlazar todas las piezas del domi...nó ¿no? -No.

Quedaba poco más de un mes para su lanzamiento, me puse a analizar la forma de resolverlo, deducir algunas estrategias probando una versión reducida del mismo que estaba disponible en la web oficial de Eternity II que pusieron a modo de Demo para mostrar cual sería el funcionamiento del puzzle. 

Tras unos cuantos folios con ideas y garabatos, unas cuantas horas de análisis, me puse a implementar un programa que intentase resolverlo. Unas semanas después ya salió a la venta y lo compré, he aquí una foto del susodicho.


Primer escrutinio (diciembre 2008)

Durante ese año, y como ya habían publicado desde sus inicios en las instrucciones del concurso, pusieron a la venta dos puzzles pista (Pista 1 y 2), los cuales eran del estilo Eternity II pero más pequeños y muchísimo más fáciles de resolver, una vez los resolvías y enviabas la solución, por cada puzzle pista te suministraban la posición correcta de una de las piezas del Eternity II.

Analicé la opción de desarrollar un programa multi-hilo (multithread) para dividir el trabajo y aprovechar el número de cores de los procesadores actuales, pero en este tipo de problemas no es fácil dividirlo ni tiene porqué ser más ventajoso, así que opté por un programa monohilo pero pensado para poder ejecutar varias instancias del mismo simultáneamente y configurados con distintas zonas de exploración. 

Al final de este apartado dejo una imagen de la última versión del software donde ha resuelto ambos puzzles pista de forma instantánea, uno en 0 y el otro en 32 milisegundos, a mano se pueden resolver en pocas horas.

A finales del año hubo el primer escrutinio y nadie había conseguido resolver Eternity II pero entregaron un premio (de consolación y motivación) no anunciado previamente de 10.000$ al que había enviado la solución con más lados emparejados.


Segundo escrutinio (diciembre 2009)

Al no haber sido resuelto, el concurso se prorrogaba un año más. Lo había dejado bastante abandonado a mitad del año anterior (muchas horas ya dedicadas) pero al conocer que nadie lo había conseguido me animé a rehacer una nueva versión muy mejorada y mucho más configurable del programa. 

Buscando algún socio intenté motivar a gente para que se apuntase a resolverlo pero no pasaron de unas semanas de calentón y lo dejaron, eso los pocos que lo empezaron. Sólo mi hermano desde el principio se apuntó al reto conmigo, colaborando con ideas, testeando el software, y probando diferentes configuraciones.

Durante este año salieron a la venta los puzzle pista 3 y 4, los cuales ya no se distribuyeron a España, y tras varios intentos fallidos de adquirirlos contacté con un paisano vía el grupo Eternity 2 de Yahoo, un tipo majo que me envió por mail las soluciones, las cuales él tuvo que pagar por ellas y comprarlas en eBay (mercado negro) por la misma razón de no poder conseguir estos puzzles de forma legal. 

A partir de este momento disponía de 5 piezas en su posición correcta (4 de las pistas + 1 que venía impuesta en el juego) de las 256 piezas totales y el (d)efecto de pensar que ahora era más fácil resolverlo. 

En este segundo escrutinio a finales del 2009 tampoco nadie había conseguido resolverlo, esto suponía un año más, el último, de prórroga para conseguirlo.

Tercer escrutinio (diciembre 2010)

Comparando mis resultados con otros, pienso que desarrollé un buen software a pesar de que usé mucho de lo que no aprendí en la universidad, mucho de lo que no debe hacer un buen programador, y cualquier otra cosa necesaria para conseguir la máxima velocidad de cálculo. 

El algoritmo se basa en un backtracking iterativo sin usar recursividad; con el mayor número de información y casos posibles precalculados una única vez al iniciarse; eliminando al máximo llamadas a funciones; simplificando las comprobaciones a realizar en cada nodo; reduciendo el número de ramas a explorar y detectando rápidamente las ramas sin solución.

En definitiva, un intento de solución por fuerza bruta “inteligente”, reducida y optimizada. En la primera versión que ejecuté tenía un rendimiento de 12.000 piezas/segundo y en la última versión (muchas horas de programación y pruebas después) de más de 14.000.000 piezas/segundo. 

Un poco más abajo veréis una captura del programa intentando encontrar la solución para Eternity II después de tan sólo 2 minutos en funcionamiento.

Lo que sí está claro es que conseguí lo mismo que cualquier persona de este planeta que lo intentó resolver, no conseguirlo. 

A principios de este presente año, 2011, después del último escrutinio anunciaron que el premio quedaba desierto y el concurso finalizado. La polémica de este eterno puzzle es que no han querido mostrar la solución.


Eternity II en 2022

Estamos en 2022, han pasado 15 años del lanzamiento del puzzle y nadie en el mundo lo ha resuelto. Aunque el concurso se cerró hace 11 años y ya no hay la recompensa del premio, hay gente que sigue intentando resolverlo. 

Yo mismo sigo con el gusanillo aunque no le dedico tiempo. Eso sí en cada PC nuevo que monto, pruebo de ejecutar mi software para ver cuánto ha mejorado la potencia de cálculo. Y a veces me entretengo a probar alguna configuración y dejarlo correr unas horas.

Final

Esta entrada es casi tan eterna como el puzzle en cuestión, pero mi capacidad de síntesis no ha podido comprimir más la historia interminable de Eternity II, que duró más de 3 años y medio en mi vida. 

Si lo has leído entero deja constancia en un comentario, para que pueda ascender tu rango en el blog de castigado a castigado Eterno.

------------

Para recibir avisos de los nuevos Castigos SUBSCRÍBETE POR EMAIL

Youtube: @disfrutadelcastigo

Comentarios

  1. Sólo puedo decir que el programa que hiciste hundía en la miseria en rendimiento a los de los demás que lo intentaron. Entre ellos yo!
    Great Job!

    Saludos!

    ResponderEliminar
  2. Bonito resumen de lo que yo vendría a llamar "el timo de la estampita" del siglo XXI jeje...Es broma, además ya sabes que yo no soy el más indicado para hablar después de mis fracasos buscando el santo grial de las quinielas de fútbol, de las casas de apuestas y últimamente de la inversión en bolsa.

    Tu y yo sabemos que lo importante es participar...por la recompensa en metálico.

    ResponderEliminar
  3. Lo he leido entero y me has dejado ojiplatico amigo. O_o

    ResponderEliminar
  4. Yo también lo he leido, aunque no estoy segura de haberlo entendido. Soy una auténtica masoca!!!
    Me acordaba de la historia y quería conocer el final.
    Que pena!!!! y que rabia no encontrar la solución, no?
    Ánimo con el Eternity III ;)

    ResponderEliminar
  5. Menudo parra estás hecho!!!!

    ¿¿¿Por que no hiciste un programa que calculara los números que van a salir en la primitiva???

    Es mucho mas fácil y puedes ganar mucho mas dinero.

    ¿No te equivocarías pensando que el Eternity tiene rodillos que giran ,verdad? xDDDD

    Un abrazo.

    ResponderEliminar
  6. Puni yo no me levanto de la cama para montar un friki puzzle por 2 milloncejos, casí que me quedo con las patas "pa arriba" rascandome la barriga, así te lo digo!!

    Tontas a parte eres en un ser especial, y friki como pocos...vamos como yo!

    Sigue castigandonos por favor que somos masocas totales.

    ResponderEliminar
  7. @Parasito Gracias! Aunque creo que había varios con buenos programas, mejores o peores es difícil saberlo. Lo más importante era intentarlo como hiciste tú, yo y muchos otros. Recuerdo que intentabas contactar conmigo por el puzzle y al final fue por Youtube. :)

    @Javier Los del primer Eternity también fueron unos timados pero se embolsaron el premio de $1m en 6 meses! Y por eso en este se les ha ido la mano en la complejidad. Al resto de tu comentario: LOOOOOL

    @Pi jajaja, también te he dejado casi sin palabras por el tamaño (no importa) del comment!? ;)

    @Lorena A ti te ofrecí ser socia y sólo se lo proponía a gente inteligente. Este peloteo es para que te animes si hay Eternity III!

    @KIT-KAT Con un software no puedo hacer lo que propones de la Primitiva, tendría que crear un hardware... llamado Máquina del tiempo y es todavía más complejo que el puzzle! ;)

    @JaviG jajaja por 2 milloncejos de nada que además eran en dólares y brutos para que mover un dedo no? Aprecio que aprecies los posts al precio recio... y buen apreciador será. buff

    ResponderEliminar
  8. Uff !!! Yo creo que eso no tenia solución pero aun así vaya currada para poder acabarlo
    , acabarías viendo piezas del puzzle por todos los sitios.

    ResponderEliminar
  9. Eres un fiera, por cierto.. no se si te lo habia dicho, eres un fiera jajaj

    el problema de no poder resolverlo con el programa que diseñaste cual es exactamente? que no tienes hardware suficiente para tanto calculo?

    ultimamente se usa un algoritmo (hay varios en realidad) para sacar por fuerza bruta el codigo de liberacion de la serie SL3 de nokia. Lo que se usa para ello es un quad crossfire de 5970 (ahora de 6990, pero va mal por los drivers) que a dia de hoy es lo mas potente para estos menesteres en relacion potencia/coste.

    A lo mejor podias adaptar el software para usar los procesadores graficos. incluso, es posible q nos llevemos una sorpresa...

    ResponderEliminar
  10. @Fernando Yo pienso que sí tiene solución de todas formas deberían haberla mostrado para despejar dudas. Jeje sí más de una vez tuve pesadillas con las piezas, y alguna vez levantarme de madrugada para escribir una idea.

    @Rafa El problema es que no tenía HW para resolverlo en un tiempo finito, ni seguramente con todos los ordenadores del planeta trabajando! Hubo un tío que hizo su soft para computación distribuida (repartía el premio al 50% con el ordenador que encontrase la solución) y nada, unos cuantos había conectados y no consiguió ni el récord de lados emparejados.

    Sobre el tema de usar las gráficas, sí se me pasó por la cabeza hacer una versión del programa para GPGPU pero por aquellos tiempos tanto Stream de ATI, como CUDA de nVIDIA estaban algo verdes, y OpenCL ni existía. Ahora hay APIs para facilitar la programación para GPGPU, antes era muy rudimentario y si sumamos que no tenía experiencia en esa programación lo descarté.

    De todas formas no tengo claro que el rendimiento final en GPGPU fuera muy bueno por el tipo de problema que es el puzzle. El uso óptimo de un algoritmo usando el HW gráfico son problemas muy paralelizables, divisibles en subproblemas independientes, y con estructuras de datos no muy complejas. El problema del Eternity II es opuesto a todo esto.

    ResponderEliminar
  11. no tengo ni idea del tema la verdad, no se que diferencia hay entre ambos procesadores (cpu y gpu)

    como ultimamente se hace esto q comentaba con las gpus por eso lo comente, pero veo q lo tienes superado :D

    yo de programacion lo justo, tengo un ciclo superior de diseño de aplicaciones.. vamos, que apenas se programar. Encima mi tiempo es limitadisimo y lo q me sobra lo empleo en otros asuntos :D

    ResponderEliminar
  12. Bueno ya imaginas que el diseño de ambos (CPU y GPU) es muy distinto por estar orientados a tareas muy distintas. De todas formas ya es correcto lo que dices de la tendencia de usar la GPU como procesador de uso general, y sobretodo para una serie de tareas específicas y cálculos es sin duda mucho más idónea y potente que la CPU; como por ejemplo el caso que has citado de fuerza bruta para reventar una clave.

    El tiempo muy limitado es un familiar mío también. ;)


    Por cierto quién quiera probar el puzzle en la web de Tomy sigue estando la Demo con el tablero de 4x4. Una vez pilléis como funciona no debería llevaros más de 3 minutos en resolverlo.
    http://www.tomy.co.uk/playzone/eternityii/

    ResponderEliminar
  13. Hi.He estado leyendo sobre el puzzle. En un segundo mi mente, ludópata de nacimiento, ha fotografíado tablero y piezas. Más de matemáticas que de máquinas empiezo a pensar en permutaciones, muchas, tantas como pasta me gustaría tener. A ver si me regalo tiempo y lo pruebo. Si no lo con/seguimos ¿tendremos premio de consolación?. Que ganas! Por cierto, gracias por tus desinteresados pero interesantes castigos. Ibas para teleformador...

    ResponderEliminar
  14. @Yoflu el concurso está cerrado pero el honor de resolverlo sigue abierto. Anímate con las permutaciones y perturbaciones mentales a ver si consigues algo. Los 2 milloncejos eran lo de menos lo interesante es el reto ¬¬
    Iba para teleformador y he llegado a túdeformador.

    ResponderEliminar
  15. Em trec el barret davant el repte que has portat a terme. Només en el planteig que has fet, ja proporciona un gran creixement intel·lectual i personal.

    Per la meva banda, jo tinc altres puzzles x resoldre...

    ResponderEliminar
  16. @Hanimal Gracias! La verdad que fue un reto muy interesante y divertido; siempre me quedará la espina de no haberlo resuelto pero el orgullo de haberlo intentado ;)
    Si sale el Eternity III anímate!

    ResponderEliminar
  17. Impresinante la capacidad de adaptacion que demostraste, lastima que no hallars la solución.
    Mira el lado bueno, hay que tener alguna derrota para saborear las victorias.

    ResponderEliminar
  18. tclever Fue una experiencia muy divertida, ordeñar las neuronas para intentar sacar lo máximo.

    El consuelo es que nadie en el mundo lo ha resuelto, todavía hay gente intentándolo, y yo sigo con ese gusanillo pero no gastaré más horas, ya fueron muchas. Si sale un Eternity III quizás vuelva a las andadas.

    Lo peor de no haberlo resuelto no son los 2 millones de dolares que no gané sino el orgullo, el orgullo de poder haberme jubilado joven. ;)

    ResponderEliminar
  19. Coincido en todo lo que dices, yo no entiendo de programas ni calculos, solo se que aun ahora enero 2012 sigo intentandolo, llego como muestra la imagen a 3 lineas del final y ahi quedo. Me llama mucho la atencion que no muestren la solucion final, eso no habla bien de todo esto no?. por lo pronto sigo intentandolo, y esperando el eternity III si es que lo habrá....

    ResponderEliminar
    Respuestas
    1. ¿Entonces lo estás intentando resolver a mano?
      Eres como yo de los que estás con el puzzle desde sus inicios o lo descubriste tiempo después?

      Yo le he dedicado muchas horas como intento explicar y transmitir en este post pero ya lo he abandonado de forma activa, aunque la espina clavada sigue allí. Cada vez que renuevo el PC pruebo ejecutar mi programa para resolver Eternity II, sólo para ver el aumento de velocidad de cálculo, en el reciente PC lo tengo pendiente, pero lo dejo sólo un rato como puro benchmark.

      Es muy sucio que no hayan mostrado la solución, a mí me ha enfadado bastante, pienso que sí tiene solución y no se trata de una estafa, pero aún así quiero verla, el concurso finalizó, y debían mostrarla. Nada de milongas que si sacarán una versión electrónica del mismo y por eso no la muestran, esto era un concurso y terminó, ahora deberían demostrar su solución.

      Tengo ganas de un posible Eternity III pero la forma en que han cerrado este me motivaría a no comprarles un sucesor.

      Eliminar
    2. Amigo, he echado una buena carcajada cuando leí "Tras unos cuantos folios con ideas y garabatos, unas cuantas horas de análisis, me puse a implementar un programa que intentase resolverlo". Esto fue leyendo me imaginé que comenzarías a resolverlo normalmente, y jamás se me pasé por la mente que harías un programa. :D. Cuando disponga del suficiente tiempo libre, echaré una ojeada más profunda al juego y veré que tal se me da intentar hacer un programa también... :D

      Eliminar
    3. Buenas Alfonso, me alegro que te hayas echado unas risas con la lectura eso siempre es positivo. ;)

      Inténtalo es un buen y divertido (sobre todo si eres masoca) reto, yo aunque dediqué excesivas horas para no conseguir resolverlo, me lo pasé muy bien intentándolo y no me arrepiento. Tenía aventuras que contar sobre el puzzle para llenar otro post. Si lo intentas me cuentas tus progresos.

      En parte quiero que salga un Eternity 3 y en parte no, porque si me pico serían demasiadas horas y por otro lado no me parece bien lo que hicieron con el final de Eternity 2.

      Eliminar
  20. hola!!!
    y después de tanto tiempo y sin sorteo por medio, me podrías compartir las pistas para intentarlo, solo por orgullo personal, que lo intenté mil veces, pero imposible, y más sin tener ninguna pista claro.
    un saludo

    ResponderEliminar
    Respuestas
    1. Lo siento, tenía el blog en hibernación. Ahora estoy viendo comentarios antiguos. En realidad cuando hice este post ya compartí las 4 piezas pistas. Si pinchas en la imagen de la configuración de mi programa verás qué piezas y en qué posición van, y luego para saber la rotación ayudado con la última imagen donde muestro el programa en ejecución.

      Te pongo aquí el trozo de configuración, aquí fijo 5 piezas, la central más las 4 pistas:

      [Pieces]
      ; Coherence between fixed will not be validated
      ; FixedJ=IdPiece+Rotation+PosX+PosY+
      Fixed=5
      Fixed1=139+3+8+9+
      Fixed2=255+0+14+3+
      Fixed3=181+0+3+14+
      Fixed4=249+1+14+14+
      Fixed5=208+0+3+3+

      Eliminar
  21. Alguien sabe donde se puede conseguir el puzzle y las piezas para comprarlo?

    ResponderEliminar
    Respuestas
    1. Ni idea, sólo podrás conseguirlo en mercados de segunda mano.
      Tienes estos foros de discusión sobre el puzzle que además últimamente han revivido y hay actividad:

      https://groups.io/g/eternity2

      Eliminar
  22. Una pregunta, si ya no hay premio que ganaría hoy en día alguien que lograra resolverlo?

    ResponderEliminar
    Respuestas
    1. Pues ganaría reconocimiento, prestigio y reputación a nivel mundial como poco. Y de ahí quizá alguna oportunidad laboral. Piensa que han pasado 15 años y nadie en el mundo lo ha resuelto.

      Todavía hay algunos "locos" de cuando yo empecé y otros que lo han descubierto más tarde o incluso hace poco, bastante activos pensando formas de intentar resolverlo, en este grupo del Eternity 2.

      Si te animas, ¡suerte!

      Eliminar
  23. hola vengo llegando... buenisimo todo este post esta hermoso, sin unda una joya total para la humanidad, hoy en dia tenemos otro tipo de sistemas complejos en donde podremos seguir indagando en este hermoso misterio, agregó: el autor todavía está vivo (siento esperanza), tambien las IAs estan en auge hacia la singularidad, las supercomputadoras están en vanguardia y podríamos soñar con acceder a las computadoras cuánticas, estoy seguro de que podrían dar solución a este enigma.. saludos

    PD: me parecio increible el avance de tus sistemas al pasar de procesar 12000 piezas a 14 millones... creo que en ese momento me di cuenta de lo complicado del asunto, buscando información, no aparece mucho...super interesante todooooooo wuuu felicidades

    ResponderEliminar
    Respuestas
    1. ¡Muchas gracias por tu comentario! Todavía me emociono y siento nostalgia cada vez que vuelvo a pensar en este puzzle. Le dediqué tantas horas, y si tuviera tiempo libre infinito, le seguiría dedicando.

      Siempre utilizo mi software como benchmark para los PCs nuevos que monto. Mi PC actual con un Ryzen 9 5900X procesa más de 30 millones/seg. Es el 50% más que lo que hacía el Intel i7 3930K con sus 20 millones/seg, claro que han pasado 10 años entre ambos procesadores... según cómo lo interpretemos no es mucho avance aunque sea del 50%.

      La clave del avance también está en que con el Ryzen puedo ejecutar 12 instancias (12 cores) de mi software, con piezas fijadas diferentes y dividir el tiempo de exploración entre 12. Mientras que con el i7-3930K lo podía dividir en 6. Es decir, que actualmente tengo el 100% más de cores y yendo al 50% más rápido cada uno.

      De todas formas sigue pareciendo poco probable resolverlo sin un ordenador cuántico. ¡Pero ya veremos! 😉

      Eliminar

Publicar un comentario

Castigos populares

Había una vez un teclado chiquitito

Había una vez un teclado chiquitito, que se podía, que se podía teclear. Pasaron un, dos, tres, cuatro, cinco, seis jornadas, y aquel teclado y aquel teclado en mi escritorio se quedó. Este castigo trata de los teclados mecánicos compactos pequeños. Se suele referir como teclado compacto a aquel cuyo tamaño es inferior a un teclado TKL ( TenKeyLess , sin teclado numérico), aunque compacto se refiere también a que todas las teclas están juntas sin espacios vacíos en el teclado. Compartiré mi experiencia con los teclados 60%, y los compararé con los teclados completos, TKL y 65%. Así que la publicación es 100% sobre teclados mecánicos, 90% sobre los mecánicos compactos 60%, y el 10% restante sobre otros porcentajes.

Montar teclado custom

Desde hace 13 años que soy entusiasta de los teclados, 9 años que me apasionan los teclados mecánicos, y 6 años que utilizo sólo teclados mecánicos compactos 60%. Hasta el momento siempre había tenido teclados mecánicos prefabricados, aunque los personalizaba en gran medida como se puede ver en otras publicaciones .

Todo lo que nunca quisiste saber sobre teclados

En esta publicación voy a dar con la tecla para conseguir un buen teclado, a escribir sobre el dispositivo de escribir, y al que podemos considerar el tacto informáticamente divagando. Porque a pesar de la proliferación de las pantallas táctiles, muy prácticas para algunos usos y también como quitagrasas de los dedos, cuando se trata de escribir de verdad y no de skrbr d vrda no se puede ni por asomo conseguir la misma experiencia ni rendimiento de escritura con otro periférico de entrada que no sea el veterano teclado. Todo el mundo sabe qué es un teclado pero no tantos conocen cómo sabe un buen teclado, ni dominan todo ese mundo de sensaciones y tecnología que intervienen durante y detrás de las pulsaciones. Además, para fastidiar la satisfacción con vuestro teclado actual y volver sibarita a vuestro paladar dactilar, llega este castigo.

Teclado 3%, con tres teclas basta

El título lo dice todo así que este preámbulo no dirá nada. Sólo añadiré que a lo mejor se me ha ido de las manos esto de reducir de tamaño el teclado mecánico.