¿Cómo se resuelve Eternity II con un ordenador?

2 · El muro exponencial

Y ese «todo», ¿cómo de grande es? Para un puzzle n×n hay aproximadamente n²! formas de ordenar las piezas, multiplicadas por sus 4 rotaciones cada una. El gráfico de abajo muestra el número de cifras de esa cuenta. Fíjate en que es una línea casi recta: cada escalón de tamaño multiplica el trabajo por un factor astronómico. La caja 16×16 que tienes en la estantería se sitúa en unas 560 cifras.

La línea azul encierra la primera lección del diseño de algoritmos: una deducción encoge mundos. Con solo notar que las piezas de esquina van en las esquinas y las de borde en el perímetro, ya se tachan unas 100 cifras. Los solucionadores de verdad encadenan muchas deducciones así. Y aún no basta ni de lejos.

La palabra «cifras» sigue siendo abstracta, así que hagámoslo personal:

3 · La dificultad, medida: tamaño y colores

Generamos cientos de mini-puzzles y dejamos que el motor resolviera cada uno, contando los nodos (los emplazamientos de pieza puestos a prueba) hasta la primera solución (mediana de 10 puzzles aleatorios por punto; ¡escala logarítmica!). Hay tres cosas que ver. Cada fila de más en el tablero multiplica el trabajo: las líneas se separan por varios órdenes de magnitud. Añadir colores suele hacer el puzzle más fácil, porque un emplazamiento erróneo se rechaza antes en lugar de arrastrar la búsqueda al fondo de un callejón sin salida. Y cada línea revela algo célebre: un marcado pico de dificultad. Muy pocos colores → soluciones a montones, fáciles de encontrar por azar. Muchos colores → un puzzle tan restringido que la búsqueda apenas se ramifica. El pico se aloja justo en medio y, sobre todo, se desplaza hacia la derecha a medida que crece el tablero: la línea 6×6 culmina en 4 colores, la línea 8×8 en 6 colores, más o menos un color más por cada fila añadida. En su pico, el puzzle 8×8 mediano exige más de 2 mil millones de emplazamientos de piezas, y la mayoría de las semillas allí tardaron tanto que tuvimos que dejar de medirlas (las mesetas planas son esos puntos censurados). Un color a un lado u otro y todo se derrumba por un factor de cien. Prolonga esa tendencia de un color por fila hasta un tablero 16×16 y el pico cae justo en torno a los 22 colores: exactamente donde se diseñó Eternity II para situarse. No es casualidad que quede más allá del pico; está calibrado para caer sobre él.

4 · El orden en que buscas importa. Y mucho.

Mismos puzzles, mismo solucionador. Lo único que cambia es el orden en que se rellenan las casillas. Los órdenes que mantienen cada nuevo emplazamiento pegado a vecinos ya colocados (snake, spiral) restringen cada paso y podan pronto. Los que dispersan los emplazamientos (random) dejan las piezas sin restricción y lo pagan más adelante. Es un tema de investigación de verdad, y puedes diseñar tu propio orden y echarlo a correr. Este es el aspecto real de los órdenes clásicos; sigue las flechas (rojo = primera casilla, verde = última):

Una sutileza que conviene nombrar (gracias a Dan Karlsson): por filas y por columnas son el mismo orden salvo por voltear el tablero sobre su diagonal, así que en muchos puzzles deberían costar lo mismo; cualquier diferencia aquí es ruido de muestreo, no una diferencia real. Los órdenes que difieren de verdad son los de forma distinta: una espiral, una diagonal, el borde primero. Una salvedad: la barra del orden aleatorio es una cota inferior, no una mediana medida: cada ejecución muestreada alcanzó el tope de búsqueda sin terminar, así que su coste real es mayor que el mostrado.

La misma pregunta, llevada hasta el final sobre el puzzle 16×16 completo, es el estudio DFS: mide lo que aporta cada orden de relleno, cada heurística y cada regla de ruptura, y descubre que el orden equivocado puede costar más de 300 puntos de puntuación.

5 · Por qué aquí los ordenadores piensan en binario

Una pieza no es más que cuatro números pequeños (los motivos de arriba, derecha, abajo e izquierda). Ni imágenes, ni geometría. Estas cuatro demos funcionan en directo; obsérvalas unos segundos cada una:

Guardado como números, el conjunto oficial entero ocupa alrededor de 1 KB. Los solucionadores serios van más allá con los bitsets: un único número de 64 bits transporta una respuesta sí/no sobre 64 piezas a la vez, de modo que una sola instrucción de la CPU filtra 64 candidatas de golpe. Así es como los motores más rápidos alcanzan cientos de millones de nodos por segundo. La representación, y no solo el algoritmo, forma parte del oficio.