El aparato detrás del estudio de las pistas: un generador paramétrico de tableros fiel a la receta de colores de Eternity II en todos los tamaños, la familia de backtrackers por orden de relleno, el único puntuador canónico, y la pieza de aritmética que mantiene significativo el eje del número, el suelo de costuras fijadas.
por Raphaël Anjou
Esta página es el aparato detrás del estudio de las pistas: cómo se generan los tableros, por qué se mantienen fieles a Eternity II en todos los tamaños, la familia de órdenes de relleno, y la pieza que más importa para leer correctamente los resultados, la aritmética del suelo de costuras fijadas, que es lo que separa un efecto real de un artefacto de medición en el eje del número.
Cada instancia se genera desde cero, con semilla y determinista: el mismo triplete
(size, colours, seed) produce el mismo tablero en cualquier máquina. Un tablero
generado es un tablero resuelto, la pieza ocupa la celda con rotación
cero, cuyos identificadores de pieza se reetiquetan después mediante una
permutación con semilla, de modo que una pista para la celda pos fija la pieza
verdadera (reetiquetada), y un solucionador no puede simplemente recorrer la
colocación identidad.
La receta de colores refleja exactamente la estructura del puzzle oficial. En un tablero hay
costuras interiores (las aristas casadas; ). Estas se dividen en una banda de marco, las costuras que unen dos piezas de borde a lo largo del perímetro, y el interior profundo. Los cinco colores de borde están confinados a la banda de marco y nunca aparecen en el interior; los colores interiores aparecen tanto en el interior profundo como en la cara orientada hacia dentro de las piezas de borde. Este es el hecho estructural definitorio de un tablero Eternity II real, y el generador lo reproduce y se testea contra él.
Es tentador, y las primeras redacciones lo hicieron, presentar el censo de colores par de Eternity II como un regalo especialmente afinado: cada color aparece un número par de veces, de modo que los emparejamientos de una solución perfecta encajan con holgura cero. La paridad par es real, pero no es un logro de afinado. Está forzada.
Un color pintado sobre costuras interiores aparece en exactamente caras de pieza, una a cada lado de cada costura. Así que para todo color ,
La paridad de holgura cero es por tanto automática para cualquier tablero construido coloreando costuras; no dice nada especial sobre Eternity II. Las propiedades que de verdad soportan carga, y que el generador debe conseguir, son tres: los colores de borde confinados a la banda de marco, los recuentos por color mantenidos equilibrados (para que ningún color sea tan escaso que sobre-restrinja), y cada pieza distinta salvo rotación (para que una pista fijada nombre una pieza única). La redacción del estudio es precisa en esto donde el encuadre anterior no lo era.
El generador y el solucionador son ambos paramétricos en tamaño, el tablero puede ser o con la misma facilidad que , lo que abre una continuación natural: ¿se refuerza el efecto de la colocación conforme el tablero crece? Responder eso limpiamente necesita una receta de colores que no cambie la dificultad del puzzle cuando cambia el tamaño. Mantener simplemente fijos los recuentos de colores mientras crece haría el puzzle estructuralmente más fácil a grande: con más costuras y la misma paleta, cada color se repite más a menudo, la celda media acepta más vecinos y la restricción se afloja. Eso confundiría tamaño con dificultad.
En su lugar, la receta mantiene la multiplicidad por color aproximadamente constante. Escribiendo para el número de costuras de la banda de marco y para el interior, el número de colores de borde e interiores se elige como
apuntando a las multiplicidades que el propio Eternity II usa en (borde , interior ). En esto devuelve exactamente la receta oficial, cinco colores de borde y diecisiete interiores.
Conseguir esto en tableros pequeños exigió una corrección del generador. La paleta de Eternity II es de dominante interior, cinco colores de borde frente a diecisiete interiores, pero el generador por defecto limita el número de colores de borde a cinco y toma todo lo demás como interior, lo que en un tablero pequeño invierte la proporción: en la receta quiere ocho colores, y el tope los repartiría en cinco de borde y uno interior, un mar interior casi uniforme que no se comporta en nada como E2. El generador acepta ahora un número explícito de colores de borde, y la receta mantiene el interior en aproximadamente el triple del borde en cada tamaño ( dos de borde, seis interiores; cinco y diecisiete, sin cambio). Con eso, los tableros pequeños son fieles y plenamente resolubles, que es de lo que depende la comparación de velocidad de resolución de la página de resultados. Los resultados principales de órdenes y número están todos a ; el tablero se usa solo donde hace falta una resolución completa.
Cada disposición es una función pura del tamaño del tablero, de modo que la misma geometría puede dibujarse, medirse y escalarse de forma consistente. La galería de abajo las renderiza todas desde la única primitiva de tablero compartida.
Diez geometrías, un tablero. Activa las aristas para ver el suelo de puntuación gratis: las disposiciones agrupadas acumulan un montón de aristas garantizadas como correctas solo por estar fijadas una junto a otra, mientras que una disposición dispersa no acumula ninguna. Ese suelo explica por qué una comparación de puntuación bruta favorece al agrupamiento — y por qué el estudio mide en su lugar la profundidad alcanzada y la tasa de resolución.
Aquí está la sutileza que remodeló el estudio. Pregunte "¿ayudan más pistas?" y el movimiento obvio es comparar puntuaciones finales con distintos números de pistas. Pero una pista hace dos cosas distintas a la vez, y la puntuación las confunde:
El segundo efecto es un puro regalo contable. Definamos el suelo de costuras fijadas de una disposición como el número de costuras interiores con ambos extremos fijados:
Como los fijados son piezas de la solución verdadera, cada una de esas costuras está garantizada correcta antes de que el solucionador arranque. Un bloque agrupado macizo de aporta de ellas; cinco bloques de acumulan costuras correctas, un cuarto de las 480 totales, gratis. Una retícula dispersa, cuyas pistas nunca se tocan, tiene un suelo de cero.
Así que una comparación de puntuación bruta halaga sistemáticamente a las disposiciones agrupadas: parten con más de cien puntos de ventaja por pura contabilidad, con independencia de si el tablero se volvió más fácil de terminar. Es la misma familia de error que contar las costuras del perímetro en un tablero parcial, un suelo que infla el número sin reflejar progreso. El conmutador de la galería de arriba dibuja esas costuras acumuladas para que la puntuación gratuita sea visible.
El estudio, por tanto, no clasifica las disposiciones por puntuación bruta en el eje del número. Usa dos métricas inmunes al suelo:
Ambas miden si la búsqueda hizo un progreso que los fijados no le regalaron. En el eje de los órdenes, donde cada disposición comparada comparte las mismas pistas y por tanto el mismo suelo, la puntuación bruta es directamente comparable y se usa.
La pregunta "¿qué valen las pistas?" solo tiene respuesta relativa a no
tenerlas. Así que el eje de los órdenes se ejecuta dos veces en cada tablero: una
con las cinco pistas en forma de pistas oficiales, otra sin ninguna
(baseline_00), y el efecto reportado es la diferencia emparejada, la
puntuación con pistas menos la puntuación sin pistas sobre el mismo tablero
generado. Emparejar por instancia elimina la varianza de dificultad de tablero a
tablero, que en estos tableros bimodales es lo bastante grande como para ahogar el
efecto si las dos condiciones se compararan sobre semillas distintas. Una
diferencia emparejada negativa significa que las pistas hicieron ese orden de
relleno peor de lo que era con un interior en blanco, que es lo que reportan los
resultados. Todas las comparaciones usan el conjunto común de semillas que
llegaron a término, de modo que cada orden y cada disposición se agregan sobre
las instancias idénticas.
El motor es el backtracker DFS
hermano de este estudio, ejecutado en estricto (sin rupturas, sin propagación) de
modo que el orden de relleno sea lo único que cambia. Los órdenes probados son
fila por fila, su espejo de abajo arriba, la espiral hacia dentro, la espiral
hacia fuera, borde primero, el peine de Verhaard, un control de
filas-de-pistas-primero, y el orden propio del estudio que busca las pistas,
connect-hints-first.
¿Por qué importa tanto el orden? El coste de un backtracker lo gobierna la frontera abierta: el conjunto de celdas ya rellenas todavía adyacentes a una vacía. Cuando la siguiente celda se coloca contra una frontera de tamaño , el número de tableros parciales que la búsqueda puede tener que considerar crece multiplicativamente en , la ramificación es exponencial en la frontera, no en el tablero. Un único barrido compacto mantiene en torno a una fila (); un orden que abre manchas alrededor de pistas dispersas lleva fronteras a la vez, y
de modo que fragmentar el relleno en regiones desconectadas multiplica el coste,
no lo suma. Esto es exactamente por lo que connect-hints-first, el orden que
busca las pistas, es el peor: alcanzar las pistas pronto vale mucho menos que
mantener la frontera pequeña, y conectar anclas dispersas hace justo lo contrario
de mantenerla pequeña.
Cada tablero se vuelve a puntuar con un único puntuador canónico de aristas
casadas que nunca cuenta una costura orientada al borde (gris). El máximo es
( en ). Cada una de las quince semillas es una instancia
generada distinta, así que la dispersión entre semillas es varianza genuina de
instancia. El rendimiento, donde se reporta, es en nodos de búsqueda por segundo y
nunca se compara entre órdenes distintos, porque un nodo bajo un orden no es la
misma unidad de trabajo que bajo otro. Todo el aparato, generador, disposiciones,
resultados por ejecución y el script de rejilla, vive en el
directorio de respaldo
del estudio, y just experiments hint-study lo relanza todo.