Raphaël Anjou

Cada tablero récord que tenemos está congelado en su sitio. No se puede progresar a base de pequeños retoques desde un tablero excelente hacia uno perfecto, y podemos demostrarlo.

Un backtracker Rust en profundidad, seguro y portable, especializado en tiempo de ejecución al emitir y compilar Rust propio de cada rompecabezas, llevado de 43 a 123 millones de nodos de búsqueda por segundo en un núcleo. Medido con justicia frente al C de Peter McGavin en la misma máquina: un empate en tableros difíciles y profundos como el Eternity II real, y alrededor del 44 % de su velocidad en los fáciles. Cada peldaño recorre el árbol idéntico; toda la ganancia es código, no algoritmo.

Quince solucionadores, los nuestros y nuestras implementaciones de los dos backtrackers récord de la comunidad, cada uno ejecutado una vez sobre diez variantes del puzzle oficial con las esquinas fijadas, un solo núcleo, 60 segundos por ejecución. El hallazgo: el número de nodos no es la puntuación.

Construir un tablero desde cero, resolviendo los empates según la posición habitual de las piezas en los buenos tableros ya conocidos. Alcanza una puntuación alta sin ningún tablero de partida que copiar.

Un solo motor de propagación de restricciones, ejecutado bajo una docena de presets de ordenación y de propagadores, sobre las mismas diez variantes con esquinas fijadas que el ranking. Un estudio de lo que aporta cada ajuste, mantenido fuera del ranking principal porque el mejor preset alcanza menos de la mitad de la puntuación de un contendiente.

Construir un tablero desde cero, clasificando cada pieza siguiente según tres señales aprendidas de tableros fuertes anteriores. Alcanzó 460 en una familia de tableros que ninguna búsqueda previa había resuelto.

Una reimplementación desde cero del método eii de Louis Verhaard, ya que su propio binario no incluye código fuente y no se ejecuta aquí. Recocido por intercambio de composición de conjunto bajo la métrica de teselado 2×2; en el puzzle real de cinco pistas alcanza 438 de 480, en un solo núcleo.

Una brújula tenue para una búsqueda partida de cero: incitarla a comprometer las piezas raras pronto, allí donde se necesitan. No eleva el techo; hace que la búsqueda alcance de forma fiable la cima de su propio rango.

Leer cada tablero fuerte para detectar los hábitos que, en silencio, limitan un tablero, y luego romperlos. Este experimento produjo el mejor tablero del proyecto: 463 de 480.

Ejecutar la misma búsqueda en haz según nueve órdenes de recorrido distintos, para que aterrice en regiones diferentes en lugar de converger siempre a la misma. El orden en zigzag encontró un tablero 458 inédito.

Reconstruir de forma idéntica los tableros estrictos de 460 de la comunidad y descubrir, de paso, la jugada que los solucionadores corrientes no saben hacer: pagar dos desajustes en una misma celda.

Fijar un borde perfecto y luego explorar el interior tratando las aristas del borde como restricciones duras desde la primera celda.

Decidir de antemano no cuándo puede romperse un tablero, sino dónde: confinar cada desajuste a una forma de celdas elegida, y buscar la mejor forma.

Lanzar cientos de búsquedas cortas y baratas sobre el tablero, conservar solo los arranques más profundos y hacer ascender a los supervivientes a través de rondas cada vez más largas.

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.

Resolver exactamente una banda de filas encontrándose en el medio, para hallar el verdadero mejor final y medir hasta qué punto puede decidirse por anticipado una fin de partida.

Construir todo el tablero desde cero, sin marco prefijado, por etapas, dejando que el borde emerja al final a partir de las piezas restantes.

Algunos motores de Eternity II vuelcan su esfuerzo en recorrer el árbol de búsqueda lo más rápido posible; otros lo gastan en el criterio sobre dónde buscar. Este es el alegato a favor de los primeros - qué compra el rendimiento bruto, las tres cosas distintas que la gente llama «rápido» y por qué el motor más rápido jamás construido sigue sin poder resolver el rompecabezas.

Todos los formatos en los que un tablero o un puzzle de Eternity II circula en este sitio y en la comunidad: la cadena de letras board_edges y la lista de pistas hints, e2pieces.txt, el CSV de puzzle, el JSON Puzzle del sitio, y la URL de visor, con las reglas exactas a nivel de byte (cómo se codifica el borde gris en cada uno) y, sobre todo, qué puede y qué no puede recuperar cada formato.

Recuentos exactos de cuántas maneras válidas hay de rellenar un bloque pequeño en una posición dada del tablero oficial de Eternity II, bajo reglas cada vez más restrictivas: números fiables para contrastar el código de emparejamiento de aristas y de restricciones de tu solucionador.

