- Para entender el muro
- Empieza por Demaine & Demaine (la demostración de NP-completitud) y Ansótegui–Béjar–Fernández–Mateu: juntos explican por qué no se conoce ningún algoritmo rápido general y, sobre todo, por qué se eligieron los parámetros exactos de Eternity II: el puzzle se sitúa en la transición de fase SAT/CSP (≈17 colores interiores), donde las instancias tienen alrededor de una solución esperada y son las más difíciles de hallar.
- Para ideas que aceleran un solucionador
- El filtrado global en O(1) por nodo de Benoist & Bourreau y la búsqueda CP + vecindario muy grande de Schaus & Deville son el linaje detrás de la mayoría de los tableros récord. La hiperheurística de Wauters et al. y las formulaciones MILP + clique máxima de Salassa et al. son las mejores metaheurísticas publicadas. Harris/Vanstone/Gepp se apoyan en el conocimiento estructural y en la distribución uniforme de colores en lugar del forward-checking genérico, y reportan hasta tres órdenes de magnitud sobre los solucionadores anteriores.
- El núcleo de la propagación de restricciones
- Si implementas una poda de verdad, el filtrado AllDifferent de Régin (consistencia de arco generalizada mediante emparejamiento bipartito) es la piedra angular: el suministro acotado de piezas por color en Eternity II convierte un AllDifferent por color en el propagador global más potente. Compact-Table es el algoritmo al que recurrir si algún día codificas tablas de parches precalculadas.
- Otro paradigma que conviene conocer
- Kovalsky–Basri–Glasner resuelven el ensamblaje de puzzles como un único programa lineal global en vez de por colocación secuencial. NO se traslada directamente a E2 (la compatibilidad de imagen es de valor real; las aristas de E2 son discretas) —los propios autores lo dicen—, pero el enfoque de optimización global es un contraste útil frente al backtracking y la semilla de cualquier intento de relajación SDP.
- Un truco práctico que los artículos infravaloran
- Precalcular los pares de dos piezas legales (esquina+borde, borde+interior, interior+interior) y buscar sobre pares en lugar de sobre piezas sueltas es una aceleración recurrente en la comunidad: adelanta la comprobación de restricción más barata y reduce el factor de ramificación. Es tanto folclore como literatura, pero conviene conocerlo antes de reinventarlo.
- Hasta dónde llega la literatura
- Ningún método publicado resuelve realmente el tablero de 16×16. Las codificaciones SAT/CSP topan empíricamente en torno a subpuzzles de 10×10; las mejores heurísticas se estancan muy por debajo de 480 aristas coincidentes. El récord de la comunidad (470/480, Blackwood 2021, con su propio solucionador; igualado desde entonces) supera a todos los solucionadores publicados en la academia. La frontera vive hoy en la comunidad (groups.io, Discord) y en cuadernos de laboratorio abiertos como este, no en un artículo.