Reduce cualquier solucionador récord a su esqueleto y encontrarás el mismo
bucle: colocar una pieza, comprobar las aristas, retroceder cuando te atascas.
El algoritmo quedó fijado en 2007. Aquello en lo que la comunidad ha competido
realmente durante veinte años es la capa por debajo del algoritmo: el oficio
que decide si visitar un nodo de ese árbol cuesta unos 26 ciclos de reloj, como
Mike Field midió en su propio motor
(message 9003), o cien veces eso en
un intérprete ingenuo. Mismo árbol, misma búsqueda, dos órdenes de magnitud de
diferencia en colocaciones por segundo.
Esta página reúne ese oficio, técnica por técnica, cada una con su fuente
primaria en el archivo de la lista de correo. La cronología de cómo un motor las
acumuló durante dos décadas se cuenta en la
página de McGavin; la anatomía del motor
detrás de los tableros récord está en la
página de Blackwood. Aquí está el estante del
que ambos se surten.
Todo backtracker rápido comparte una idea portante: nunca buscar piezas
candidatas, sino consultarlas. Fija el
orden de relleno (un recorrido por filas, por
lo general), y cada celda expone exactamente dos restricciones conocidas cuando
llega su turno, el color de su arista norte y el color de su arista oeste. Así
que precalculas una tabla indexada por ese par de colores, y encontrar todas las
piezas que pueden ocupar legalmente la celda actual se convierte en un único
acceso a memoria. La receta de Field de 2007 la ponía la primera en la lista,
junto con su corolario: un orden de búsqueda fijo es lo que hace posible la
clave de dos aristas en primer lugar, y colocar una pieza entonces solo actualiza
sus vecinas sur y este
(message 3098). El mismo diseño se
diseccionaba ese mismo año en torno al solucionador C++ público de Marc Lebel, el
backtracker rápido de referencia de la época, en el hilo que hace también las
veces del primer seminario de ingeniería de la comunidad
(message 1704).
Todo lo demás en esta página es un refinamiento de esa tabla: hacerla más
pequeña, densificar sus entradas o desenrollar el código a su alrededor.
La tabla de consulta tiene un problema de tamaño en cuanto la indexas por más de
dos aristas. En el hilo de Lebel, Nathan describió la versión de fuerza bruta: un
arreglo de 4 dimensiones indexado por los cuatro colores de arista,
combo4[32][32][32][32]. Un millón de entradas, en su mayoría ceros, fallos de
caché garantizados. Su solución se apoyaba en el generador de hash perfecto
mínimo de Bob Jenkins, un enlace que él mismo había compartido con la lista. Dado
que las 256 piezas en 4 rotaciones producen solo 1024 cuádruples de aristas
distintos, un hash perfecto mínimo hace corresponder la clave empaquetada de 32
bits a una tabla de 1024 entradas sin colisiones: «lo bastante pequeña para caber
en el caché la mayor parte del tiempo», con un sobrecoste de hash casi nulo, y
las claves ausentes simplemente leen un conteo de cero
(message 1831). Un millón de
entradas reducidas a mil, únicamente para que el conjunto de trabajo viva en L1.
Él trazó la frontera él mismo: la tabla de cuatro aristas solo se gana el sustento
cuando el orden de relleno puede dejar huecos; un solucionador de recorrido
estricto por líneas nunca la necesita.
El presupuesto de ciclos de Field explica por qué tanto de este oficio trata de
la disposición en memoria: a 75 M tiles por segundo por núcleo, más de la mitad
del tiempo estaba detenido en el acceso a memoria, no en el cálculo
(message 9003). La respuesta es
hacer que cada byte que la búsqueda toca cuente. Empaqueta los cuatro lados de
una pieza en un único entero (message 3098).
Mantén el conjunto de piezas usadas como una palabra de 64 bits por grupo y
cortocircuita todo un bucle de candidatos con una única comprobación de máscara,
una optimización que Arnaud Carré y Adam Miles descubrieron haber implementado de
forma independiente, línea por línea
(message 9808,
message 9809). Dimensiona la entrada
de la tabla de candidatos para que toda la tabla quepa en el caché. Ese es
exactamente el diseño de la struct RotatedPiece de seis bytes de Blackwood, ya
contada en la página de Blackwood: número
de pieza, rotación, los dos lados expuestos, un conteo de rupturas y un conteo
heurístico, y nada más.
Si una consulta te da las piezas candidatas, ¿por qué no precomponer pares en
«bipiezas» 1×2 y colocar dos celdas por nodo? Medido sobre el código de Lebel en
agosto de 2007, funcionaba: alrededor de un 20–30 % más rápido
(message 1734). Pero el trueque es
duro y el archivo documenta ambas caras. Al pasar a bloques 2×2, un miembro midió
aproximadamente 4,2× más lento y rechazó de plano las piezas más grandes
(message 1730). Ninguna sorpresa una
vez contadas las tablas: cerca de 4 millones de combinaciones 2×2 interiores
distintas (message 3044). Louis
Verhaard reportó que las bipiezas ayudaban «solo muy marginalmente» en su propio
backtracker rápido
(message 3061). Y en 2008 la lista
zanjó la cuestión teórica subyacente: un solucionador de metateselas visita
esencialmente la misma frontera de restricciones que un solucionador 1×1
(«sincronizados cada 4 piezas»), de modo que la ganancia es a nivel de
implementación, nunca una reducción del espacio de búsqueda
(message 5842,
message 5899). La precomposición es
una aceleración que se paga con memoria, y más allá del 1×2 el precio se vuelve
negativo.
Las últimas indirecciones del bucle interno («¿en qué celda estoy?, ¿cuáles son
sus vecinas?») se pueden eliminar sencillamente no teniendo bucle. La receta de
Field: generar procedimentalmente código monolítico en línea recta, un bloque
por celda, cada bloque conociendo sus propias vecinas como constantes; su código
generado se compilaba en unas 33 instrucciones por celda
(message 3098). La idea se propagó
rápido: ya a mediados de 2008, istarinz generaba un solucionador C no recursivo
por puzzle y por camino de relleno, compilado con el compilador de Intel
(message 5480,
message 5438), en la misma temporada
en que la lista comparaba notas sobre backtrackers no recursivos en general
(message 4683). El body.c de Peter
McGavin es esta idea acumulada durante veinte años: bloques etiquetados como
cell_9_2_next:, cadenas de goto que regresan a la celda anterior al agotarse,
el fichero entero regenerado para cada puzzle y cada conjunto de pistas
(message 11337,
message 11782). Y funciona entre
lenguajes: libblackwood de Jef Bucas, un generador en Python que emite C, hizo el
algoritmo C# de Blackwood aproximadamente el doble de rápido en la misma máquina
(message 10065,
message 10078).
Por debajo del código fuente todavía queda rendimiento por cosechar, en
instrucciones y flags más que en ideas. Adam Miles llevó su solucionador de 78 a
90 millones de colocaciones por segundo con las instrucciones de extracción de
bits bextr de BMI y pext de BMI2, a la vez que señalaba que se estaba
volviendo «cada vez más difícil» llegar más lejos
(message 9796). El manual de McGavin
de 2026 es el folclore acumulado: prueba clang, icc e icx frente a gcc; prueba
versiones (clang-15 le gana a clang-19 en sus placas ARM); añade
-march=native y -mtune=native; usa optimización guiada por perfiles. Ninguno
de estos consejos es una bala de plata
(message 11751). Su truco de
contador del mismo mensaje es el género en miniatura: el contador de colocaciones
de 64 bits se alimenta de un registro de 16 bits que se desborda, sumando
0x10000 cada vez, porque cronometró ambas formas hace años en hardware de 32
bits y el truco ganó.
El mismo realismo se aplica al hardware. El multithreading escala de la manera
obvia: los solucionadores multinúcleo rebasaron los 100 M colocaciones/s en 2008
(message 5804), y un solo Core i7
alcanzó los 558 M/s aquel diciembre
(message 6212). El progreso en un
solo núcleo, en cambio, se detuvo en gran medida. Al publicar su tabla de 2025 de
nueve combinaciones CPU/compilador (38–84 M colocaciones/s), McGavin señaló que
las velocidades en las CPU más recientes «son solo un poco más rápidas» que en su
Phenom II de 2010
(message 11643). Los motores
chocaron contra el muro de memoria de Field hace quince años y desde entonces se
apoyan en él.
Una cultura de ingeniería vale tanto como sus bancos de prueba, y el archivo tuvo
que construir esa disciplina a las malas. En enero de 2008, comparar afirmaciones
de velocidad forzó la pregunta de definición: Txibilis contaba un nodo como cada
pieza válida comprometida en el tablero, sin anticipación
(message 3843); otros contaban
colocaciones intentadas, o pasos, y el hilo concluyó que quizá no exista una
métrica en la que todos coincidan
(message 3946). La pregunta volvió
en 2017 y recibió la respuesta estándar: las «piezas por segundo» de la comunidad
cuentan las piezas colocadas por segundo, al estilo del ajedrez
(message 9739,
message 9740). La objeción estándar
la acompañaba: la métrica favorece los órdenes de relleno por recorrido de líneas
y no dice nada sobre la cobertura del espacio de búsqueda por unidad de tiempo
(message 9746).
Dos consecuencias prácticas. Primera: nunca compares las cifras de M/s de dos
solucionadores sin comprobar qué cuentan; un solucionador «más rápido» puede
simplemente tener una definición más generosa. Segunda, el hábito positivo que
surgió de ahí: publicar conteos de nodos junto a los tiempos. Un backtracker
determinista que recorre un árbol fijo debe contar los mismos nodos en cualquier
máquina, de modo que los conteos exactos de nodos se convirtieron en las sumas de
verificación de la comunidad, la forma en que los portes, reescrituras y hardware
nuevo prueban que recorren el mismo árbol antes de que su velocidad signifique
nada.
Hay una tercera confusión que conviene nombrar de una vez por todas, porque reaparece
cuando estos números llegan a un público más amplio. «Rápido» apunta a tres cantidades
sin relación, y ninguna se convierte en otra:
- Colocaciones por segundo (o piezas/s o nodos/s) - cuán rápido avanza la
búsqueda. Es lo que mide cada cifra de esta página, y depende del tablero tanto como
del motor. El C de McGavin hace ~287 M en un tablero fácil pero ~105 M en uno difícil;
un motor en Rust portable en este sitio
alcanza ~110 M en el mismo tablero difícil - empate allí - y ~122 M en el fácil.
- Aristas casadas sobre 480 - cuán bueno es un tablero. Es el eje donde viven los
récords (el techo es 470). Es independiente de la velocidad de
recorrido: un motor lento suele encontrar un tablero mejor que uno rápido.
- Colocaciones agregadas por segundo - un total de flota, muchas máquinas sumadas.
El «~300 M/s» que a veces se atribuye a un solo motor es en realidad el
enjambre del Eternity 2 Syndicate, unas
veinte máquinas sumadas, no un núcleo.
Un número alto en el primer eje no dice nada del segundo, y el tercero no es en absoluto
una velocidad de motor. Cuando este sitio cita un rendimiento, siempre es colocaciones/s
en un núcleo salvo que se diga otra cosa; donde el compromiso entre gastar el
presupuesto de un solucionador en velocidad o en criterio es el tema, ese argumento vive
en ir rápido.
| Técnica | Lo que cuesta | Lo que rindió | Fuente |
|---|
| Tablas de candidatos por posición (clave de dos aristas) | memoria para las tablas; un orden de relleno fijo | los candidatos en un solo acceso a memoria, la base que comparte todo solucionador rápido | 3098 |
| Hash perfecto mínimo | construcción de hash fuera de línea | tabla de un millón de entradas → 1024 entradas, residente en caché | 1831 |
| Empaquetado de bits, structs a medida del caché | contorsiones de código | menos detenciones donde >50 % del tiempo es memoria; cortocircuitos por máscara de 64 bits | 9003, 9808 |
| Bipiezas (precomposición 1×2) | las tablas crecen rápido; sin reducción del espacio de búsqueda | +20–30 % en 1×2; ~4,2× más lento en 2×2 | 1734, 5899 |
| Generación de código (código en línea recta por celda) | un pipeline de compilación; regenerar por puzzle | ~33 instrucciones/celda (2007); ~2× gracias al C de libblackwood (2020) | 3098, 10065 |
| Instrucciones de extracción de bits BMI/BMI2 | portabilidad | 78 → 90 M colocaciones/s | 9796 |
| Comparativa de compiladores, flags nativos, PGO | ensayo y error, por máquina | ganancias «significativas» pero sin cuantificar, de un solo dígito porcentual a decenas | 11751 |
| Trucos de contador (alimentación por desbordamiento de 16 bits) | oscuridad | medible solo en hardware de la era de 32 bits | 11751 |
Ahora tomemos distancia. La receta de Field de 2007 ya hacía 60–80 millones de
colocaciones por segundo por núcleo
(message 3098). Veinte años de
oficio desde entonces han ensanchado ese rango en lugar de multiplicarlo de manera
uniforme. Sobre código portable comparable la ganancia es modesta: 72,7 M/s de un
solucionador C++ afinado y 68,4 M/s de un descendiente en Rust del de Blackwood en
2025 (message 11633,
message 11634), apenas por encima de
la base de 2007. El ~4× solo aparece con C generado por celda en el hardware más
reciente: alrededor de 225–295 M/s para el de McGavin
(message 11751,
message 11750), así que mezcla una
ganancia de generación de código con una ganancia de hardware, no oficio a secas.
A lo largo de esos mismos veinte años, el récord se movió tres aristas: de 467 a
470.
Un experimento de 2026 en este sitio
separa esas dos ganancias directamente. Toma un backtracker en Rust portable y seguro
y aplica el mismo oficio - código generado por celda, celdas empaquetadas, conjunto
usado en arreglo de bytes, fusión de celdas - y luego lo mide frente al C de McGavin en
una máquina, mismo tablero, ambos sin pantalla, uno tras otro. Manteniendo el hardware
fijo, el motor portable iguala al C en tableros difíciles y profundos (≈105 a 110 M
nodos de búsqueda/s cada uno) mientras que el C sigue siendo ~2,3× más rápido en los
fáciles y poco ramificados (≈287 M frente a ≈125 M) - cada peldaño verificado como
recorriendo el árbol idéntico. La lección corta por ambos lados: el oficio de generación
de código es real y reproducible en un lenguaje moderno - bastante para igualar al C
afinado a mano donde la búsqueda es difícil - y sigue siendo solo el factor constante
que esta página describe. El mismo motor, apuntado al rompecabezas real, se estanca en
los 300 altos sobre 480, justo donde la velocidad sola te deja.
Los practicantes lo dijeron ellos mismos. Joshua Blackwood, catalogando sus
callejones sin salida tras el 469 (solucionadores SAT,
GPU, bloques 2×2 en caché, todos medidos y
descartados), constató que solo refinar las heurísticas rindió alguna vez, con
otro ~2× (message 10056). Y cuando
el hilo de velocidad de 2025 se apagó, Razvan escribió su epitafio: por rápido que
podamos comprobar, «no haremos ni una mella» en el espacio de búsqueda de E2
(message 11657). El oficio de esta
página es real, medible y vale la pena aprenderlo; es lo que permite que una
granja de aficionados recorra 10¹⁷ nodos. Pero un factor constante es un factor
constante.
Por qué encoger el árbol le gana a acelerar el recorrido
es la aritmética de esa frase; esta página es su registro de ingeniería.