Por qué es difícil
Eternity II no es difícil por accidente. Fue diseñado para resistir el ingenio, y los muros estructurales medibles (rigidez, entropía, patrones prohibidos) explican por qué ninguna búsqueda, por ingeniosa que sea, ha llegado al final.
La idea más importante de la búsqueda combinatoria difícil: reducir el espacio que se explora vence, por un margen exponencial, a explorarlo más rápido. Eternity II está diseñado para que apenas puedas reducirlo.
La sección de investigación tiene dos vertientes: los muros estructurales que hacen difícil a Eternity II, y los algoritmos concebidos para franquearlos. Esta página es el puente: cada método enfrentado al muro que realmente ataca, y la puntuación en la que ese muro lo detuvo.
El emparejamiento de aristas es NP-completo como familia, pero eso no dice nada de un tablero 16×16 fijo: una instancia aislada es una constante, no un problema. Lo que sí es cierto es la dureza en el peor caso de la familia y la dureza empírica de esta instancia, y cómo escribir el puzzle para un solucionador SAT, de cobertura exacta o de PLE, con pequeños esbozos detallados.
La teoría compleja de Brendan Owen estima la anchura del árbol de búsqueda a cada profundidad, e incluso cuántas soluciones existen en total. Muchos en la comunidad la consideran lo más importante que hay que entender sobre Eternity II.
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.
Eternity II sigue una receta para lograr el puzzle de emparejamiento de aristas más difícil posible: forma compacta, sin piezas simétricas ni duplicadas, paletas separadas, frecuencias planas, una sola solución esperada. La comunidad aplicó ingeniería inversa a cada ingrediente en el año del lanzamiento.
Cada tablero récord que tenemos está congelado en su sitio. No se puede progresar a base de pequeños retoques desde un tablero excelente hacia uno perfecto, y podemos demostrarlo.
Si no puedes mejorar un tablero excelente puliéndolo, quizá puedas saltar a otro tablero excelente. En cada par de récords probado, no puedes, y vale la pena ver la razón estructural que lo explica.
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.
Casi todo pequeño conjunto de piezas que podrías construir es imposible. Para un cuadrado 2×2, el 99,72 % de las formas de colocar cuatro piezas nunca podrá encajar.
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.
Un solucionador rellena unas pocas filas sin esfuerzo y luego choca contra un muro en mitad del tablero. He aquí el mecanismo: una pieza escasa gastada en el lugar equivocado, varias filas atrás.
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.
Un tablero resuelto esconde una sencilla ley contable: cada color que el borde entrega al interior, el interior se lo devuelve al instante. Rómpela y sabrás de inmediato que el tablero es incorrecto; respetarla, en cambio, no garantiza nada.
Eternity II tiene dos reglas: los bordes deben coincidir y cada pieza se usa una sola vez. La primera es generosa. Toda la dificultad reside en la segunda.