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.
Mida las 256 piezas oficiales sin ningún solucionador a la vista y cada puerta estructural está cerrada: ninguna pieza simétrica por rotación, 5 parejas gemelas entre 32 640 emparejamientos, un tope de 307 sobre 480 si nada gira, presupuestos de color que se emparejan a exactamente 480 sin holgura, y una paleta 17+5 situada en el punto de una-solución-esperada.
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. Una medición con tableros plantados pone cifras a la elección de la formulación: un acantilado de resolubilidad que un paradigma de búsqueda golpea y otro cruza, y que se mueve con el número de colores.
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.
Un argumento de conteo sobre el juego de piezas oficial prohíbe una puntuación de exactamente 479/480: las semiaristas de cada color vienen en cantidades pares, y una sola unión rota dejaría dos cuentas impares. El suelo bajo lo perfecto es 478, y a lo sumo 76 cuasi-soluciones a un movimiento pueden rodear una solución.
Eternity II utiliza 22 colores, repartidos entre 17 colores interiores y 5 reservados al marco, y ese número de alrededor de 17 se sitúa cerca del punto donde este tipo de puzzle es más difícil de resolver (la transición es una banda, no un entero único).
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.
La meseta comunitaria en los 460 altos se lee como una frontera de fase entrópica de la instancia, no como un límite de la ingeniería de solvers: el cálculo exacto sobre el juego oficial da una densidad de restricciones cercana a 0,0094, un paisaje recocido que se derrumba por encima de 470 y solo cruza 1 en 480, y un número esperado de 10 a 20 soluciones perfectas casi ortogonales entre sí. Los números del lado de la instancia son exactos; el cuadro de la brecha de solapamiento en 16x16 es una conjetura declarada.
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.
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.
Cinco de los 22 colores nunca tocan las 196 piezas interiores. La lista de piezas obliga a toda solución válida a gastar las 120 semiaristas de marco en el anillo del borde: un subpuzle autónomo con holgura exactamente nula (120 = 120), un circuito euleriano sobre cinco vértices, acoplado al interior solo por 56 aristas orientadas hacia dentro.
Pondere cada color de arista y lea cada pieza como un vector con signo, este menos oeste en un eje, sur menos norte en el otro. Sumado sobre cualquier región, las costuras interiores se cancelan y solo sobrevive el borde, de modo que el tablero totaliza cero. Un cuarto de vuelta gira el vector un ángulo recto, lo que vuelve la ley álgebra en los enteros de Gauss.
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.
Toma el truco del físico que vuelve solubles los defectos cristalinos e intenta convertir un empalme mal casado en una dislocación con una carga conservada. Fracasa de tres maneras: una altura escalar es ciega a las roturas, el conjunto de roturas forma cadenas abiertas y no bucles cerrados, y la corriente orientada por color no se conserva. Solo sobrevive un bit de paridad sin signo.
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.
Rellena un tablero en cualquier orden fijo y los tres cuartos de arriba entran con soltura, mientras la dificultad se amontona en la banda que terminas al final. En cuarenta tableros generados, todo lo que sobra cae en la mitad inferior cada vez; baraja el orden de relleno y se dispersa, así que la región difícil la fabrica el barrido, no está escondida en el tablero.
Sume, para cualquier orden de visita del tablero 16x16, el número de vecinos ya colocados que cada celda enfrenta en el instante en que se rellena: el total es exactamente 480, sea cual sea el orden. Un orden de llenado no puede añadir restricción; solo elige cuándo se aplica cada una. Lo que separa a los órdenes es la inmediatez, la distancia entre una decisión y su refutación, y solo los extremos de esa clasificación pertenecen al puzzle y no al motor.
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.
Lee un tablero completo como una palabra de código cuyas 480 junturas interiores son comprobaciones de tipo paridad, y el score de aristas emparejadas pasa a ser 480 menos el número de comprobaciones fallidas. Es una lente limpia que descansa sobre una sola identidad portante, y conviene ser preciso sobre lo que la vista de códigos correctores aporta y lo que solo renombra.
En un puzzle de 16×16 construido como Eternity II, dieciocho pistas repartidas por el tablero lo resuelven en minutos, mientras que amontonarlas en filas contiguas necesita un centenar solo para bajar la búsqueda a decenas de miles de millones de colocaciones. La posición, no la cantidad, es la palanca, y apunta directamente a la fase final.
Unir pares de pistas con pasillos de piezas tendidos pronto parece añadir restricciones. El recuento dice lo contrario: un pasillo de ancho 1 entre las dos pistas más cercanas admite unos dos mil billones de rellenos distintos, así que no excluye casi nada mientras gasta piezas que la fase final va a necesitar. En un A/B controlado, cada brazo con pasillos perdió frente a su propio control en todos los tamaños de tablero.
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.
El anillo del borde es la parte más restringida del rompecabezas, así que un borde fuerte distinto debería fijar un interior alto distinto. No lo hace. Muchos bordes completamente emparejados y distintos, cada uno completado por un mismo productor de interior fijo, dan cimas casi máximamente distintas entre sí pero uniformemente bajas, ninguna cerca de la franja récord. El borde diversifica el tablero sin predecir su techo.
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 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.
Un solo arco de investigación, trece familias de teoremas estructurales: pureza del anillo, el suelo de paridad en 479, el muro de 470 como frontera de fase, los invariantes de flujo, la ley de área entrópica, y los resultados de imposibilidad que ponen precio a cada atajo clásico. Esta página es el mapa.