Cómo buscan en realidad los solucionadores que ostentan los récords. Todos son, en el fondo, backtrackers en profundidad; lo que los distingue es el orden en que prueban las cosas y cómo doblan las reglas al acercarse al final.
Todo solucionador que ostenta un récord serio en Eternity II es, en el fondo, la misma máquina: un backtracker en profundidad. Lo que los distingue no es el bucle, sino tres decisiones que se superponen a él: el orden en que visitan las celdas, las heurísticas que deciden qué pieza probar primero y cómo doblan el final de la partida cuando ya no queda una coincidencia perfecta. Esta página es el recorrido neutral por esas decisiones. La historia completa y de primera mano de cada motor (descifrada a partir del código fuente y la literatura, y luego reconstruida y medida) vive en su propia página de laboratorio, enlazada desde cada sección más abajo.
Antes del recorrido, el catálogo: una fila por motor, y las cuatro decisiones que lo distinguen. Cada alcance se mide en un solo núcleo, en una misma máquina, de modo que los números se comparan igual con igual en vez de entre clústeres; cada fila enlaza su informe completo.
| Motor | Orden de relleno | Poda | Régimen de hardware | Alcance medido |
|---|---|---|---|---|
| Backtracker de Blackwood | barrido por fila desde abajo-izquierda, piezas de borde al final | cuota de color por profundidad más un presupuesto de índice de ruptura según la profundidad | un solo núcleo; el 470 salió de muchos núcleos en paralelo | 248/256 piezas sin restricción; se estanca cerca de 45 al fijar las cinco pistas |
| eii de Verhaard | órdenes de búsqueda en peine | poda anticipada frente a umbrales de puntuación ajustados; un calendario de deslizamiento ajustado por Markov | binario Win32 en un núcleo; sin fuente para recompilar | 467/480, el único premio que pagó el concurso |
| Backtracker C de McGavin | según el puzle: barrido por fila, espiral, o borde primero | código generado más tablas de consulta y trucos de contador para el rendimiento bruto | un solo núcleo, ~109M colocaciones/s en el puzle real | más allá de 200/256 piezas; hecho para la velocidad, no para un score récord |
| Reimplementación de Verhaard | recocido por intercambio de composición de conjuntos bajo la métrica 2×2 | aceptación por recocido, constantes recuperadas al bit desde el binario | un solo núcleo; ejecución versionada y reejecutable | 438/480 en el puzle real de cinco pistas |
| Preajustes CSP, medidos | una docena de preajustes de orden, borde primero el mejor | propagación por consistencia de arco | un solo núcleo, diez variantes ancladas por esquina | cerca de 183 en las variantes ancladas; por debajo de la mitad del score de un contendiente |
El recorrido de abajo repasa las tres decisiones que comparten esas filas.
Rellenar el tablero celda por celda en un orden fijo. En cada celda, probar toda pieza y rotación cuyas aristas coincidan con lo ya colocado; si ninguna encaja, retroceder y probar la celda anterior de otra manera. Correcto pero lento: el árbol de búsqueda es de una anchura astronómica.
Esto es exactamente eso, a cámara lenta: un backtracker real sobre un 3×3, una decisión a la vez. Recórrelo paso a paso y observa cómo se coloca una pieza, aparece un callejón sin salida y la búsqueda retira la pieza y vuelve a intentarlo.
El orden en que visitas las celdas cambia la dificultad en varios órdenes de magnitud, porque algunos órdenes fuerzan a que los conflictos afloren pronto (bueno) y otros los posponen hasta que se ha desperdiciado mucho trabajo (malo). Empezar por el borde supera con amplio margen a un recorrido fila por fila sobre el mismo puzzle. Es la única palanca que ajusta cada motor récord: los órdenes de búsqueda en peine de Verhaard, el barrido de Blackwood en filas desde la esquina inferior izquierda con las piezas de borde intercaladas tardíamente y la elección por McGavin, puzzle a puzzle, entre barrido en filas, espiral hacia el interior o borde primero son todas respuestas a la misma pregunta.
Un backtracker elemental prueba los candidatos en un orden arbitrario. Un motor récord los puntúa, de modo que las piezas con más probabilidad de importar se colocan primero, y poda toda rama que se quede rezagada respecto a un calendario. El solucionador de Blackwood, por ejemplo, privilegia tres colores e impone una cuota por profundidad que debe cumplirse para seguir descendiendo; Verhaard poda hacia adelante apoyándose en umbrales de puntuación ajustados a mano. Los detalles difieren, pero la forma es compartida: comprometer pronto las piezas restringidas, cortar las ramas que no pueden rentabilizar su coste.
Nunca se ha encontrado un teselado perfecto de 256 piezas. En su lugar, cada tablero récord tolera un puñado de discordancias tardías, y los motores las alcanzan planificando la imperfección: un presupuesto por profundidad de aristas no coincidentes que se desbloquea en lo más hondo de la búsqueda. Verhaard llamó al suyo un array de deslizamiento (slip array); Blackwood llama al suyo los índices de ruptura (break indexes). La misma idea, condicionada por la profundidad para que el inicio del tablero se mantenga limpio y las discordancias solo se gasten allí donde más rinden.
El laboratorio de abajo te permite mover ese presupuesto y observar cómo cambia la puntuación alcanzable:
Un puzzle 8×8 fijo, el solucionador real ejecutándose en tu navegador. Una rotura —un único desajuste permitido— solo se admite en las filas inferiores que autorices más abajo, reflejando cómo los solucionadores récord confinan las roturas a unas pocas posiciones fijas. Sin ninguna, la búsqueda estricta se estanca por debajo de un tablero completo. Autoriza una fila o dos y lo completa, casi perfecto.
Prueba primero con una sola fila: dónde se autorizan las roturas importa tanto como cuántas. Reparte esa misma cantidad arriba y el tablero no terminará — los conflictos que este orden de recorrido acumula caen abajo.
Cada motor récord tiene una página dedicada que descifra cómo funciona y luego lo reconstruye y lo mide en una sola máquina, en un solo núcleo:
El área de pruebas ejecuta un solucionador en profundidad real en tu navegador. Míralo buscar en directo o dibuja tu propio orden de relleno y ponlo a competir contra los clásicos para sentir cuánto importa el orden.
Para los enfoques que no funcionan, consulta los callejones sin salida.