Dividir el tablero en pequeños bloques, resolver cada uno hasta el óptimo demostrado y volver a pegarlos, pagando las costuras en lugar de prohibirlas. Partiendo de cero, sin ningún récord que copiar, el método alcanza 448.
Reproducirdeterminista — se reproduce bit a bit·relanza la búsqueda (Ver más abajo)·Presupuesto: ~30 s per block × 16 blocks (exploratory run, not the standardized single-core bench)
Pipeline
1
MaxSAT
Solve each 4×4 block to a provable optimum with core-guided weighted MaxSAT; shared edges are soft clauses
aporta: Scarcity reservation: hold back the ~8% globally scarcest pieces to fight piece theft
2
cola exacta
Coarse backtracking over the per-block MaxSAT solution enumerators composes the blocks into a full board
Complejidad
Tiempo
per 4×4 block ~30 s to MaxSAT optimum (3×3 ~11 s); 16 block levels with backtracking
Espacio
one MaxSAT solution enumerator per block level held on the backtrack stack
Each block is exact (MaxSAT-optimal), but composing 16 of them is a coarse 16-level backtracking search, exponential in the worst case, tractable because each node is a whole provably-optimal block.
Hardware y ejecución
Ejecución nativaSolo CPU
0.067núcleos·hora
Núcleos
8
RAM
16 GiB
GPU
0
CPU
Apple M1
Máquina
MacBook (Apple M1, 8 cores)
Presupuesto
~30 s per block × 16 blocks (exploratory run, not the standardized single-core bench)
Eternity II no posee ninguna estructura local que se pueda explotar a escala
global, pero una pequeña ventana de ella, un bloque 4×4, se resuelve hasta la
optimalidad perfecta en segundos. MOSAIC es un experimento construido sobre ese
único hecho: si sabes resolver un bloque exactamente, ¿puedes componer dieciséis
bloques exactos en un tablero entero?
El tablero 16×16 se recorta en dieciséis bloques 4×4, que se rellenan uno a uno.
Cada bloque se entrega a un solucionador MaxSAT exacto, que encuentra la mejor
colocación posible de las piezas que contiene. El truco está en cómo un bloque
se encuentra con sus vecinos ya colocados: esas aristas compartidas no son
requisitos estrictos, sino objetivos suaves que el bloque es recompensado por
igualar. Así un bloque nunca puede volverse imposible; simplemente paga por
cualquier costura que no pueda igualar, y siempre se completa.
La segunda idea combate directamente el robo de piezas. Antes de rellenar un
bloque, MOSAIC retiene las piezas globalmente más escasas, de modo que a los
últimos bloques no les falten las piezas raras que sus costuras exigirán. Ajustar
cuánto reservar es la única perilla real; demasiado poco y la esquina se queda
sin recursos, demasiado y los primeros bloques lo sufren.
▶Interactivo: la búsqueda de ensamblaje de bloquesExplorar →
La primitiva de ventana cumple su promesa: un bloque 4×4 se resuelve hasta su
óptimo de 24 aristas en unos treinta segundos, un 3×3 en once, confirmando que
el puzzle es efectivamente tratable a pequeña escala. Compuesto sobre todo el
tablero, desde cero y sin arranque en caliente, MOSAIC alcanza 448 de 480. El
punto óptimo de reserva se sitúa en torno al ocho por ciento del reservorio.
El déficit es informativo: casi todo él está en los tres últimos bloques de la
esquina inferior derecha, donde el reservorio finalmente se agota: el robo de
piezas de nuevo, ahora visible como un único punto brillante en el tablero. La
exactitud a pequeña escala sí compone, pero el orden de composición gasta su
libertad temprano y la paga al final, la misma forma con la que se topa cada
método aquí.
La exactitud es genuina, y también lo es el backtracking que la cose.
Bloques exactos. Cada bloque 4×4 se codifica como un problema MaxSAT
ponderado y se resuelve con RC2, un solucionador guiado por núcleos, hasta un
relleno demostrablemente óptimo. Las aristas compartidas con los vecinos ya
colocados son cláusulas suaves (recompensadas, no exigidas), de modo que un
bloque nunca puede ser inviable: paga por cualquier costura que no pueda
igualar y siempre se completa.
Backtracking sobre las soluciones. MOSAIC no es un pegado de un solo tiro.
Cada nivel de bloque mantiene un enumerador de soluciones MaxSAT, las mejores
primero, mediante RC2 más cláusulas de bloqueo que descartan los rellenos ya
vistos. Cuando un bloque posterior se queda sin recursos o un nivel se agota,
la búsqueda retrocede y extrae la siguiente solución del bloque anterior
(liberando un conjunto de piezas distinto). Es una búsqueda por backtracking
gruesa sobre 16 niveles, donde cada nodo es un bloque entero óptimo.
Reserva por escasez. Antes de rellenar, MOSAIC retiene las piezas
globalmente más escasas, de modo que a los bloques finales no les falten las
piezas raras que sus costuras exigen. Esa fracción de reserva es la única
perilla real; el punto óptimo medido es ~8% del reservorio.
La primitiva de ventana es real: un bloque 4×4 alcanza su óptimo de 24 aristas
en ~30 s, un 3×3 en ~11 s, el puzzle es tratable a pequeña escala. Compuesto
desde cero alcanza 448, con el déficit residual concentrado en los tres últimos
bloques de la esquina inferior derecha: el robo de piezas
hecho visible como un único punto brillante.
Determinista: las resoluciones de bloque MaxSAT y la composición por backtracking
son exactas, de ahí kind: exact; el tablero de 448 se reproduce y se verifica
arista por arista en el visor. El motor de bloque funciona a partir del puzzle
solo, sin corpus ni tablero de partida, siendo su única dependencia externa un
solucionador MaxSAT, por lo que se prevé un directorio ejecutable de respaldo
para él junto a los demás experimentos exactos.
¿Un orden de bloques no por filas, en espiral hacia el interior o resolviendo
primero la esquina más restringida, desplazaría el agotamiento fuera del bloque
más difícil? ¿Podrían solaparse los bloques, de modo que las costuras se
resuelvan dos veces y se reconcilien? ¿Y haría una primitiva más rápida (en Rust)
asequible un tamaño de bloque mayor, con su garantía de exactitud más fuerte?