Construir un solucionador

Un kit de inicio en Rust listo para usar para construir tu propio solucionador de Eternity II: puntuar, generar tableros con equilibrio de colores real, generar lotes con pistas fijadas, convertir todos los formatos, medir el rendimiento y un bucle resolver→barrer→comparar, donde solo escribes el solucionador. Además, una configuración de una línea para agentes de código y un generador de tableros directamente en el navegador.

La síntesis que la comunidad reclama sin encontrarla nunca: cada familia de ataque probada en Eternity II, lo que cada una alcanzó realmente, dónde se estrella, y un enlace a la página de fondo. Una misma idea rectora las atraviesa todas.

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.

Las cifras que todo investigador de Eternity II acaba redemostrando, reunidas en un solo lugar con su procedencia: la definición del puzzle, la colocación de las pistas, las convenciones de puntuación, la tabla de récords, el tamaño del espacio de búsqueda y los recuentos estructurales.

Cómo una comunidad a la que se le prohibió compartir las piezas construyó aun así una cultura de pruebas compartida: protocolos de verificación por conteos derivados, las suites Txibilis y para principiantes, duelos al número de nodos, enumeraciones completas y el único benchmark que sigue abierto hoy.

Diecinueve años de software comunitario para Eternity II (interfaces de colocación manual, editores, solucionadores públicos, generadores y visualizadores), más la capa más discreta que los hizo interoperar: e2pieces.txt, las sumas de comprobación CRC-16 y el formato tablero-en-una-URL que se convirtió en la lingua franca. Un censo de referencia, con cada herramienta rastreada hasta el mensaje que la anunció.

Tomy vendió cuatro pequeños puzzles complementarios de Eternity II: resuelve uno, envía la solución y el sitio oficial revelaba la posición de una pieza en el tablero principal. Qué era cada puzzle, el verificador en línea defectuoso, el mercado gris de eBay, por qué los puzzles 5 y 6 nunca llegaron, y la segunda vida de los puzzles-pista como casos de prueba para la teoría de complejos y como juegos de piezas donantes.

Todos los «Eternity II» que no son el puzzle real: la variante Marathon de TopCoder y el 468 sin resolver de Takahashi, el 480/480 sin marco de McGavin, los tableros de juegos mezclados, el desafío sin pieza inicial y la cuarentena de afirmaciones, desde la advertencia de 2007 sobre los juegos fantasma hasta la ética comunitaria de verificación de conocimiento cero. Termina con una lista de comprobación para enunciar una puntuación correctamente.

Cómo buscan en realidad los solucionadores que ostentan los récords. Todos son, en el fondo, backtrackers en profundidad; lo que los distingue es el orden en que prueban las cosas y cómo doblan las reglas al acercarse al final.

Todo lo que descarta estados sin esperanza antes de que la búsqueda pierda tiempo en ellos: propagación hasta el punto fijo, el filtro de emparejamiento all-different, no-goods aprendidos y el invariante de deslizamiento de bordes.

La búsqueda en profundidad tomada en serio. El orden en que un solucionador visita las celdas es su única elección libre y hace variar el tamaño del árbol en órdenes de magnitud; los reinicios convierten un tiempo de ejecución de cola pesada en un portafolio. Esta es la familia detrás de cada backtracker récord.

Rendimiento en bruto: el oficio por debajo del algoritmo (tablas de consulta, estructuras dimensionadas para la caché, código generado) y la distribución del trabajo entre muchas máquinas. Es lo que decide si un nodo cuesta 26 ciclos o 2600, y es la demostración más clara de que la velocidad por sí sola no mueve el muro.

Construir un tablero de alta puntuación a partir de una cuadrícula vacía en lugar de excavar con backtracking: la búsqueda en haz mantiene vivos los mejores tableros parciales y los hace crecer celda a celda. El caballo de batalla de los constructores desde cero de este proyecto, y una ilustración nítida de por qué la amplitud por sí sola se atasca en las profundidades del interior.

La mayoría de los ataques a Eternity II buscan partiendo de cero. Una familia distinta hace lo contrario: explora el corpus de tableros que la gente ya ha encontrado en busca de estructura, y luego reinyecta esa estructura en la búsqueda. Priors de posición, ordenación aprendida de jugadas, minería de antipatrones, decodificación de récords y el modo de fallo en el que una señal aprendida se derrumba.

Parte de un tablero completo pero imperfecto y mejóralo mediante movimientos: destrucción-reparación, recocido y templado, recombinación evolutiva. Los pulidores más fiables del sitio, y las demostraciones más nítidas del muro de rigidez, donde cada uno de ellos se detiene a la misma altura.

El estante de técnicas: los algoritmos y las ideas de poda que reaparecen en todo solucionador serio de Eternity II, cada uno con lo que es, lo que cuesta y lo que realmente aportó al medirse sobre este puzzle.

Solucionadores capaces de demostrar: codificaciones SAT y CSP, programación entera y sus relajaciones, cobertura exacta, encuentro en el medio y mapas de proyección iterados. Los métodos completos se atascan en el tablero completo, pero sus veredictos se ganan su lugar como pruebas de imposibilidad en subtableros.

Estos métodos no intentan resolver el puzzle: lo miden, y así es como la comunidad sabe dónde están los muros. Los argumentos de paridad aportan pruebas de imposibilidad en una sola pasada; el conteo de soluciones fija cuántas soluciones completas existen con un margen de un factor dos, sin que nadie haya visto ninguna.

Lanzar silicio contra el muro: portes a GPU, pipelines FPGA, barridos distribuidos y la eterna propuesta cuántica. Este es el balance de lo que cada uno aportó realmente, y por qué el muro que encuentran es la memoria y la estructura, no la aritmética.

Enfoques que probamos que parecen prometedores y no mueven la aguja en Eternity II, documentados con lo que encontramos para que inviertas tu tiempo en otra parte.

Un conjunto de datos público bajo licencia CC0 para Eternity II, en dos partes: catorce instancias de referencia para resolver, y un corpus de 7658 tableros fuertes distintos de los que aprender. Cada puntuación se recalcula a partir del propio tablero, y se verifica que el corpus sea realmente variado, en lugar de mil copias de un mismo tablero.

Todo el sitio, el motor y cada resultado de esta sección se ejecutan desde un único repositorio. Aquí tienes cómo ponerlo en marcha, recompilar el motor WebAssembly y reproducir las cifras.

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.