El orden en que un algoritmo de backtracking visita las 256 celdas es su única libertad: no cuesta nada en tiempo de ejecución y mueve el tamaño del árbol de búsqueda en varios órdenes de magnitud. Veinte años de ciencia comunitaria, desde las guerras entre fijo y dinámico y las carreras de estrategias hasta el cuadrado mágico 10×16 y la búsqueda en peine de Verhaard, responden todos a la misma pregunta: ¿qué camino a través del tablero es el más barato?
Un algoritmo de backtracking apenas tiene libertad. Las piezas están dadas, la
regla de emparejamiento está dada, el tablero está dado. Lo único que depende
enteramente de ti es el orden de relleno: la secuencia en que se rellenan las
256 celdas. Parece un detalle (la búsqueda es exhaustiva de cualquier modo), y
en realidad es la decisión de mayor apalancamiento de todo el solucionador.
Brendan Owen lo dijo sin rodeos en 2007: «Uno de los mayores ahorros de conteo
de nodos que puedes lograr consiste en elegir un buen orden de búsqueda»
(msg 2714). El mismo puzzle,
recorrido en un orden distinto, puede costar diez órdenes de magnitud más de
nodos. Y la elección es gratuita, decidida antes de colocar la primera pieza.
Por eso la lista de correo lo debatió durante veinte años. El primer gran
debate, en el verano de 2007, fue fijo contra dinámico: los veteranos de
Eternity I abogaban por elegir dinámicamente, en cada paso, la celda más
restringida, la heurística CSP clásica
(msg 2392). Los empiristas
respondieron con conteos de nodos: los mejores resultados venían de caminos
fijos, precalculados, y el veredicto de Owen fue que «un barrido por líneas
después de colocar la pieza pista parece lo mejor»
(msg 2425). Un año más tarde,
cuando le preguntaron por qué nadie se molestaba con la colocación
completamente dinámica, istarinz comprimió la mitad de ingeniería de la
respuesta en una palabra, velocidad: un camino fijo mantiene el bucle interno
sin ramificaciones y guiado por tablas
(msg 5860). La mitad teórica
tardó más, y es el tema de esta página.
Una idea que subyace a todo lo demás: la colocación de una pieza solo se
comprueba jamás contra los vecinos ya presentes en el tablero. Una cuadrícula
16×16 tiene exactamente 480 uniones internas, y todo orden de relleno completo
(barrido por líneas, espiral, lo que sea) acaba comprobando las 480. El orden
solo cambia la planificación: qué uniones se pagan temprano, mientras el árbol
sigue siendo estrecho, y cuáles se posponen hasta donde es ancho. Una celda que
llega con dos vecinos ya colocados admite pocas piezas candidatas; una celda que
llega sin ninguno las admite casi todas y no poda nada. Los buenos órdenes son
los que alimentan a la búsqueda con una dieta constante de celdas restringidas,
que es exactamente lo que hace un barrido por líneas: tras la primera fila, casi
cada celda nueva toca una pieza a su izquierda y una pieza debajo.
Owen lo convirtió en un método. Para un orden fijo, los nodos a la profundidad
D son (en esperanza) el número de formas de teselar la forma que el orden ha
construido a la profundidad D. Cualquier orden candidato puede por tanto
puntuarse, forma a forma, sin ejecutarlo. Su conclusión, extraída de hacerlo de
manera exhaustiva: las formas que dominan el total son las de tamaños 121 a 185,
y las mejores formas en esa ventana crítica «forman un simple orden de barrido
por líneas» (msg 2714). Toda la
maquinaria, probabilidades de unión incluidas, se convirtió en la
teoría compleja; esta página muestra a qué se
parecen sus respuestas en la práctica.
El cuaderno de laboratorio del proyecto pone números a la dieta misma.
Llamemos k al número de lados vecinos ya colocados que una celda presenta
cuando la búsqueda la alcanza. Una ley de campo medio dice que la celda
debería admitir unas 4Rpk colocaciones candidatas, donde R es el
número de piezas aún en mano y p≈0,048 es la probabilidad media,
en E2, de que un lado empareje con un color. Al comienzo del relleno
interior eso predice unos 38 candidatos para una celda k=1, 1,8 para
k=2, 0,09 para k=3 y 0,004 para k=4. Una enumeración exacta contra el
juego real de 256 piezas (40 ensayos sembrados por configuración) cae
dentro del 20 a 40% de esas predicciones y confirma los tres regímenes que
dibujan: las celdas k=1 son en esencia siempre rellenables; las celdas
k=2 cruzan el 50% de celdas muertas en algún punto entre el 50 y el 62%
de relleno del tablero; y las celdas con tres o más vecinos colocados están
muertas en el 87 a 100% de los ensayos a cualquier nivel de relleno,
incluida la primera colocación interior. (La ley es una idealización de
campo medio validada para las estadísticas de color de Eternity II, una
sola instancia; no es una afirmación sobre el emparejamiento de aristas en
general.)
Leída como regla de diseño: un buen orden es aquel cuya frontera presenta a
cada celda nueva exactamente dos vecinos colocados, suficientes para podar,
pocos para sobrevivir. El barrido por filas lo hace por construcción, un
k=2 constante tras la primera fila; cualquier orden cuya frontera
desarrolle bolsas cóncavas de tres lados paga celdas casi seguramente
muertas, esté como esté de lleno el tablero. Los mismos regímenes miden
también lo que compra el propio backtracking. Sin backtracking alguno, un
relleno voraz aleatorio se atasca dentro del primer 5 a 12% del tablero use
el recorrido que use: sobre 8 semillas por orden, el atasco mediano llegó
en el paso 15 para fila-mayor, 13 para un recorrido diagonal y 15 para una
espiral (el recorrido diagonal osciló entre 4 y 32), y ninguna de las 24 ejecuciones llegó más lejos.
Cualquier recorrido fabrica una esquina cóncava fatal en un puñado de
colocaciones; ese número ilustra la geometría, no es un banco de pruebas de
solucionadores.
El laboratorio de abajo hace visible la planificación. Anima la secuencia de
visita de cuatro órdenes predefinidos sobre una cuadrícula 16×16 y traza, en
directo, el conteo de restricciones (cuántos vecinos ya colocados tiene cada
celda nueva) junto con el acumulado de uniones recogidas. (Muestra la
geometría; para hacer correr resoluciones reales a lo largo de caminos que
tú mismo dibujas, el complemento práctico es el
campo de juego de caminos de búsqueda.)
▶Interactivo: orden de relleno contra ramificaciónExplorar →
Las carreras de estrategias. A finales de 2007 la pregunta se había vuelto
cuantitativa: puzzles de referencia compartidos, conteos de nodos en búsqueda
completa y un marcador público. La cima del estilo fue el algoritmo
completamente automático de búsqueda de estrategias de doc_s_smith, que diseñó
un orden de búsqueda que agotó el benchmark de tamaño 14 hints15_2 en 89.794
nodos, batiendo los 141.628 ajustados a mano de Txibilis: la máquina sobre el
humano (msg 2896). Txibilis
contraatacó en dos días con 85.729
(msg 2928); doc_s_smith ya venía
reflexionando sobre por qué los humanos son tan fuertes en esta disciplina
(msg 2883). La lección que
sobrevivió a la carrera: la calidad de un orden es medible, y las diferencias
nunca son pequeñas.
Dinámico contra fijo, medido. El argumento entre fijo y dinámico de 2007
obtuvo una pequeña prueba controlada en septiembre de 2008. Markus Zajc ejecutó
tres órdenes sobre el 8×8 sin pistas, cada uno sobre diez órdenes de piezas
aleatorizados para cancelar los efectos del orden de entrada, todos bajo un
resolvedor de restricciones: barrido simple, un orden por valor restante mínimo
que toma siempre la celda con menos candidatos, y un orden por reducción máxima
que toma la celda cuya colocación poda más. El valor restante mínimo ganó; el
barrido quedó segundo pero oscilaba con el orden de entrada (su mejor ejecución
seguía siendo ~2× el ganador); la reducción máxima quedó última, porque sembrar
temprano el interior abierto compra un gran primer corte pero luego un factor de
ramificación castigador en cada retroceso
(msg 5918; los volcados de
dominios por orden están en su carpeta del área de archivos). Es un tablero
pequeño, pero es el duelo más limpio de la heurística CSP clásica contra un
barrido fijo, y aterriza donde aterrizan los conteos de nodos posteriores de la
comunidad: el valor reside en alimentar a la búsqueda con celdas restringidas,
ya sea una regla dinámica o un buen camino fijo el que te lleve allí.
La victoria del barrido es un hecho sobre el diseño de E2. En abril de 2008
Owen construyó puzzles 16×16 con el equilibrio de colores borde/interior
deliberadamente inclinado (2 colores de borde y 19 de interior, luego 14 y 15) y
puntuó los órdenes barrido, centro primero y borde primero en cada uno. Los
diseños inclinados son atacables: el centro primero bate al barrido en ~150× en
el diseño 2/19, el borde primero gana en el 14/15. En la partición 5/17 real de
E2, toda desviación pierde: el centro primero cuesta 1,22×1060 nodos
frente a los 1,07×1050 del barrido, porque el diseño equilibra la
teselabilidad del borde y del interior, dando al puzzle «ninguna zona débil por
la que empezar a teselar»
(msg 5263,
5243). El barrido por líneas no es
una ley de la naturaleza; es la respuesta correcta a un diseño específico y
adversario.
El cuadrado mágico 10×16. ¿Por qué el barrido por líneas y no, digamos, un
orden por bloques 4×4? La regla empírica de la forma de frontera de Louis
Verhaard: la mayoría de los órdenes alcanzan su máximo de conteo de nodos en
torno a la profundidad 160, así que lo que importa es la forma que tu orden ha
construido ahí, y la mejor forma conocida en profundidad 160 para E2 es un
rectángulo 10×16 (con dos esquinas rellenas). Los órdenes cuya frontera pasa por
«el cuadrado mágico 10×16» son casi óptimos; un barrido por bloques 2×2 lo hace,
un 4×4 no, que es exactamente la brecha que Max acababa de medir
(msg 5868,
5879). Esta es la pieza que la
curva de conteo de restricciones por sí sola no puede ver: dos órdenes pueden
pagar uniones según la misma planificación y aun así diferir por el perímetro de
la región que construyen.
Por qué «resolver el borde primero» es una trampa. El instinto humano más
natural, construir el marco fácil y luego rellenar el medio, es
cuantitativamente uno de los peores órdenes, y en 2025 Owen y Peter McGavin
detallaron por qué, precisamente sobre este pico en profundidad 160. El borde es
realmente fácil: tras la pieza de partida hay unas 5,17×1037 formas de
completarlo, de las cuales solo 14.702 pueden rellenarse con las 196 piezas de
interior, de modo que unos 3,5×1033 marcos deben probarse antes de que
uno siquiera pueda terminar
(msg 11572). Eso por sí solo es
desesperante, pero no es el verdadero problema. El problema es que con el marco
fijado primero, el conteo de nodos sigue subiendo después del borde hasta un
pico de unos 1057 hacia las 160 piezas, frente a unos 1043 del barrido
por filas. Un orden borde primero se compromete temprano con el borde y luego se
mete de lleno en un pico catorce órdenes de magnitud más alto que el del barrido
por filas, porque solo alrededor de 1 marco de cada 1031 lleva a alguna
parte y cada uno es caro de descartar
(msg 11573). El barrido por
líneas no gana construyendo una frontera más bonita, sino no pagando nunca por
un borde que aún no puede saber que está condenado.
Pero ¿qué barrido? Incluso dentro de los barridos por filas hay ocho
orientaciones: cuatro esquinas de partida, filas o columnas
(msg 6018). Max ejecutó durante
varios días estimaciones por muestreo del tamaño del árbol completo por
orientación: de derecha a izquierda se mantuvo estable justo por debajo de
2,7×1040 nodos, mientras que de abajo arriba, de izquierda a derecha
(la orientación que conecta más pronto la pieza de partida obligatoria, y la que
Verhaard ya usaba) salió en torno a 2,3×1040
(msg 6015,
6023). Una elección de folclore
convertida en un ~15% medido: minúsculo al lado de los órdenes de magnitud de
arriba, pero gratis.
Desviaciones que pagaron. La ortodoxia del orden de barrido se puso a prueba
constantemente, y en su mayoría ganó, pero no siempre. El propio Owen resolvió
su desafío 14×14 con un orden de cuadrados decrecientes después de que el
barrido se atascara; en tableros irregulares el argumento de equilibrio ya no se
sostiene (msg 3124). Se propusieron
híbridos que empiezan como cuadrados crecientes (más baratos al principio) y
cambian al barrido antes del pico de profundidad media
(msg 6142). Y Max encontró una
mejora genuina dentro del barrido: al comienzo de una fila, los candidatos de
borde que difieren únicamente en su segundo color de borde no emparejado son
equivalentes: refuta uno y los has refutado todos. Verhaard, encantado
(«¡Por fin algo que bate al simple barrido por filas!»), la implementó y
confirmó ~10% del espacio de búsqueda eliminado a un coste casi nulo
(msg 5980,
5983,
6062).
Desviaciones que no pagaron (mediciones del cuaderno)#
La comunidad publicó sobre todo las desviaciones que tenían argumentos a
favor. El cuaderno de laboratorio del proyecto guarda la otra especie,
órdenes atractivos que perdieron, y los regímenes k de arriba saben
nombrar el mecanismo de cada uno.
Las espirales pagan un impuesto de cierre. En un banco de pruebas de
interior 14×14 con borde (8 semillas por brazo), una espiral de fuera hacia
dentro se atascó en la profundidad 26 en las 8 semillas, en la esquina de
cierre de su primer anillo. Una espiral de borde libre se estancó en
profundidades 133 a 141 con 0 completados, frente a 344 a 347 de un barrido
por filas; con todas las asistencias del motor activadas aún chocaba en 131
a 140 con 0 completados en 300 s, frente a 446 a 448 del barrido. La ley en
k dice por qué: todo el primer anillo de una espiral de borde libre corre
con un vecino colocado o menos por celda, una ramificación casi imposible
de podar, mientras que una espiral con borde paga un impuesto de cierre:
cada anillo carga 4 o 5 celdas con tres vecinos colocados en sus esquinas y
en su empalme, y las celdas de tres lados son casi irrellenables. El
barrido por filas es el orden de Ricitos de Oro, dos vecinos constantes y
una sola zona de daños activa.
Partir de las pistas pierde. «Empieza donde está la información» suena
bien y apunta al revés. En un duelo de 60 s sobre el puzzle real (una
configuración, una ejecución, así que léase como nuestra prueba y no como
una refutación), un orden centrado en las pistas, extendiéndose desde las
cinco celdas de pista, alcanzó la profundidad 42 (62 aristas emparejadas)
mientras que un orden dinámico por celda más restringida, que en la
práctica devora primero el borde pero sigue libre de abandonarlo (a
diferencia del marco comprometido de la trampa de arriba), alcanzaba la
profundidad 164 (282 aristas emparejadas). Las celdas alrededor de las
pistas centrales llevan los dominios de piezas más anchos del tablero;
el orden centrado en las pistas prioriza exactamente las celdas menos
restringidas.
Una X a través de las pistas también pierde. Precomprometer dos
diagonales de 3 celdas de ancho pasando por las cinco pistas, y luego
rellenar hacia fuera, terminó 51 aristas emparejadas por debajo de su
referencia (396 contra 447 con presupuestos idénticos, una sola semilla).
Tres experimentos, un patrón, enunciado como patrón y no como teorema: todo
orden estático que probamos que pasa temprano por celdas interiores de
dominio ancho perdió. Un orden estático no esquiva la región difícil; elige
qué región se convierte en la región difícil. También elige dónde aterrizan
los fallos: dónde se amontonan los desajustes
en un tablero casi perfecto sigue al orden de barrido, centro-abajo para
los barridos de arriba abajo, arriba para los de abajo arriba (visible en
los propios tableros de clase 469 de la comunidad), esquinas para las
espirales desde el centro. Un orden de relleno no solo decide cuánto
fallas, sino dónde.
La literatura académica aterriza en el mismo sitio. Ansotegui, Bejar,
Fernandez y Mateu, que convirtieron los puzzles de emparejamiento de
aristas en benchmarks SAT/CSP, trabajaban con órdenes estáticos de la
familia damero-más-espiral-central; reproducido en nuestro motor sin el
filtrado all-different completo que sus modelos suponen, ese orden hizo
explotar los conteos de nodos en unas 600×. Y la base de backtracking del
estudio hiperheurístico de 2012 de Wauters, Vancroonenburg y Vanden Berghe
hizo competir el barrido por filas contra espiral, espiral inversa y
órdenes en espejo, y encontró el barrido significativamente mejor: un
redescubrimiento independiente de la tesis de la lista de correo.
La búsqueda en peine: la geometría de las puntuaciones altas#
Todo lo anterior optimiza una búsqueda completa, cuyo conteo de nodos culmina
cerca de la profundidad 160. En octubre de 2008, mientras guardaba en privado
los tableros que ganarían el premio de escrutinio de 10.000 dólares, Verhaard
respondió a una pregunta distinta de Owen: ¿cuál es el mejor orden cuando
persigues una puntuación parcial y por tanto vives mucho más profundo en el
tablero (msg 6111)? Su respuesta
nombraba una geometría: los mejores órdenes que había encontrado se parecen a
una búsqueda en peine (la mayoría de las filas recorridas horizontalmente, y
luego las filas restantes recorridas verticalmente), con la longitud de los
dientes ligada al objetivo: «Cuanto más baja sea la puntuación que persigues, más
largos se vuelven los dientes del peine»
(msg 6112). Max había convergido de
forma independiente hacia casi el mismo orden (doce filas de barrido, luego
barrido por columnas) y reportó puntuaciones «aproximadamente 1 arista más bajas»
que lo que lograba el solucionador de Louis
(msg 6126).
La intuición: una búsqueda completa debe cruzar el cuello de botella de la
profundidad 160 lo más barato posible; una búsqueda de puntuación alta, en
cambio, quiere muchas maneras baratas de terminar. Cada diente vertical es una
columna corta, casi independiente, cuyos fallos son locales, de modo que
fronteras profundas y de puntuación alta se alcanzan una y otra vez. El peine
era una de las dos mitades de la máquina detrás del 467; la otra mitad, el
deslizamiento de aristas con umbral de profundidad,
decidía qué se les permitía colocar a los dientes. Y las dos se ajustaron
conjuntamente: Verhaard optimizó el orden de relleno y el arreglo de
deslizamientos juntos con una cadena de Markov sobre (profundidad, deslizamientos
usados), construida a partir de probabilidades de ajuste por profundidad medidas
(msg 6423). Diseño de orden por
cálculo, no por folclore. El motor completo está en
la página eii de Verhaard.
El peine durmió dieciocho años en la historia de los récords antes de que
lo probáramos en casa; fue releer los mensajes de arriba lo que sacó a la
luz la palanca. Injertar la geometría del peine en un productor de búsqueda
en haz escrito desde cero (filas superiores en fila-mayor, filas inferiores
rellenadas como dientes verticales cortos) elevó su mejor parcial bruto de
455 a 457 aristas emparejadas de 480, en tableros con las cinco pistas
estrictas, solo por el orden de visita; nada más cambió. Detrás de esa
frase hay un barrido, no una carrera afortunada: cinco órdenes (fila-mayor
más cortes de peine tras las filas 8, 10, 12 y 14) cruzados con tres
anchuras de haz (2048, 8192 y 16384), 24 semillas cada uno a cómputo
igualado, en 8 núcleos. El techo nuevo solo aparece en el haz más ancho,
donde el corte 14 alcanzó 457 en una semilla y el corte 12 alcanzó 456 en
dos, cada tablero comprobado de tres maneras independientes (un
repuntuador independiente, un verificador externo y el conteo propio del
productor; colocación estricta de las cinco pistas, las 256 piezas todas
distintas). En anchuras menores el peine empata el máximo del fila-mayor.
Lo que el peine mueve con fiabilidad es el suelo y el centro de la
distribución. En haz 2048, los cortes 10 y 12 suben el mínimo de 24
semillas de 446 a 449 y la mediana de 449 a 451; en el haz más ancho, la
mediana del corte 12 gana una arista. El corte 12 también alcanza 455, el
antiguo techo del fila-mayor, con la mitad de la anchura de haz, y en haz
8192 un barrido de 24 semillas rinde 15 tableros de 453 o mejor contra 9
del fila-mayor: +67% de buenos tableros de partida por unidad de cómputo.
La regla de Verhaard sobre la longitud de los dientes se sostiene también
desde arriba. Los dientes largos (corte 8, dientes de 8 celdas) retroceden
por debajo del fila-mayor en todas las anchuras; los dientes cortos ganan.
El corte 12, el exacto «doce filas, luego columnas» de Max, es el mejor
para toda la distribución, mientras que el corte 14, con sus dientes de 2
celdas, encuentra el mejor tablero aislado sobre una mediana más baja: una
geometría de remate más fina y de mayor varianza. El mecanismo es la
intuición enunciada arriba, ahora medida: cada diente corto es una columna
casi independiente cuyos fallos quedan confinados, de modo que las
fronteras profundas de puntuación alta se alcanzan una y otra vez.
El orden también decide dónde acaba la holgura recuperable. Una
re-resolución exacta de las tres últimas filas sube un tablero fila-mayor
de 455 a 457 y no hace nada por un tablero peine de 457: la región rellenada
al final y menos restringida del peine son sus dientes verticales, no sus
filas inferiores, así que una reparación por banda de filas apunta al lugar
equivocado. Una re-resolución exacta alineada con los dientes, por banda de
columnas, lleva los tableros peine a 459 y no más allá, porque los dientes
salen del haz ya exactamente óptimos (un solucionador exacto probó óptima
una región de dientes de 32 celdas en unos 21 s); el peine gasta durante la
construcción la holgura que la reparación habría recuperado. Las dos rutas
convergen en 459: el peine adelanta la puntuación, el fila-mayor la deja en
una cola recuperable, y orden más reparación de final de partida cosechan
la misma holgura. Para la escala, 455, 457 y 459 son conteos de aristas
emparejadas en tableros con las cinco pistas estrictas, de un productor de
cuaderno en 8 núcleos; los tableros comunitarios están más arriba, y
la página de récords lleva la clasificación.
Todo lo anterior ordena celdas. La perilla gemela es el orden de las
piezas probadas dentro de una celda: el duelo de Zajc iba de qué celda
abrir a continuación, este va de qué candidato entra primero. La respuesta
del cuaderno es un nulo limpio. Dentro de un relleno fila-mayor fijo,
reordenar la lista de candidatos de cada celda por escasez global de color
(colores más raros primero) no cambió nada medible sobre 8 semillas por
brazo: a 60 s de reloj iguales, la mediana fue de 389 aristas emparejadas
(pistas fijadas, puzle de cinco pistas) en cada brazo, orden de
referencia, escasez-primero, y un contraorden deliberado (colores más
abundantes primero) diseñado para perder. El control no perdió; su mejor
ejecución (419) batió a la mejor de la referencia (415). El caudal de nodos
fue plano entre brazos, 8,2 a 9,6 millones de nodos por segundo: el
reordenamiento es gratis, y sin valor, en ambos sentidos. (Antes de
comparar, el brazo de referencia se verificó idéntico nodo a nodo al motor
sin modificar.)
El mecanismo es una señal hambrienta. Cuando un barrido fila-mayor alcanza
una celda, la lista de candidatos ya está filtrada al puñado de piezas que
emparejan con dos colores fijados, y una poda global de factibilidad
oferta-demanda ya explota la escasez de color sobre todo el resto del
inventario; el orden por escasez re-deriva, más toscamente, información que
la búsqueda ya usa, y cuál de tres piezas legales entra primero importa
poco cuando el cubo se agotará de todos modos. Acotémoslo como se midió: el
orden de candidatos fue inerte en nuestro motor en un punto de operación
(una pila de podas, un presupuesto de 60 s, solo señales globales de
escasez), no «el orden de valores nunca importa en ningún sitio». Rima
además con la única victoria intra-barrido de arriba: el ~10% de Max vino
de eliminar candidatos de borde, no de reordenarlos. Las ganancias viven
en la poda y en el orden de las celdas.
Observa el barrido por filas. Tras la primera fila, casi cada colocación
encuentra exactamente dos vecinos colocados: a la izquierda y debajo. La
curva de restricciones se aplana en 2, y el acumulado de uniones sube de
forma constante: la búsqueda paga a medida que avanza.
Cambia a la espiral. Todo el primer anillo (60 colocaciones) llega con
como mucho un vecino colocado: sesenta elecciones casi sin restricción
apiladas antes de que el interior empiece a devolverlas. La línea acumulada
se hunde por debajo de la referencia del barrido por filas exactamente donde
el árbol menos se lo puede permitir.
Prueba la diagonal. Sorpresa: los conteos se parecen casi a los del
barrido por filas. Este es el límite del punto de vista por conteo de vecinos:
la frontera de la diagonal es más larga que la de un barrido durante buena
parte del medio juego, un efecto de forma que solo la
teoría compleja (o la regla mágica del 10×16)
puede puntuar.
Selecciona el peine con dientes de 4. Doce filas de barrido, luego dientes
verticales, el orden de Max del
msg 6126. Fíjate en el pequeño
acantilado en cada nuevo diente: la primera columna paga una celda débil, de 1
vecino, en su base, el precio de la geometría de las puntuaciones altas.
Alarga los dientes. Una mayor parte del tablero pasa a modo vertical y las
colocaciones débiles se multiplican. Ese es el compromiso de Verhaard, dicho
visualmente: cuanto más baja sea la puntuación que persigues (cuantos más
deslizamientos permitas), más largos serán los dientes que puedes permitirte.
Luego hazlo correr de verdad. El
campo de juego de caminos de búsqueda te permite dibujar
cualquiera de estos caminos, o el tuyo propio, sobre un puzzle real y ver a
los solucionadores correrlos en carrera, con una estimación de pico de meseta
en directo al lado.
En tiempo de ejecución, nada: un orden de relleno fijo es un arreglo precalculado
de 256 índices de celda, y «elegir la siguiente celda» es un incremento de
índice: O(1), cero ramificaciones, que es precisamente el argumento de
velocidad que mató al ordenamiento dinámico para E2
(msg 5860). Todo el coste y todo el
beneficio residen en el árbol que el orden induce:
Entre familias de órdenes, órdenes de magnitud. El centro primero en E2 es
1010 veces más caro que el barrido
(msg 5263); un orden por bloques
4×4 cuesta ~70× sobre el barrido 1×1 según las estimaciones de teoría compleja
de Max, la brecha que resume la regla mágica del 10×16
(msg 5867).
Dentro de una familia, porcentajes medibles. Abajo-arriba-izquierda-derecha
contra barrido de derecha a izquierda: ~15%
(msg 6023); poda por equivalencia
de piezas de borde: ~10%
(msg 6062). Vale la pena tenerlo,
nunca decisivo.
Elegir mal es invisible. Un mal orden no produce ningún error, solo un
árbol 1010 veces más grande, en silencio. Por eso el verdadero avance de
la comunidad no fue ningún orden en particular, sino la capacidad de puntuar
un orden antes de ejecutarlo: los conteos de formas de Owen, luego la
teoría compleja, luego el ajuste por cadena de
Markov de Verhaard combinando orden y calendario de deslizamientos
(msg 6423).
Cada motor récord desde entonces ha tratado el orden como un objeto diseñado y
calculado: el peine-más-arreglo-de-deslizamientos de Verhaard
(eii), el barrido inferior-
izquierdo elegido por teoría compleja de McGavin, y el orden de barrido fijo bajo
los cortes con umbral de profundidad de
Blackwood. Veinte años de
ciencia del orden de barrido se condensan en una sola instrucción: antes de
gastar una sola hora-CPU, gasta un milisegundo puntuando el camino.