martes, 19 de abril de 2011

El Puzzle Interminable

Era verano del 2007 cuando navegando entre tetas y locuras por Yonkis 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 el coco 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 romper cocos en un periquete. Yonkis enlazaba a Microsiervos y fue allí donde obtuve la primera información sobre este puzzle cuyo nombre es Eternity II, un juego comercializado por Tomy.


Eternity II puzzle

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 era más fácil conseguirlo. Podéis ver aquí debajo el fichero de configuración del programa para haceros una idea de la cantidad y del tipo de parámetros que implementé.

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 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 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.





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. Si algún valiente la ha leído entera creo que merece dejar constancia de ello en un comentario, para que pueda además ascender su rango en el blog de castigado a castigado Pro.

Ver todos los castigos sobre Miss Celánea
Twitter: @dPunisher1337