Reducir la búsqueda
Todo lo que descarta estados sin esperanza antes de que la búsqueda pierda tiempo en ellos: propagación hasta el punto fijo, el filtro de emparejamiento all-different, no-goods aprendidos y el invariante de deslizamiento de bordes.
El forward checking mira un movimiento por delante; la consistencia de arco obliga a la lista de candidatos de cada celda a defenderse frente a la de cada vecina, hasta un punto fijo. El AC-3 de Mackworth, los refinamientos óptimos que vinieron después, y lo que toda esa familia midió realmente en este puzzle, incluido dónde deja de ser correcta.
Ninguna pieza puede usarse dos veces: una sola restricción all-different global sobre 256 celdas. Jean-Charles Régin mostró en 1994 cómo un matching bipartito la filtra por completo en tiempo polinómico; su variante por color es el propagador más potente jamás medido sobre el edge matching, con una reserva clara sobre las búsquedas tolerantes a desajustes.
La jugada premiada de Louis Verhaard: dejar que el backtracker coloque una pieza no concordante, pero solo a profundidades escogidas cerca del final del tablero. Cada deslizamiento permitido cuesta un punto de puntuación y multiplica de forma astronómica el número de tableros objetivo. Por eso su 467 se encontró más de cincuenta veces, y el ancestro directo de las rupturas de Blackwood.
Un subárbol fallido es un teorema: este estado parcial nunca podrá extenderse. Memorízalo y no vuelvas a entrar en él. La comunidad probó ambas variantes: tablas de transposición al estilo del ajedrez sobre la frontera de búsqueda, y restricciones extraídas del propio puzzle. El balance completo de lo que la memoria compra a la escala de E2, y los tableros pequeños donde realmente rinde.