Esta página responde a una pregunta que reaparece una y otra vez en los Stack
Exchange de matemáticas e informática y que encabeza la lista de disputas en la
página de discusión de Wikipedia sobre el puzzle: el emparejamiento de aristas
es NP-completo en general, así que ¿nos dice eso algo sobre este tablero
16×16 fijo y, en concreto, cómo se le entregaría Eternity II a un solucionador?
Las respuestas breves son: no, no directamente, aquí van tres codificaciones, y
una medición al final muestra cuánto puede importar la elección entre ellas.
La NP-completitud es una propiedad de un problema, lo que en teoría de la
complejidad designa una familia infinita de instancias indexada por un parámetro
de tamaño n. Los «puzzles de emparejamiento de aristas» forman una familia de
ese tipo: dados n, un conjunto de piezas cuadradas y un alfabeto de colores,
decidir si las piezas embaldosan un marco n×n con todas las aristas
adyacentes en concordancia. Ese problema de decisión es NP-completo
(Demaine & Demaine 2007), lo que
significa tanto que una solución propuesta es verificable en tiempo polinómico
como que todo problema de NP se reduce a él.
Un único tablero fijo no es una familia. La instancia de Eternity II tiene una
respuesta bien definida, «sí, tiene solución» (los diseñadores la construyeron a
partir de una solución) o, en la forma de competición con 5 pistas, «sí, con
exactamente esta disposición». Esa respuesta cabe en un solo bit. Un solo bit es
una constante, y «¿es NP-completa esta constante?» no es una pregunta bien
formada: existe un algoritmo en tiempo constante que imprime la respuesta
(return true), sencillamente lleva la respuesta grabada dentro. Preguntar si
una instancia aislada es NP-completa incurre en el mismo error de categoría que
preguntar si el número 17 es de tiempo polinómico.
Así pues, la familia es dura y la instancia es una constante. ¿Qué hay,
entonces, de realmente cierto y útil que decir sobre la dificultad del tablero
que tienes sobre el escritorio?
Dos afirmaciones distintas, mantenidas por separado:
- Dureza en el peor caso de la familia. Como el problema general es
NP-completo, no se conoce ningún algoritmo que supere el tiempo exponencial en
el peor caso a medida que n crece, y encontrar uno probaría
P=NP. Esto acota lo que puede prometer cualquier
solucionador de emparejamiento de aristas genérico. No dice nada sobre cómo se
comporta una entrada específica.
- Dureza empírica de esta instancia. Una dureza que se puede medir. El
tablero 16×16 tiene del orden de 1,115×10557 disposiciones distintas
de piezas y rotaciones, y el puzzle parece admitir muy pocas soluciones (la
forma con 5 pistas está diseñada para tener esencialmente una; véase la
teoría de la complejidad para la estimación del
número esperado). Por tanto, una búsqueda con backtracking enhebra un espacio
astronómicamente amplio hacia un conjunto de soluciones casi vacío, y así pasa
casi todo su tiempo explorando callejones sin salida. Por eso el puzzle es
duro en la práctica, y es una afirmación sobre este tablero, no sobre la
familia.
El teorema del peor caso y la dificultad empírica apuntan aquí en la misma
dirección, pero son enunciados de naturaleza distinta y solo uno de ellos es un
teorema. Una familia puede ser NP-completa mientras que una instancia dada es
trivial (muchas lo son), y una instancia puede ser brutalmente difícil de
resolver en la práctica incluso dentro de una familia polinómica. Ansótegui et
al. plantearon exactamente ese caso empírico para Eternity II, construyendo a
partir de él bancos de pruebas para solucionadores y midiendo la dificultad
directamente en lugar de apelar al teorema general
(CCIA 2008).
La versión en una línea
«¿Es Eternity II NP-completo?» No: una instancia no tiene clase de
complejidad. «¿Es NP-completo el problema de emparejamiento de aristas?» Sí.
«¿Es difícil de resolver esta instancia?» Empíricamente sí, porque el espacio
de búsqueda es de ~10557 de ancho y el conjunto de soluciones está casi
vacío, de modo que la búsqueda se ahoga en callejones sin salida.
Lo demás es práctico: ¿cómo escribes el tablero para que un solucionador pueda
masticarlo? Las tres codificaciones de abajo comparten el mismo esqueleto.
Numera las celdas c=1…256, las piezas p=1…256 y las
rotaciones r∈{0,1,2,3}. Una colocación es un triple (c,p,r): la
pieza p depositada en la celda c girada r cuartos de vuelta. Toda
codificación tiene que expresar tres cosas:
- cada celda recibe exactamente una colocación,
- cada pieza se usa exactamente una vez,
- dondequiera que dos celdas se toquen, los colores de la arista compartida
concuerdan.
Las codificaciones solo se diferencian en cómo expresan la restricción 3, el
emparejamiento de colores, y esa diferencia es toda la historia. Los esbozos de
abajo usan un tablero 2×2 o 3×3 para que puedas ver todas las cláusulas; el
16×16 tiene la misma forma a mayor escala.
Introduce una variable booleana xc,p,r, verdadera cuando la pieza p se
asienta en la celda c en la rotación r. En el tablero completo eso son
256×256×4≈262,000 variables antes de cualquier
restricción. Luego:
- Exactamente una colocación por celda. Para cada celda c, una cláusula de
«al menos una» sobre todas sus colocaciones, ⋁p,rxc,p,r, más
cláusulas de «a lo sumo una» que prohíben cualquier par,
¬xc,p,r∨¬xc,p′,r′ para colocaciones distintas.
- Exactamente una celda por pieza. La imagen especular: para cada pieza p,
una cláusula de «al menos una» sobre las celdas que podría ocupar, más
cláusulas de «a lo sumo una» para que se coloque solo una vez.
- Emparejamiento de aristas. Para cada adyacencia interior y cada colocación
cuya arista expuesta muestra el color k, prohíbe toda colocación de la celda
vecina cuya arista enfrentada no sea k: una cláusula binaria
¬xc,p,r∨¬xc′,p′,r′ por cada par en conflicto.
Un esbozo 2×2 concreta la tercera familia. Las celdas A (arriba a la
izquierda) y B (arriba a la derecha) comparten una arista vertical; la arista
este de A debe ser igual a la arista oeste de B. Para cada colocación
(A,p,r) que muestra el color este k, y cada colocación (B,p′,r′) cuyo
color oeste no es k, añade ¬xA,p,r∨¬xB,p′,r′. Haz lo
mismo para A/C verticalmente y las otras dos adyacencias interiores. Eso es
todo lo que es la restricción 3: un gran montón de cláusulas binarias «estas dos
colocaciones no pueden ser ambas verdaderas».
El problema es que el montón es enorme. Las cláusulas de conflicto dominan, las
codificaciones de «a lo sumo una» añaden su propia explosión (el enfoque ingenuo
por pares es cuadrático; las codificaciones en escalera o por comandante lo
cambian por variables auxiliares), y el resultado es una fórmula con millones de
cláusulas cuya estructura le da casi nada que aprender a la búsqueda guiada por
conflictos. Esto se ha intentado desde 2008 y los solucionadores SAT completos
se atascan en el tablero completo; Blackwood, entre otros, informó de que SAT no
ayudaba. La codificación es limpia, el solucionador no es el cuello de botella,
lo es la instancia. Véase
codificaciones SAT y CSP para el
historial de bancos de pruebas y dónde los veredictos SAT todavía se ganan su
sitio como pruebas de imposibilidad en regiones pequeñas.
La visión por cobertura exacta es más pulcra, y esconde una trampa que hace
tropezar a casi todo el que recurre a los enlaces danzantes de Knuth.
Plantea 512 ítems: uno por celda («la celda c está rellena») y uno por pieza
(«la pieza p se usa»). Cada opción es una colocación (c,p,r), y cubre
exactamente dos ítems: la celda c y la pieza p. Un conjunto de opciones que
cubre cada ítem exactamente una vez es un tablero con cada celda rellena y cada
pieza usada una vez. Esa es una instancia de cobertura exacta limpia, y el
Algoritmo X de Knuth con enlaces danzantes resuelve la cobertura exacta a la
perfección.
Aquí está la trampa. Las restricciones 1 y 2 son condiciones de cubrir-una-vez,
que es exactamente lo que expresa la cobertura exacta. Pero la restricción 3, el
emparejamiento de colores, no es en absoluto una condición de cubrir-una-vez:
una arista compartida no se «usa una vez», se le «asigna un color en el que
ambos vecinos coinciden». El Algoritmo X sin más no tiene forma de decir esto.
La gente lo codifica, lo ejecuta y obtiene tableros con aristas discordantes, o
intenta injertar ítems adicionales y descubre que la semántica de cubrir-una-vez
se le resiste. Esta confusión concreta tiene su propia pregunta en el CS Stack
Exchange.
La solución es la propia extensión de Knuth, el Algoritmo C, para XCC, la
cobertura exacta con colores (TAOCP Volume 4B). Junto a los ítems primarios
(cubiertos exactamente una vez) añades ítems secundarios que pueden cubrirse
cualquier número de veces, siempre que todas las opciones que cubren un ítem
secundario dado le asignen el mismo color. Da a cada arista interior de la
cuadrícula un ítem secundario. Una colocación que expone el color k en una
arista compartida asigna el color k al ítem secundario de esa arista. Dos
colocaciones pueden entonces coexistir a ambos lados de la arista solo si la
colorean de forma idéntica, que es precisamente la restricción de emparejamiento
de aristas, ahora expresada de forma nativa.
Un esbozo 3×3: 9 ítems de celda y 9 ítems de pieza (primarios), más 12 ítems de
arista interior (secundarios, uno por cada unión horizontal o vertical). Las
colocaciones de la celda central tocan cada una cuatro ítems de arista
secundarios y deben concordar en color con los cuatro vecinos; las colocaciones
de una celda de esquina tocan dos. El Algoritmo C enhebra todo esto sin emitir
jamás un tablero discordante. Lo que los estudiantes pasan por alto:
la cobertura exacta por DLX para Eternity II necesita el Algoritmo C, no el
Algoritmo X. La página
cobertura exacta y enlaces danzantes
recorre la construcción XCC completa y dónde el DLX brilla de verdad (tableros
pequeños, recuento exhaustivo de soluciones) frente a dónde se atasca en el
16×16.
Dos encuadres más, útiles sobre todo como indicadores:
- Programación lineal entera. Reutiliza las variables SAT como enteros 0/1
xc,p,r. Las restricciones 1 y 2 se convierten en igualdades
∑p,rxc,p,r=1 por celda y ∑c,rxc,p,r=1 por pieza. El
emparejamiento de aristas pasa a ser, para cada arista interior y cada color
k, una condición de enlace que ata las colocaciones de color k de los dos
vecinos (una forma limpia: una nueva variable binaria de color de arista
ye,k con ∑kye,k=1, y las colocaciones de cada lado implicando
el y correspondiente). Es una PLE de factibilidad, sin objetivo, y la
relajación lineal es débil, de modo que la ramificación y acotación se comporta
muy parecido a la búsqueda SAT. Véase
relajaciones lineales.
- Clique máxima. Construye un grafo cuyos vértices son las colocaciones
legales y cuyas aristas unen cualesquiera dos colocaciones mutuamente
compatibles (celdas distintas, piezas distintas y concordancia en cualquier
arista compartida). Un tablero completo es una clique de tamaño 256. Es
elegante sobre el papel, pero el grafo es inmenso y los solucionadores de
clique no salen mejor parados; vale la pena conocerlo como reducción, no como
ataque práctico.
Las secciones anteriores terminan con una nota desalentadora: la codificación
es limpia, la instancia es el muro. Esa afirmación merecía una cifra, y
ponérsela la afinó en una dirección inesperada. El banco de pruebas es una
familia de tableros plantados: instancias con marco y colores equilibrados,
construidas a partir de una solución conocida, con cinco celdas de la solución
fijadas como pistas, puntuadas con la convención de aristas emparejadas sin
contar el borde exterior (una resolución completa a tamaño N vale
exactamente 2N(N−1) aristas emparejadas: 264 en 12×12, 480 en 16×16). Los
tableros plantados no son el Eternity II canónico; plausiblemente admiten
muchísimas soluciones donde el puzzle real está diseñado para tener en esencia
una. Lo que ofrecen es una escalera de instancias resolubles por construcción
que dos paradigmas de búsqueda distintos pueden atacar lado a lado.
En este banco, a 22 colores, una búsqueda en profundidad con reinicios que
solo coloca coincidencias exactas resuelve por completo cuatro de cinco
semillas 10×10 (la más rápida en 4 ms) y dos de cinco semillas 11×11, y luego
cero de cinco en 12×12 y cero en todos los tamaños superiores. El fallo no es
cuestión de presupuesto. La instancia 12×12 de semilla 1 puntúa 127 de 264
tras 20 segundos, tras 45 segundos y tras 120 segundos, mientras el número de
nodos visitados crece de 22 millones a 132 millones; una instancia 14×14
repta de 236 a 240 de 364 a lo largo del mismo estiramiento séxtuple del
presupuesto. La búsqueda no está convergiendo despacio; está clavada.
Entrega las instancias idénticas a CP-SAT con un modelo estructurado (una
variable entera por celda que recorre los identificadores de pieza bajo una
restricción AllDifferent, índices de pieza y rotación canalizados mediante
tablas Element hacia variables de color por lado, todo planteado como pregunta
de decisión) y el muro se mueve. Cuatro de las cinco instancias 12×12 caen en
31,7 a 88,1 segundos (la quinta agota el límite de 300 segundos), y una de las
dos instancias 13×13 probadas cae en 74 segundos, con cada tablero devuelto
reverificado de forma independiente: distinción de piezas, conformidad con las
pistas, recuento de aristas recalculado. Son resoluciones completas
verificadas de tableros que ninguna semilla de la DFS toca con ningún
presupuesto. El acantilado pertenece al paradigma de búsqueda, no a los
tableros.
La ronda original de esta medición corría sobre un generador que permitía 26
colores interiores, un ajuste que el banco empaquetado no puede producir (su
generador limita los colores interiores a 22, el recuento del puzzle real). A
26 colores el contraste era aún más nítido: CP-SAT resolvió por completo 25 de
25 instancias en los tamaños 10 a 14 con tiempos medianos de 0,10 a 0,84
segundos, medio segundo en 13×13, y terminó un 16×16 plantado en unos 15
segundos, mientras el acantilado de la DFS quedaba un peldaño más arriba, en
13×13. Esa misma ronda midió además la brecha de formulación en aislamiento:
sobre una instancia 12×12, un MIP genérico sobre binarias de colocación con
filas de suma uno, pasado por la ramificación y acotación de HiGHS, devolvió
11 de 264 aristas emparejadas tras 300 segundos; CP-SAT devolvió las 264
completas sobre la misma instancia en 0,42 segundos. Mismo problema, misma
máquina, unos tres órdenes de magnitud, y toda la diferencia está en cómo se
escribieron las restricciones.
Poner los dos ajustes lado a lado hace aflorar un segundo hallazgo: el
acantilado se mueve con el número de colores, para ambos paradigmas a la vez.
A 26 colores, la DFS muere en 13×13 y CP-SAT atraviesa un 16×16 plantado en
segundos. A 22 colores, la DFS muere un peldaño antes, en 12×12, y el propio
CP-SAT se ralentiza unos dos órdenes de magnitud entre 11×11 y 12×12 y
empieza a agotar sus límites desde 12×12 en adelante: las sondas 14×14 y
16×16 chocan ambas con un tope de 120 segundos. (Los peldaños grandes fueron
sondas de una sola semilla, y los tiempos de CP-SAT a 22 colores llevan algo
de inflación por un brazo DFS compartiendo la máquina, que ni de lejos
explica la brecha con las medianas por debajo del segundo a 26 colores.) Más
colores significa un tablero más restringido y una búsqueda más fácil para
todos; menos colores arrastra a ambos paradigmas hacia abajo a la vez, de
modo que las mediciones tomadas a 26 colores favorecen a todos los
solucionadores de la carrera. El 16×16 plantado en el que la sonda agotó su
tiempo merece verse, mostrado aquí como su solución construida:
16×16 plantado, 480/480.
Un testigo, contado diez veces
La ronda a 26 colores también probó diez familias heurísticas sobre el
acantilado, desde un rellenador ingenuo fila a fila hasta la propagación
AC-3 y la poda por déficit de Hall: seis resolvieron por completo el 12×12
y ninguna resolvió el 13×13. Diez solucionadores de acuerdo parecían diez
pruebas de que las instancias eran el muro. Era una sola. Los diez se
comprometen cronológicamente y con avidez sobre información local, así que
fallan juntos por la razón compartida, y el primer solucionador de un
paradigma de verdad distinto tumbó la conclusión en medio segundo. El
acuerdo de N solucionadores de la misma familia es un testigo con N voces.
Si viniste a preguntar si la teoría de la NP-completitud vuelve a esta instancia
demostrablemente difícil, la respuesta es que no lo hace, ni puede: las clases de
complejidad describen familias, y este tablero es una entrada fija con una
respuesta fija. El problema general de emparejamiento de aristas es NP-completo,
lo que pone un techo a lo que puede prometer cualquier solucionador a medida que
n crece, pero la dificultad que realmente sientes es empírica: un espacio de
10557 de ancho sobre un conjunto de soluciones casi vacío. Cada
codificación de arriba captura fielmente el puzzle, y en el 16×16 completo
ninguna lo vuelve fácil; pero el acantilado de los tableros plantados muestra
que la elección del formalismo no tiene nada de neutral por debajo de esa
escala, donde el mismo tablero puede ser inalcanzable para un paradigma y una
resolución de un minuto para otro. Una
vez codificado el tablero, la palanca que queda es la
consistencia de arco y un orden de
búsqueda inteligente, que es donde retoma el resto de esta sección.