Una sola pregunta, planteada con cuidado: entre los backtrackers en profundidad para Eternity II, ¿qué aporta realmente cada orden de relleno, cada heurística y el mecanismo de ruptura? Una familia de backtrackers escritos desde cero, separados cada uno por un único cambio, ejecutados sobre las mismas diez variantes con esquinas fijadas, en un solo núcleo, durante sesenta segundos.
Todo solucionador de Eternity II poseedor de un récord (Blackwood, Verhaard,
McGavin) es un backtracker en profundidad. Lo que los distingue de un backtracker
del primer trabajo de la semana no es su naturaleza, sino un puñado de decisiones:
el orden en que rellenan las celdas, la anticipación que aplican y el hecho de
dejar o no que una arista rompa. Este estudio desmonta esas decisiones.
Construye desde cero una familia de backtrackers en profundidad, cada uno
separado de su vecino por un único cambio, y los ejecuta a todos sobre las mismas
diez variantes con esquinas fijadas del puzzle oficial, en un solo núcleo,
sesenta segundos por ejecución. La puntuación máxima es de 480 aristas casadas.
El objetivo no es ganar. La variante más fuerte que aquí se presenta ronda de
media los 430 justos, muy por debajo de los 464 de la comunidad sobre estas cinco
pistas, porque sesenta segundos en un núcleo son apenas una fracción ínfima del
cómputo que exigieron los récords. El objetivo es aislar lo que vale cada idea
cambiando una sola cosa a la vez y midiendo el resultado con el mismo
solucionador canónico de puntuación para cada tablero.
Los diez puzzles de partida
Cada motor se ejecuta sobre estas diez instancias: el puzzle oficial de 256 piezas con ocho celdas fijadas (las cinco pistas oficiales y tres esquinas), dispuestas de forma distinta cada vez. Solo se muestran las celdas fijadas; el resto es lo que la búsqueda debe rellenar.
Cuatro familias, dispuestas de modo que los vecinos difieran en una sola decisión.
Baseline es el backtracker más crudo posible, acompañado de un gemelo
especializado a mano que pone precio al coste de la ingeniería de bajo nivel.
Path order fija todo salvo la secuencia en que se rellenan las celdas.
Heuristic fija el orden y añade un propagador cada vez. Break es el eje de
élite: el mecanismo de ruptura de arista con umbral de profundidad sobre el que se
apoyan los récords. Los motores récord de la comunidad, el C de McGavin y el C# de
Blackwood, son ellos mismos backtrackers de ruptura, de modo que ocupan su lugar
en la familia break, y no en una categoría aparte. De quién es el código de un
motor sigue siendo cuestión de etiquetado, no de color. Ambos aparecen en el
clasificatorio con su puntuación de esquinas fijadas, marcados con una insignia
allí donde se derrumban, y de nuevo sobre una rejilla sin fijación más abajo,
donde funcionan tal como fueron diseñados.
El ranking — puntuación media por variante
Puntuación media (aristas coincidentes) sobre diez variantes con esquinas fijadas del puzzle oficial, un solo núcleo, 60 s por ejecución. El color marca la familia, nombrada en cada barra: el color nunca es la única señal. El C de McGavin y el C# de Blackwood también figuran aquí, en la puntuación que su orden de recorrido fijo alcanza antes de que una esquina fijada lo bloquee, etiquetados donde se atascan; la sección de dos rejillas más abajo los muestra funcionando correctamente una vez retiradas las esquinas.
Dibujando…
referenciaorden de recorridoheurísticarupturas
Hasta dónde llegó cada búsqueda, y a qué velocidad
La profundidad máxima alcanzada por cada variante, de 256. Los backtrackers estrictos se estancan en torno a 200 (el más rápido, NAIVE-CODEGEN, llega a 216); la familia de rupturas llega bastante más lejos, de 243 a 245, porque puede atravesar una arista localmente incoincidente en lugar de retroceder. La tabla de abajo añade el rendimiento medio, en nodos de búsqueda por segundo, que nunca se compara entre familias porque un nodo con propagación no es un nodo ingenuo.
Dibujando…
referenciaorden de recorridoheurísticarupturas
variante
familia
profundidad máx. alcanzada (de 256)
rendimiento medio
BREAK-1
rupturas
245
4.6M
BREAK-2
rupturas
245
5.2M
VERHAARD-SLIP
rupturas
243
2.3M
NAIVE-CLEAN
referencia
208
32.4M
ROWMAJOR
orden de recorrido
208
31.5M
NAIVE-CODEGEN
referencia
216
44.9M
VERHAARD-COMB
orden de recorrido
197
23.3M
BLACKWOOD-COMB-BREAK
rupturas
197
17.9M
BORDER-MRV
heurística
194
6K
MRV-RARE
heurística
194
7K
MRV-FC
heurística
193
7K
MRV-AC3
heurística
192
8K
MRV-GACOLOR
heurística
192
8K
ROWMAJOR-BOTTOMUP
orden de recorrido
201
273K
SPIRAL-IN
orden de recorrido
79
13.3M
BLACKWOOD-CS
rupturas
47
—
BORDER-FIRST
orden de recorrido
77
365K
SPIRAL-OUT
orden de recorrido
31
20.1M
MCGAVIN-C
rupturas
21
—
Qué se apila sobre qué
Cada variante es un backtracking en profundidad declarado como un único cambio respecto a su variante padre. Esta tabla se genera a partir del registro del motor, así que siempre coincide con el código que se ejecutó.
variante
familia
el cambio que añade sobre su padre
rupturas
media
prof.
NAIVE-CLEAN
referencia
the rawest depth-first backtracker: row-major, no heuristics, no breaks
estricto
376.8
208
NAIVE-CODEGEN
referencia
same algorithm, a 16×16-specialised unrolled hot loop
estricto
372.1
216
ROWMAJOR
orden de recorrido
the row-major control (same as NAIVE-CLEAN, named for the path study)
estricto
376.6
208
ROWMAJOR-BOTTOMUP
orden de recorrido
fill bottom-to-top instead of top-to-bottom (Blackwood's scan direction)
estricto
225.9
201
SPIRAL-IN
orden de recorrido
fill the outer ring inward instead of row-major (the cloister spiral)
estricto
80.2
79
SPIRAL-OUT
orden de recorrido
spiral from the centre outward instead of inward
estricto
24.5
31
BORDER-FIRST
orden de recorrido
fill the whole border ring first, then the interior
estricto
66.6
77
VERHAARD-COMB
orden de recorrido
a horizontal band then vertical teeth (Verhaard's COMB order)
estricto
357
197
BORDER-MRV
heurística
choose the most-constrained empty cell dynamically (MRV) instead of a fixed order
estricto
324.1
194
MRV-RARE
heurística
try pieces carrying globally-rare colours first (Selby/Riordan rarity)
estricto
323.7
194
MRV-FC
heurística
add forward-checking: reject a placement that empties any neighbour's domain
estricto
322.2
193
MRV-AC3
heurística
extend the look-ahead to arc-consistency (AC-3) over the frontier
estricto
320.6
192
MRV-GACOLOR
heurística
add Régin per-colour all-different reasoning on the remaining supply
estricto
320.6
192
BREAK-1
rupturas
allow ≤1 broken edge per cell on a depth schedule (Blackwood's ladder)
break (≤1/cell)
431.3
245
BREAK-2
rupturas
allow up to 2 broken edges at one cell (double-breaks the community 460s use)
break (≤2/cell)
428.5
245
VERHAARD-SLIP
rupturas
Verhaard's interior edge-slip schedule instead of Blackwood's ladder
break (≤1/cell)
399.3
243
BLACKWOOD-COMB-BREAK
rupturas
run the Blackwood break ladder on Verhaard's COMB fill order
break (≤1/cell)
356.4
197
MCGAVIN-C
rupturas
the community's fastest DFS, run here; it collapses on our corner pins
break (≤1/cell)
13
21
BLACKWOOD-CS
rupturas
Blackwood's C# record engine, run here; it stalls on our pins
break (≤1/cell)
75
47
Los motores récord de la comunidad, ejecutados aquí
El C de McGavin y el C# de Blackwood se compilan y ejecutan en la misma máquina. Ninguno puede afrontar la rejilla con esquinas fijadas de arriba: cada uno está construido en torno a una configuración de pistas concreta, de modo que una esquina fijada que su recorrido nunca alcanza pronto lo bloquea de inmediato. Los dos paneles de abajo muestran ambas caras de esto. Primero, las esquinas fijadas del estudio los hacen colapsar. Después, en una rejilla equitativa con solo la única pista central obligatoria, funcionan según su diseño.
Mismo presupuesto, mismo núcleo: 60 s desde cero
Los mismos motores sobre las piezas oficiales con solo la pista central obligatoria fijada, de modo que nada se bloquea en una esquina arbitraria. Cada puntuación se recalcula canónicamente a partir del tablero del propio motor, un solo núcleo, 60 segundos, arranque en frío. Es una comparación con presupuesto controlado, condiciones idénticas para los cuatro, no un concurso de fuerza máxima: muestra hasta dónde llega cada uno en un minuto de núcleo, no el techo de cada motor. Esa única pista fijada aún pesa: Blackwood obtiene aquí 214, muy por debajo de los 454 que alcanza en su página de solucionador, donde su búsqueda coloca cada pieza libremente en lugar de comprometer la pista central de entrada (un tablero legal aun así, ya que solo la pista central obliga, pero una búsqueda más fácil). El marcador tenue sobre los dos motores externos es su mejor puntuación documentada, que exige largas ejecuciones multinúcleo inalcanzables con un presupuesto de un minuto. Lo que la rejilla sí muestra es que los cuatro funcionan correctamente una vez retiradas las esquinas que rompen un recorrido fijo, algo que la rejilla fijada negaba a los dos motores externos.
Dibujando…
La línea discontinua en cada motor externo marca su mejor puntuación documentada (Blackwood ~470, McGavin 469): el puzzle oficial nunca se ha resuelto, así que ningún motor alcanza un 480 genuino. Estos récords exigen largas ejecuciones multinúcleo inalcanzables con un presupuesto de un minuto en un solo núcleo; la propia ejecución más larga de Blackwood en esta misma máquina ya se recalculó a 454. El rendimiento se etiqueta por motor (McGavin cuenta piezas, los demás nodos de búsqueda) y nunca se compara entre motores, porque las unidades no miden el mismo trabajo. McGavin se compila con las propias opciones ARM de su autor (ajuste nativo y optimización en el enlazado).
motor
media
profundidad alcanzada
rendimiento
McGavin (C)
392
211
85M tiles/s
break-2 (ours)
344
192
33M search-nodes/s
Verhaard (our reimpl)
286
172
8k search-nodes/s
Blackwood (C#)
214
119
9M search-nodes/s
Con esquinas fijadas: el colapso, como puntuación
Los dos mismos motores externos sobre la configuración con esquinas fijadas del estudio. La barra es la puntuación canónica que su tablero alcanza antes de que el recorrido fijo los deje varados; la barra tenue detrás es lo que el mismo motor alcanza sin esquinas fijadas. La diferencia es el colapso.
MCGAVIN-C(C)con esquinas fijadas 13 · solo pista central 392
depth 21
BLACKWOOD-CS(C#)con esquinas fijadas 75 · solo pista central 214
depth 47
El colapso por las esquinas fijadas. Adding the study's three corner pins collapses its fixed scan path to depth 21 (canonical score 13), confirmed on 2 pinned variants: the scan never reaches a corner early, so a pinned corner dead-ends it at once.
El colapso por las esquinas fijadas. It hardcodes its piece set and scan, so it cannot express the study's arbitrary corner pins; the matching constrained test is the five official clues, where its heuristic phase thrashes to depth 47 (canonical score 75) in 60 s.
El orden de recorrido es la mayor palanca gratuita, y el orden equivocado es
catastrófico. Un simple recorrido fila por fila promedia 377; un relleno
estricto de borde primero o en espiral, sin heurística que lo rescate, se estanca
cerca de 67. Mismo motor, mismo presupuesto, una oscilación de más de 300 puntos
debida al solo orden de relleno.
La heurística de la celda más restringida (MRV) es lo que hace viable el borde
primero. Eleva un borde primero estancado desde los sesenta hasta una media de
324, a un coste de tres órdenes de magnitud en el rendimiento de nodos. El
rendimiento de nodos y la puntuación son dos ejes distintos, una distinción sobre
la que el estudio vuelve de principio a fin.
Más propagación no compró más puntuación con este presupuesto. El
forward-checking, la arco-consistencia y el razonamiento por color aterrizan a un
punto unos de otros (322, 321, 321), una brecha muy dentro de la dispersión de
una ejecución a otra, de modo que una anticipación más pesada ni ayudó ni
perjudicó claramente. Gasta los sesenta segundos en demostrar regiones pequeñas
en lugar de descender más profundo.
Las rupturas descienden más profundo que cualquier búsqueda estricta. Los
backtrackers estrictos se topan con un techo en los 200 justos (el más rápido,
NAIVE-CODEGEN, en 216); un presupuesto de ruptura con umbral de profundidad
supera 245 y promedia los 430 justos, porque puede forzar el paso más allá de una
arista localmente incasable en lugar de retroceder para salir de ella. El factor
decisivo es el calendario de las rupturas: desbloquear las rupturas demasiado
pronto (la escalera de Verhaard, media 399) puntúa muy por debajo de la escalera
más tardía de Blackwood (media 431). Elevar el tope por celda de uno a dos no
ayudó con este presupuesto, un resultado nulo reportado como medido.
Cada uno de estos puntos tiene su propia página: cómo se construye el motor y qué
significa cada estadística registrada está en la
página de método, y las
comparaciones de recorrido, heurística y ruptura se desarrollan en la
página de resultados.
Cada tablero se vuelve a puntuar con un único solucionador canónico de puntuación,
y no se da por buena la puntuación autodeclarada de ningún motor. El rendimiento
se reporta en nodos de búsqueda por segundo y nunca se compara de una familia a
otra, porque un nodo que ejecuta una arco-consistencia completa no es la misma
unidad de trabajo que una colocación ingenua. La profundidad es la colocación más
profunda que alcanzó una variante, sobre 256.
El número de rupturas merece una definición precisa, porque es fácil enunciarlo de
forma vaga. La puntuación de un tablero es el número de sus aristas interiores
casadas, y la brecha 480 − score es el déficit total de aristas no casadas del
tablero. Sobre un tablero completado, cada arista no casada es una ruptura
genuina, de modo que allí la puntuación vale exactamente 480 − #breaks. Sesenta
segundos rara vez bastan para rellenar el tablero, sin embargo, de manera que la
mayoría de los tableros de las variantes de ruptura aquí presentados son parciales,
y su déficit está dominado por aristas simplemente aún vacías más que rotas. Este
estudio reporta por tanto el verdadero número de rupturas, es decir, los
desapareamientos interiores que la búsqueda comprometió efectivamente bajo su
presupuesto, seguidos por la propia búsqueda en lugar de inferidos de la
puntuación. Ese número se mantiene pequeño incluso cuando el déficit es grande.
Cada tablero lleva una .url bucas que se abre en el visualizador, de
modo que tanto la puntuación como las aristas rotas pueden verificarse
directamente.
Todo el aparato (el espacio de trabajo del motor, las diez variantes, los
resultados por ejecución versionados y los scripts de la rejilla) reside bajo el
directorio de respaldo
del estudio, y just experiments dfs-study reconstruye el motor y relanza toda la
rejilla.