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.
Reproducirprosa — no hay ningún cálculo detrás de esta página·relanza la búsqueda (Ver más abajo)
Complejidad
Tiempo
AC-3 O(e·d³) · AC-2001 O(e·d²) (optimal for arc revision)
Espacio
AC-3 O(e) · AC-2001 O(e·d)
On the 16×16 board e = 960 directed interior arcs and d ≈ 764 candidate tuples per cell, so the worst-case gap is ~4×10¹¹ vs ~5.6×10⁸ checks, but real propagations touch only a few cells, and the cost is paid at every search node.
En Eternity II, un backtracker gasta la mayor parte de su esfuerzo no en colocar
piezas sino en descartarlas. Puesto que ninguna celda queda nunca
forzada (toda posición interior conserva decenas
de candidatos vivos hasta muy adentro de la búsqueda), la única palanca
disponible es reducir esas listas de candidatos con la mayor dureza y el menor
coste posibles. La consistencia de arco es la maquinaria estándar para ello, y
arrastra tras de sí medio siglo de publicaciones.
Asignemos a cada celda vacía un dominio: el conjunto de candidatos
pieza-y-rotación aún permitidos en ese lugar. En el puzzle completo, eso arranca
en unas 764 tuplas por celda interior. El forward checking es la disciplina
de un solo paso: cuando se coloca una pieza, se elimina de todos los demás
dominios y se elimina todo candidato que choque con las aristas recién
expuestas. Es barato, y todo solucionador serio hace al menos esto.
La consistencia de arco exige más. Para cada par de celdas adyacentes, todo
candidato de un dominio debe tener al menos un compañero compatible en el otro,
un soporte. Cuando una eliminación, en cualquier parte, deja un candidato sin
soporte, ese candidato desaparece a su vez, y la comprobación se propaga hacia
afuera hasta que no queda nada más por retirar. Para el emparejamiento de aristas
esto significa exactamente: "una pieza solo puede permanecer en una celda si
cada celda vecina puede seguir respondiendo a sus colores".
El AC-3 de Alan Mackworth (1977) es la forma de grano grueso de alcanzar ese
punto fijo: se mantiene una cola de arcos orientados, se revisa un arco a la vez
(se recorre un dominio, se eliminan los candidatos sin soporte), y cada vez que
un dominio se encoge, se reencolan los arcos que apuntan hacia él. Es corto,
correcto y fácil de hacer incremental dentro de una búsqueda, y por eso sigue
siendo la opción por defecto en todas partes. En el peor caso cuesta O(ed3)
para e arcos y un tamaño de dominio d; en el tablero de 16×16, e vale
e=960 (las 480 adyacencias interiores, en ambos sentidos) y d≈764.
Su defecto conocido: cada revisión busca los soportes desde cero, de modo que el
mismo soporte se redescubre miles de veces a medida que la búsqueda se sumerge y
retrocede.
Las descripciones de algoritmos de lista de trabajo suenan todas iguales; es al
ver a uno estabilizarse cuando todo encaja. Abajo está AC-3 sobre una versión
en miniatura del problema: un tablero de 4×4, 3 colores de arista, cada celda
arrancando con sus 64 candidatos (16 piezas × 4 rotaciones). Coloca una pieza y
sigue la cola: qué arcos entran en ella, qué elimina cada revisión, cómo una
eliminación rearma los arcos que apuntan al dominio encogido, y cómo se apaga la
onda. Los contadores comparan el trabajo de AC-3 con el del bucle ingenuo de
punto fijo (AC-1: rebarrer cada arco hasta que una pasada completa quede limpia)
ejecutándose sobre exactamente las mismas posiciones.
▶Interactivo: mira a AC-3 estabilizarse hacia un punto fijoExplorar →
Observa cómo AC-3 se propaga — un arco a la vez
Un juguete de encaje de bordes de 4×4 con 3 colores: cada celda arranca con sus 64 candidatos (16 piezas × 4 rotaciones). Coloca una pieza y observa la lista de trabajo: los arcos que apuntan a la celda modificada entran en la cola, cada revisión elimina los candidatos sin soporte, y cada eliminación reencola los arcos que apuntan al dominio reducido — hasta que la cola se vacía.
El número = candidatos que quedan en el dominio de la celda. Las flechas = arcos que esperan en la cola (la flecha gruesa es el arco que se está revisando).
0/16 colocadas0 arcos en cola
AC-3 (lista de trabajo)
0revisiones de arcos
0comprobaciones de soporte
rebarrido ingenuo (AC-1)
0revisiones de arcos
0comprobaciones de soporte
Tablero nuevo: cada celda conserva sus 64 candidatos. Todavía no ha cambiado nada, así que la cola está vacía.
Los contadores son lo esencial: AC-3 solo vuelve a visitar los arcos cuyo dominio del otro extremo realmente cambió, mientras que el bucle ingenuo de punto fijo rebarre los 48 arcos hasta que una pasada completa no cambia nada. Las mismas eliminaciones, un trabajo radicalmente distinto — y AC-2001 recortaría aún más las comprobaciones de soporte al recordar dónde se detuvo cada búsqueda.
Dos cosas merecen atención. Las primeras colocaciones apenas propagan: un anillo
de vecinas se encoge y la onda se detiene, porque el segundo anillo aún
encuentra soportes para los tres colores entre los supervivientes. Las
colocaciones tardías se propagan mucho más lejos: los dominios están apretados, y
una sola eliminación deja aislados candidatos a dos y tres celdas de distancia.
Ese es exactamente el comportamiento en el puzzle real: la consistencia de arco
se gana el pan en el final de partida, no en la apertura.
La misma ejecución, en palabras. Esto es todo AC-3:
Inicio. Cada celda tiene un dominio de 64 candidatos. La cola de arcos
está vacía; sin ninguna eliminación aún, no hay nada que comprobar.
Una pieza aterriza en B2. Su dominio se colapsa al único candidato
colocado. Todo arco dirigido hacia B2 entra en la cola, uno por vecina:
aquí (B1→B2), (C2→B2), (B3→B2), (A2→B2). Nada más lo hace: ningún otro
dominio cambió, así que ningún otro arco pudo perder un soporte.
Se desencola un arco, se revisa. Tomemos (B1→B2): se recorren los 64
candidatos de B1 y, para cada uno, se busca en el dominio de B2 un compañero
compatible, un soporte. B2 tiene ahora una sola pieza, así que solo
sobreviven los candidatos cuya arista sur coincide con su color norte: en
torno a un tercio. El resto se elimina.
Las eliminaciones rearman arcos. El dominio de B1 se encogió, así que los
candidatos en otros lugares que se apoyaban en los eliminados pueden quedar
aislados: todo arco que apunta a B1 reentra en la cola, salvo el que viene de
B2 y acaba de dispararse. Esta es la onda.
Sin eliminación, sin reencolado. Cuando una revisión no retira nada, el
arco simplemente se descarta. Al principio de la partida el segundo anillo
casi siempre sobrevive intacto, y la cola se vacía en un puñado de revisiones.
Punto fijo. La cola está vacía: cada candidato, en todas partes, tiene un
soporte en cada dominio vecino. Ningún orden de procesamiento cambia este
estado final: el punto fijo es único, y la disciplina de cola solo cambia con
qué rapidez lo alcanzas.
La comparación con AC-1 en la demo es todo el argumento a favor de la lista de
trabajo: el bucle ingenuo rerevisa los 48 arcos por barrido hasta que un barrido
queda limpio, haciendo las mismas eliminaciones a costa de varias veces más
comprobaciones, y la brecha se ensancha a medida que el tablero crece.
La literatura pasó dos décadas corrigiendo esa redundancia. AC-4 (Mohr &
Henderson 1986) cuenta los soportes explícitamente: tiempo óptimo O(ed2),
pero O(ed2) de memoria y una penosa restauración de estado al retroceder.
AC-6 y AC-7 (Bessière; Bessière, Freuder & Régin) almacenan los soportes de
forma perezosa y explotan la bidireccionalidad, manteniendo el tiempo óptimo con
O(ed) de espacio a costa de una contabilidad de grano fino.
La versión que vale la pena conocer hoy es AC-2001/AC-3.1, hallada de forma
independiente por Bessière & Régin y por Zhang & Yap en 2001: se conserva el
bucle simple de AC-3, pero se recuerda para cada par candidato-arco el último
soporte encontrado, se comprueba que sigue vivo antes de volver a buscar, y se
reanuda el recorrido donde se detuvo en lugar de desde cero. Ese único entero por
par entrega la cota óptima O(ed2) con solo O(ed) de memoria; en este
puzzle eso son unos 367 000 enteros pequeños, despreciable. El estudio de revista
de 2005 mide entre 1,5 y 9 veces menos CPU que AC-3 en una búsqueda con
consistencia de arco mantenida, y muestra que la ventaja sobre AC-6 crece con
el tamaño del dominio al otro lado del arco. Eternity II tiene dominios enormes a
ambos lados de cada arco, lo que hace de AC-2001 la elección de manual.
La consistencia de arco comprueba pares de celdas. El siguiente peldaño, la
consistencia de camino, comprueba tripletes: retira todo par de asignaciones
que ninguna tercera celda pueda soportar, propagando una condición mucho más
fuerte. Encoge el árbol de búsqueda enormemente, y la comunidad midió
exactamente cuánto, y exactamente por qué nadie la usa. En marzo de 2008, Geoff
ejecutó toda la escalera sobre los puzzles para principiantes de Brendan Owen
(msg 4827):
En el de 6×6, la simple consistencia nodal deja un árbol de búsqueda de más de
40 000 nodos. La consistencia de camino-1 parcial lo baja a unos 10 000. La
consistencia de camino-2 parcial lo baja a 138 nodos, el mínimo estricto
necesario para recorrer las ocho soluciones. Pero el tiempo de ejecución pasa
de 0,25 segundos a más de 10 segundos.
En el de 8×8, el trato empeora. La consistencia de arco por sí sola lo resuelve
en menos de 6 millones de nodos y unos 36 segundos. Añadir un
preprocesamiento de camino-1 recorta el árbol a aproximadamente 1 millón de
nodos pero cuesta unos 14 minutos de preprocesamiento; el preprocesamiento
de camino-2 seguía corriendo tras 7 horas.
El patrón es inequívoco: cada nivel más fuerte de consistencia recorta
realmente el árbol en varios órdenes de magnitud, y cada uno cuesta más de lo que
ahorra. La propia conclusión de Geoff fue que la consistencia de camino "no tiene
sencillamente un efecto coste-beneficio positivo" en este puzzle. Eso es podar
frente a velocidad enunciado en el lenguaje de un
algoritmo real: la poda es genuina y grande, pero aquí la maquinaria para
calcularla es más cara que la búsqueda que elimina, y por eso los motores
recordistas se detienen en la consistencia de arco (o por debajo) y dedican el
tiempo ahorrado a colocaciones en bruto.
La contabilidad, con e el número de arcos orientados y d el tamaño máximo de
dominio:
AC-3 corre en O(ed3) de tiempo en el peor caso: cada arco puede
reencolarse hasta d veces (una por eliminación en su dominio lejano), y cada
revisión cuesta hasta d2 comprobaciones de soporte. Su memoria de trabajo se
reduce a la cola, O(e).
AC-2001 corre en O(ed2) de tiempo, lo que es óptimo para cualquier
algoritmo basado en la revisión de arcos: hay ed pares candidato–arco y cada
uno puede necesitar que su soporte se recorra una vez sobre un dominio de tamaño
d. El precio es la tabla del último soporte: un entero por par candidato–arco,
O(ed) de espacio.
A la escala de Eternity II, esos símbolos valen: e=960 (480 adyacencias
interiores, en ambos sentidos) y d≈764 tuplas candidatas por celda
interior. Así que las cotas del peor caso se sitúan cerca de
ed3≈4×1011 comprobaciones elementales para AC-3 frente a
ed2≈5.6×108 para AC-2001, tres órdenes de magnitud de
diferencia sobre el papel. Los peores casos son pesimistas (las propagaciones
reales tocan unas pocas celdas, como muestra la demo de arriba), pero esa razón
es por la que la literatura señala la cota de AC-3 como la cosa a corregir, y la
corrección solo cuesta O(ed) enteros de memoria. La trampa en este puzzle no
es el coste de propagación por nodo; es que dentro de una búsqueda ese coste se
paga en cada nodo, millones de veces por segundo, y por eso los factores
constantes y el comportamiento de la caché acaban importando tanto como el
exponente de d.
En el motor de este proyecto (medido aquí; no replicado de forma
independiente):
Un backtracker simple que propaga AC-3 junto con el
filtro de emparejamiento por color
alcanza 449 de 480 aristas en el puzzle canónico en unos 44 segundos en un
solo hilo, alrededor de 2,5 segundos en 8 núcleos.
La mejor aceleración algorítmica hallada dentro del propio AC-3 fue mundana:
una tabla precalculada de qué rotaciones de la misma pieza comparten colores de
arista, para que las revisiones dejen de rederivarla, con un valor de 2,9× de
ganancia de rendimiento en el banco de referencia del motor.
La parte no construida: AC-2001 se recomendó dos veces en las notas de este
proyecto y nunca se construyó realmente, de modo que su ganancia proyectada de
2 a 5× aquí es una lectura de la literatura, no una medición. Y la creencia de
que AC-3 dominaba el perfil de ejecución nunca la confirmó un profiler. Medir
antes de portar.
La consistencia de arco supone que cada arista debe coincidir perfectamente. Los
motores recordistas no lo hacen: las búsquedas al estilo
Blackwood permiten un
presupuesto de desajustes deliberados a grandes profundidades, y bajo ese régimen
la consistencia de arco es incorrecta: poda tableros que un desajuste
autorizado haría perfectamente legales. En el motor de este proyecto, toda la
familia AC se desactiva en las ejecuciones tolerantes a rupturas, exactamente por
esa razón. El único propagador fuerte que sobrevive al régimen de desajuste es el
all-different a nivel de pieza; véase el filtro de
Régin.
Para cualquier búsqueda de emparejamiento exacto, la consistencia de arco es
obligatoria y barata: es la diferencia entre un backtracker que patina y uno que
alcanza los 440. El forward checking por sí solo deja podas sobre la mesa; AC-3
las recoge; AC-2001 recoge las mismas por menos CPU, si primero verificas que la
propagación es donde de verdad se van tus ciclos. Para la caza de récords
tolerante a desajustes, déjalo fuera; la corrección va primero.