El backtracker de Rust a WebAssembly que anima cada demo en vivo y verifica cada número de este wiki. No una máquina de récords sino un motor de referencia, portado cuatro veces y validado byte a byte, construido para que las afirmaciones de aquí puedan volver a ejecutarse.

Un estudio en cinco experimentos de una sola idea: en lugar de buscar Eternity II desde cero, extraer estructura del corpus de tableros fuertes ya encontrados y reinyectarla en una búsqueda. Un prior de posición, un voto de jugada aprendido, una brújula de demanda escasa, un minero de antipatrones y un decodificado de récord, ordenados de la señal más simple a la más sutil, y el único muro que los cinco alcanzan.

El estándar editorial de este cuaderno abierto: cómo una investigación sobre Eternity II pasa de ser un trabajo no publicado a una página publicada. De qué tipo de contribución se trata, si se publica, en qué nivel y dónde reside. Un estándar común, concebido para escalar a muchos autores.

Los motores compartidos que sustentan los experimentos de Raphaël Anjou. Los experimentos con nombre son estudios que se ejecutan sobre ellos; este es el aparato que comparten. Los preajustes CSP y la reimplementación de Verhaard están documentados aquí; los motores constructivos aún no están publicados.

El motor detrás del estudio DFS: un backtracker componible donde una variante es un cambio declarado sobre un padre, una capa IO compartida que cada algoritmo habla, y las definiciones de cada estadística que el estudio plantea: tasa de nodos, profundidad, rupturas.

El motor detrás del estudio de reparación: un único bucle componible de destrucción-reparación donde una variante es un cambio declarado sobre un padre, la IO y el scorer que comparte con el estudio DFS, un mapa de desajustes mantenido de forma incremental, y las definiciones de cada estadística que el estudio pone de relieve.

The apparatus behind the hint study: a parametric board generator faithful to Eternity II's colour recipe at every size, the family of fill-path backtrackers, the one canonical scorer, and the piece of arithmetic that keeps the count axis meaningful, the pinned-seam floor.

Los experimentos de búsqueda con nombre propio que persiguen la puntuación. Cada uno es un pipeline más que un único algoritmo: construye un tablero con un motor y luego lo eleva o lo remata con otro. Cada uno deja constancia de su idea, de su mejor tablero y de las preguntas que deja abiertas.

Un cuaderno de experimentos de búsqueda sobre Eternity II, organizado en torno a los motores compartidos sobre los que se ejecutan, las pipelines de combinación que persiguen la puntuación, tres estudios que desmontan un paradigma de búsqueda una decisión a la vez, y resoluciones exactas de final de partida. Cada uno expone su idea, su mejor tablero y las preguntas que deja abiertas. El mejor alcanza 463 de 480.

Las cinco comparaciones en el corazón del estudio de reparación, desarrolladas: la destrucción aleatoria ciega gana mientras que todo operador que apunta a los conflictos pierde; la construcción fija el suelo; el recocido simulado es la regla de aceptación más fuerte; y los refinamientos ingeniosos (recarga exacta, reinicios) no aportan nada con este presupuesto.

Las tres comparaciones en el corazón del estudio DFS, llevadas hasta el final: el orden de relleno (el recorrido por filas gana, un mal orden es catastrófico), las heurísticas (MRV rescata el borde primero pero cuesta rendimiento; más propagación no aportó nada) y las rupturas (rompen el muro de profundidad; el calendario de rupturas es la palanca, no el tope por celda).

The results, worked through: on these boards the five clue-shaped hints never help a backtracker, they range from a mild cost to a catastrophe, and the fill order decides how much damage they do; the scores are bimodal, not a smooth gradient; and the hint-count question is confounded by a free pinned-seam floor.

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.

La hermana del estudio DFS, para la otra manera en que se ataca Eternity II: destruir parte de un tablero, reconstruirla, conservar el cambio si ayuda. Una pregunta, planteada con cuidado. Qué aporta cada decisión de ese bucle: qué región destruir, cómo reconstruirla, cuándo conservar un movimiento, cuándo reiniciar, y desde qué tablero partir.

Give a backtracker five correct pieces for free, in the puzzle's own clue geometry. It turns out not to help, and depending on the fill order it can hurt badly, because a pinned piece is a hard constraint a fixed fill order must satisfy on arrival. A family of fill paths, run on the same hinted boards, single core, measured against no hints at all.

Experimentos exactos de final de partida que se encuentran en el medio: enumeran una región desde dos extremos y las unen por la costura, para hallar la verdadera mejor terminación con una prueba en lugar de la mejor conjetura de una heurística. Miden con exactitud una región pequeña en vez de perseguir la puntuación del tablero completo.