Oops Again

 

Este juego tiene 10 piezas y cada pieza consta de dos bolas unidas en un punto. Lo que diferencia unas piezas de otras son los colores de sus bolas. En el juego hay 5 colores diferentes y en las 10 bolas encontramos todas las formas posibles que hay de combinarlos de dos en dos (sin repetir colores en cada pieza).

El objetivo del puzzle es colocar las piezas formando una pirámide con base triangular de forma que dos bolas del mismo color nunca se toquen. El puzzle fue inventado por Mike Reilly y se comercializó en 1993 a través de Channel Craft. Bueno, en realidad se comercializaron dos juegos. La palabra Again dentro del nombre del puzzle hace referencia a otro juego de menor tamaño llamado Oops, con la mitad de piezas. Dejo aquí una imagen que conservo de hace bastante tiempo donde se ven los dos juegos (y que no recuerdo de dónde salió).

La verdad es que teniendo el juego grande, es muy fácil quedarse sólo con las 5 piezas necesarias para el pequeño y jugar. Simplemente eliminando todas las piezas que lleven uno de los colores (por ejemplo el lila) y otra pieza más (no importa cuál, por ejemplo el verde y azul).

Equivalencias y simetrías

Ambos juegos son bastante entretenidos y por supuesto es más difícil resolver el grande que el pequeño. Aunque ninguno de los dos nos llevará demasiado tiempo son muy entretenidos e interesantes. ¿Pero, cuántas soluciones tienen? Incluso contar las soluciones que vamos obteniendo no es fácil porque si tenemos una solución válida y hacemos una permutación de colores, obtendremos otra solución aparentemente diferente. Pero sólo aparentemente ya que supongo que todos coincidiremos en que se debería considerar como la misma ya que, por ejemplo en Oops again todos los colores son “simétricos” (en Oops hay dos grupos de colores).

Del mismo modo, si hacemos una rotación o cualquier otra simetría del tetraedro (de las 23 distintas de la identidad que tiene) obtendremos otra que también debería considerarse como equivalente. Es decir, tenemos dos formas de hacer que una misma solución parezca otra diferente pero sin serlo realmente (incluso una tercera que sería combinar las dos formas).

Al tener tantas soluciones equivalentes, lo primero que es importante es fijar una de ellas como “representante canónico” de todas. Y por supuesto pensar en algún método para poder anotarlas.

Buscando todas las soluciones

Desde que me fabriqué una copia de este juego (hace ya más de 22 años) siempre me ha intrigado saber el número total de soluciones del puzzle. Para Oops hice un pequeño análisis a mano y llegué a la conclusión de que tiene sólo dos soluciones, eliminando simetrías y permutaciones de colores (aunque como pondré al final de este post, este resultado no era correcto).

Pero con Oops again no he tenido tanta paciencia. Aunque empecé a analizarlo a mano, enseguida pude ver que tenía tantas posibilidades que no tuve valor a seguir intentándolo. Como siempre, teniendo BurrTools era obligado intentar hacer algo con este programa. Por lo menos conseguí ver que, considerando las piezas todas iguales e ignorando los colores, las piezas se podrían colocar de 213 formas diferentes para formar la pirámide.

Seguramente si intentase poner color a cada una de esas 213 soluciones para que cumpliese las restricciones del juego tendríamos que cada una (o muchas) se desdoblaría en varias coloraciones diferentes válidas. Con lo cual, efectivamente, eran demasiadas soluciones para hacerlo a mano. Sólo era razonable programarlo para que se resolviera con ordenador. Lo malo es que yo no sé nada de programación. Hace 10 años compartí en facebook una foto de este juego y animé a mis contactos a que buscasen el número de soluciones del puzzle. Pero imagino que nadie con los conocimientos necesarios se animó a hacerlo. Igual ya se conoce el número de soluciones, pero yo no he podido enterarme. También intenté contactar con Mike Reilly, pero no tuve éxito.

Programando en Python con IA

