Mediciones

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.

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.

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

The results, worked through: on these boards the five clue-shaped hints never help a backtracker, they range from a mild cost to a catastrophe, and the fill order decides how much damage they do; the scores are bimodal, not a smooth gradient; and the hint-count question is confounded by a free pinned-seam floor.

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.

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.

Give a backtracker five correct pieces for free, in the puzzle's own clue geometry. It turns out not to help, and depending on the fill order it can hurt badly, because a pinned piece is a hard constraint a fixed fill order must satisfy on arrival. A family of fill paths, run on the same hinted boards, single core, measured against no hints at all.

Eternity II utiliza 22 colores, repartidos entre 17 colores interiores y 5 reservados al marco, y ese número de 17 coincide exactamente con el punto donde este tipo de puzzle es más difícil de resolver.

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.

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.

En un puzzle de 16×16 construido como Eternity II, dieciocho pistas repartidas por el tablero lo resuelven en minutos, mientras que el mismo puzzle necesita ochenta pistas o más amontonadas en filas contiguas para resultar igual de fácil. 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.