Mediciones

Quince solucionadores, los nuestros y nuestras implementaciones de los dos backtrackers récord de la comunidad, cada uno ejecutado una vez sobre diez variantes del puzzle oficial con las esquinas fijadas, un solo núcleo, 60 segundos por ejecución. El hallazgo: el número de nodos no es la puntuación.

El backtracker en C de Peter McGavin, el más rápido de la comunidad: una receta de optimización de 2007 capitalizada durante dos décadas mediante código generado, tablas de búsqueda y trucos de contador, luego compilada en mi M1 y apuntada al puzzle real de 256 piezas, donde en un solo núcleo supera las 200 de 256 piezas a ~109M colocaciones/s.

El backtracker récord de Joshua Blackwood, decodificado gracias a las notas de Jef Bucas (un calendario de cuotas de color y una tolerancia a desajustes en el tramo final, ajustados casi óptimamente), luego construido y ejecutado en mi M1: tal como se publicó, vuela hasta 248 de 256 piezas ignorando las pistas; fija las cinco pistas oficiales y el mismo motor se atasca cerca de 45.

Un solo motor de propagación de restricciones, ejecutado bajo una docena de presets de ordenación y de propagadores, sobre las mismas diez variantes con esquinas fijadas que el ranking. Un estudio de lo que aporta cada ajuste, mantenido fuera del ranking principal porque el mejor preset alcanza menos de la mitad de la puntuación de un contendiente.

Las cinco comparaciones en el corazón del estudio de reparación, desarrolladas: la destrucción aleatoria ciega gana mientras que todo operador que apunta a los conflictos pierde; la construcción fija el suelo; el recocido simulado es la regla de aceptación más fuerte; y los refinamientos ingeniosos (recarga exacta, reinicios) no aportan nada con este presupuesto.

Los resultados, desarrollados: en estos tableros las cinco pistas con forma de pistas oficiales nunca ayudan a un backtracker, van de un coste moderado a una catástrofe, y el orden de relleno decide cuánto daño hacen; las puntuaciones son bimodales, no un gradiente suave; y la pregunta por el número de pistas está confundida por un suelo gratuito de costuras fijadas.

Las tres comparaciones en el corazón del estudio DFS, llevadas hasta el final: el orden de relleno (el recorrido por filas gana, un mal orden es catastrófico), las heurísticas (MRV rescata el borde primero pero cuesta rendimiento; más propagación no aportó nada) y las rupturas (rompen el muro de profundidad; el calendario de rupturas es la palanca, no el tope por celda).

Una sola pregunta, planteada con cuidado: entre los backtrackers en profundidad para Eternity II, ¿qué aporta realmente cada orden de relleno, cada heurística y el mecanismo de ruptura? Una familia de backtrackers escritos desde cero, separados cada uno por un único cambio, ejecutados sobre las mismas diez variantes con esquinas fijadas, en un solo núcleo, durante sesenta segundos.

Darle a un backtracker cinco piezas correctas gratis, en la geometría misma de las pistas del puzzle. Resulta que no ayuda, y según el orden de relleno puede dañar gravemente, porque una pieza fijada es una restricción dura que un orden de relleno fijo debe satisfacer al llegar. Una familia de órdenes de relleno, ejecutada sobre los mismos tableros con pistas, un solo núcleo, medida contra la ausencia total de pistas.

La hermana del estudio DFS, para la otra manera en que se ataca Eternity II: destruir parte de un tablero, reconstruirla, conservar el cambio si ayuda. Una pregunta, planteada con cuidado. Qué aporta cada decisión de ese bucle: qué región destruir, cómo reconstruirla, cuándo conservar un movimiento, cuándo reiniciar, y desde qué tablero partir.

Un backtracker Rust en profundidad, seguro y portable, especializado en tiempo de ejecución al emitir y compilar Rust propio de cada rompecabezas, llevado de 43 a 123 millones de nodos de búsqueda por segundo en un núcleo. Medido con justicia frente al C de Peter McGavin en la misma máquina: un empate en tableros difíciles y profundos como el Eternity II real, y alrededor del 44 % de su velocidad en los fáciles. Cada peldaño recorre el árbol idéntico; toda la ganancia es código, no algoritmo.

Mida las 256 piezas oficiales sin ningún solucionador a la vista y cada puerta estructural está cerrada: ninguna pieza simétrica por rotación, 5 parejas gemelas entre 32 640 emparejamientos, un tope de 307 sobre 480 si nada gira, presupuestos de color que se emparejan a exactamente 480 sin holgura, y una paleta 17+5 situada en el punto de una-solución-esperada.

Eternity II utiliza 22 colores, repartidos entre 17 colores interiores y 5 reservados al marco, y ese número de alrededor de 17 se sitúa cerca del punto donde este tipo de puzzle es más difícil de resolver (la transición es una banda, no un entero único).

La manera habitual de resolver un puzzle lógico es encontrar un lugar donde solo encaja una pieza, colocarla y repetir. Aquí ese recurso no existe: cada pieza interior tiene entre 73 y 137 vecinas posibles, y ninguna queda jamás fijada a una sola opción.

Un tablero casi perfecto no reparte sus escasos errores de forma uniforme. Los concentra en una sola banda de cinco filas y deja todo lo demás impecable. ¿Qué banda? Lo decide la dirección en la que la búsqueda rellenó el tablero, y puede verse el reflejo en los tableros récord reales.

En un puzzle de 16×16 construido como Eternity II, dieciocho pistas repartidas por el tablero lo resuelven en minutos, mientras que amontonarlas en filas contiguas necesita un centenar solo para bajar la búsqueda a decenas de miles de millones de colocaciones. La posición, no la cantidad, es la palanca, y apunta directamente a la fase final.

Cinco de los 22 colores de Eternity II aparecen solo a lo largo del anillo de borde, cada uno en exactamente 24 aristas, nunca una sola vez en el interior. Una separación estructural que moldea la forma en que cada solucionador trata el marco.