Finalmente, este invierno me enteré casualmente de que ChatGPT podía usarse para programar. Supongo que habrá otras IA que estarán más especializadas en programación, pero a mí se me cruzó esta en el camino y lo intenté con ella. Preparar la descripción de las piezas y las adyacencias dentro del tetraedro era lo más sencillo. Pero conseguir guiar a la IA para que el programa funcionase correctamente fue bastante trabajoso y a veces desesperante. Y supongo que alguien con bastantes conocimientos de programación lo haría con menos trabajo, más elegante y mejor.

Para empezar, pensé que sería bueno fijar una pieza concreta en un vértice de la pirámide (ya que todas las piezas son “equivalentes” en un principio. De ese modo ya habrá dos colores fijos y una pieza. Y para seguir “normalizando las soluciones” fijé también dos colores en las posiciones que forman un pequeño tetraedro con la pieza fijada en el vértice de la solución.

Con ese punto de partida y mucha ayuda por mi parte, la IA consiguió generar un programa con el que se obtenían 251626 soluciones y las pude guardar en un Excel para analizarlas. Según mi forma de “normalizar” los colores (eligiendo los 4 que formarían un vértice de la pirámide) ya se habrían eliminado las posibles permutaciones de colores.

Aún así, y dado que por el camino la IA había fallado con la implementación de mis requisitos en multitud de ocasiones, ese resultado me generaba bastante desconfianza. Por lo que intenté analizar un poco las soluciones del Excel obtenido. Lo primero que conseguí ver es que si ignoramos los colores, en la estructura de todas esas soluciones hay sólo 213 “estructuras” diferentes de las piezas. Es decir, la misma solución aportada por BurrTools. Eso me hizo tener algo más de confianza en el conjunto de soluciones que teníamos.

El siguiente paso que intenté fue modificar el programa (o mejor dicho, pedir a la IA que lo hiciera) para que en lugar de las piezas del puzzle usara sólo 20 bolas de colores sueltas. Es decir eliminar la “estructura” de las piezas y el puzzle para fijarnos sólo en cuántos coloraciones diferentes de la pirámide podían obtenerse. Resultado inicial: 3778 (ya eliminando las simetrías y partiendo de las soluciones “normalizadas”).

¿Cuántas soluciones tienen?

Y así creía haber concluido mi análisis del número de soluciones. Ya que en teoría las permutaciones de colores ya estaban tenidas en cuenta y también las 24 simetrías del tetraedro. Pero me faltaba probar también qué pasaba si las combinaba. Tomé una solución del juego, le apliqué una simetría y luego una permutación de colores adecuada para “normalizar” las solución (y así poder compararla con el listado de 251626 soluciones). De ese modo encontré que llegaba a otra solución teóricamente diferente de ese listado. Es decir, tenía que depurar esas soluciones ya que habría muchas equivalentes.

Es probable que lo mejor fuese modificar el programa para que tenga en cuenta esto. Pero yo tenía ya resultados en Excel y preferí seguir la vía de buscar otro programa que depurase estos resultados. Empecé con el que contenía las 3778 coloraciones diferentes del puzzle ya que me parecía más sencillo y de nuevo con Python conseguimos que esas soluciones se redujeran a 183 coloraciones.

De modo que 183 coloraciones diferentes y 213 “estructuras” diferentes podrían dar como máximo un total de 183*213=38979 soluciones (ya tenía una cota máxima para las soluciones del juego).

Y finalmente, después de bastantes equivocaciones y de casi tirar la toalla en varias ocasiones llegamos a reducir a 31617 las soluciones para Oops again (partiendo de las 251626 iniciales).

Y haciendo lo mismo (ahora a mano) con su hermano pequeño Oops pude comprobar que mis dos soluciones iniciales eran en el fondo equivalentes. Con lo cual, yo diría que Oops (10 bolas) tiene una solución única.

Estas son mis conclusiones y la verdad es que me gustaría que alguien con conocimientos de programación pudiera comprobar si son correctos o si estoy equivocado. Dar por correcto un resultado hecho con ordenador me resulta difícil si no se tiene confianza en el programa usado. Y en este caso, al no tener ni idea de programación mis inseguridades se multiplican. Pero lo que sí tengo claro es que todas las soluciones que he probado de mi listado son válidas y correctas.

Igualmente si alguien tiene algo que corregirme sobre mi forma de considerar soluciones equivalentes, lo debería hacer libremente.