Saltar al contenido
Eternity II

Glosario

Las palabras en las que se apoya el wiki, definidas de una vez por todas: la jerga de la comunidad, los términos informáticos que aquí tienen un sentido preciso y la notación con la que se escriben los tableros, cada uno con un enlace a la página que lo profundiza.

A

ALNS
Búsqueda adaptativa de gran vecindario: se destruye parte de un tablero, se reconstruye mejor y se aprende qué demoliciones rinden. El pulidor de tableros más fiable medido aquí. Ver →
aprendizaje de no-goods
Registrar que un estado parcial dado no se extiende, para que la búsqueda nunca vuelva a él. Rinde en tableros pequeños; el número de no-goods distintos supera la memoria en 16×16. Ver →
argumento de paridad
Contar algo del tablero dos veces, una por cada lado; los totales deben coincidir, lo que da pruebas de imposibilidad en una sola pasada. Ver →

Á

árbol de búsqueda
El árbol exponencial de todas las secuencias de colocación que un backtracker podría explorar. En Eternity II es astronómicamente grande y apenas reducible. Ver →

B

backtracking (retroceso)
Búsqueda en profundidad que coloca las piezas una a una en un orden fijo o calculado y deshace una colocación en cuanto lleva a un callejón sin salida. Todo motor récord pertenece a esta familia. Ver →
borde (marco)
El anillo exterior del tablero: las cuatro esquinas y las 56 piezas de borde, que muestran un lado gris (no puntuado) hacia afuera. El resto son piezas interiores. Ver →
búsqueda en peine
Un orden de llenado que recorre la mayoría de las filas en horizontal y luego barre las filas restantes en vertical, con la longitud del diente ajustada a un puntaje objetivo. El orden de Verhaard. Ver →
búsqueda local
Partir de un tablero completo pero imperfecto y mejorarlo mediante movimientos (intercambios, reubicaciones, destruir y reparar) guiados por el número de desajustes. Ver →
búsqueda tolerante a desajustes
Un backtracker que permite un presupuesto de desajustes deliberados, buscando un puntaje parcial alto (467, 469, 470) en lugar de un 480 perfecto. Ver →

C

callejón sin salida
Un tablero parcial del que se puede probar que no se extiende a ningún tablero completo. Reconocerlos pronto es para lo que sirve la poda. Ver →
cartera de reinicios
Ejecutar el mismo solucionador muchas veces con semillas aleatorias distintas, cortando cada corrida pronto. Todo solucionador récord desde 2007 es uno. Ver →
casilla
Uno de los 256 cuadros del tablero de 16×16. Ver →
cobertura exacta
El problema de elegir opciones para que cada elemento quede cubierto exactamente una vez. Eternity II se enuncia con limpieza como cobertura exacta con colores (XCC), siendo el algoritmo X de Knuth su máquina clásica. Ver →
codificación
Reescribir el puzle en el lenguaje de entrada de otro solucionador, por ejemplo como cláusulas SAT o restricciones CSP, para tomar prestada una década de ingeniería de ese solucionador. Ver →
cola pesada
Una distribución de tiempos de ejecución donde unas pocas corridas con mala suerte tardan órdenes de magnitud más que la mediana. Es lo que hace rentables los reinicios. Ver →
colocación
La asignación de una pieza dada, en una rotación dada, a una casilla dada. Ver →
comprobación anticipada (forward checking)
La propagación más ligera: al colocar una pieza, se la quita, junto con cualquier pieza ahora incompatible, de las listas de candidatos de las casillas vecinas. Ver →
consistencia de arco (AC-3)
Propagación que obliga a la lista de candidatos de cada casilla a resistir frente a sus vecinas hasta un punto fijo, yendo más allá del forward checking de un movimiento. Poda con fuerza en tableros pequeños y se apaga a unas dos casillas en el tablero completo. Ver →

D

déficit (equilibrio de borde)
Un desequilibrio en la costura entre el anillo de borde y el interior. Un tablero completable exige que sea cero, lo que da una condición necesaria barata. Ver →
deslizamiento de lado
Colocar a propósito una pieza desajustada según un calendario que depende de la profundidad, para que la búsqueda supere una barrera donde de otro modo se atascaría. La palanca tras el 467 de Verhaard. Ver →
dominio (de una variable)
El conjunto de valores que una variable aún puede tomar. Aquí, las opciones de pieza y rotación que le quedan a una casilla. Ver →

E

encuentro en el medio
Enumerar dos mitades del tablero y unirlas por una interfaz común, cambiando memoria por la mitad del exponente. Real en bandas, medido como dejar de rendir a tamaño completo. Ver →
enlaces danzantes (DLX)
La estructura de datos de Knuth para la cobertura exacta: listas doblemente enlazadas que cubren y descubren una columna en O(1) mediante cirugía de punteros, de modo que el retroceso sale barato. Ver →
entropía (ley de área)
Cuán rica es la gramática de emparejamiento por casilla. La entropía 2D bruta es modesta, y la regla de todos distintos la colapsa exponencialmente, lo que hace tan escasas las cuasisoluciones. Ver →
estricto-5 (estricto-canónico)
Un tablero que respeta las cinco pistas oficiales: la pieza central obligatoria más las cuatro colocaciones que revelan los puzles pista. La mayoría de los récords respeta solo el centro. Ver →

F

factor de ramificación
Cuántas colocaciones candidatas ofrece en promedio una casilla durante la búsqueda. En Eternity II se mantiene alto hasta el fondo del tablero, y por eso el árbol de búsqueda nunca colapsa. Ver →

H

heurística
Una regla que guía la búsqueda sin garantía de corrección, por ejemplo visitar primero la casilla más restringida, o desempatar por la rareza de las piezas. Ver →

Í

índice de rotura
El número de lados desajustados (rotos) en un tablero. Una solución completa tiene cero; el récord de la comunidad deja diez. El puntaje barato que todo solucionador optimiza, y una mala guía de cuán cerca está de verdad un tablero. Ver →

I

ingeniería de solucionadores
El oficio bajo el algoritmo: tablas de consulta, estructuras del tamaño de la caché, código generado. Decide si un nodo cuesta 26 ciclos o 2 600, y es la razón de que los motores récord funcionen siquiera. Ver →
invariante
Una propiedad cierta en toda solución completa (paridad, equilibrio de borde, conteos de colores). Rompe una y tienes una prueba de imposibilidad rápida. Ver →

L

lado (costura)
Una frontera compartida entre dos casillas adyacentes. El tablero de 16×16 tiene 480 lados interiores, que deben coincidir todos en una solución completa. Ver →
lado emparejado
Un lado que muestra el mismo color en ambos costados. El puntaje es el conteo de lados emparejados, sobre 480; un desajuste es lo contrario. Ver →
lado gris
Un lado orientado hacia el borde, coloreado de gris y nunca puntuado. Las piezas interiores no tienen ninguno; las de borde y esquina muestran uno o dos. Ver →
lista de candidatos
El conjunto de opciones de pieza y rotación aún legales para una casilla tras la propagación. Reducirlo es todo el sentido de la propagación de restricciones. Ver →

M

motivo
El glifo impreso que representa cada color de lado en las fichas físicas. Este sitio sabe dibujar los tableros con los motivos reales. Ver →
muro
Una barrera que detiene a un solucionador en un puntaje: el muro de rigidez (sin mejora local), el muro de los σ-ciclos (sin salto de cuenca), el muro de profundidad (la búsqueda en amplitud se atasca). Cada método muere en un muro distinto. Ver →
muro de rigidez
El hecho probado de que los tableros récord están congelados localmente: liberar y reoptimizar el halo en torno a los desajustes no encuentra mejora. La barrera central del puzle. Ver →

N

nodo
Un estado del árbol de búsqueda. El coste por nodo, el tiempo de evaluar uno, es lo que la ingeniería de solucionadores baja. Ver →
notación Bucas
El formato de texto compartido por la comunidad para un tablero, del visor de Jef Bucas: filas A a P, columnas 1 a 16, cada casilla con un id de pieza y una rotación. La lengua franca que todo solucionador lee y escribe. Ver →

Ó

óptimo local
Un tablero sin ningún movimiento de mejora. Los tableros récord están congelados en uno: el paso hacia un tablero perfecto no es una mejora local. Ver →

O

orden de llenado
La secuencia en que un backtracker visita las 256 casillas. Su única elección libre, y mueve el tamaño del árbol de búsqueda en órdenes de magnitud sin coste de ejecución. Ver →

P

patrón prohibido
Una pequeña configuración local que nunca puede casar, de modo que ninguna solución la contiene. En Eternity II casi toda disposición 2×2 de piezas está prohibida. Ver →
pieza
Una de las 256 fichas cuadradas, cada una con cuatro lados de color. También llamada ficha. Ver →
pieza interior
Una de las 196 piezas sin lado gris, que solo puede situarse lejos del borde. Ver →
pista
Una casilla cuya pieza y rotación se dan de antemano, ya sea la pista central obligatoria o una revelada por un puzle pista. Dónde se sitúan las pistas importa más que cuántas son. Ver →
poda
Descartar toda una rama de la búsqueda sin explorarla, mediante una restricción, una cota o una prueba de imposibilidad. Ver →
propagación
Véase propagación de restricciones: quitar los candidatos que una colocación deja muertos, en cascada hasta un punto fijo. Ver →
propagación de restricciones
Eliminación automática de los candidatos que ya no pueden llevar a un tablero legal, con el efecto encadenándose hasta que no queda nada más que quitar (un punto fijo). Ver →
puntaje
El número de lados emparejados en un tablero, sobre 480. Una solución perfecta puntúa 480; el récord de la comunidad puntúa 470. Ver →
puzle pista
Uno de los cuatro puzles complementarios opcionales (dos de 6×6 y dos de 12×6) que, al resolverse, revelaba cada uno una colocación de pieza en el tablero principal. Ver →

R

recocido (recocido simulado)
Búsqueda local que trata los desajustes como energía y la temperatura como tolerancia a empeorar, enfriándose despacio hacia un buen tablero. Ostenta el récord más antiguo de su familia. Ver →
relajación (LP/ILP)
Renunciar al requisito de piezas enteras para que un solucionador lineal pueda colocar fracciones de piezas y llegar a error cero, y pagarlo luego al restablecer la integralidad. Ver →
robo de pieza
Gastar pronto una pieza escasa en el lugar equivocado, de modo que una casilla posterior que la necesitaba se queda sin nada con que llenarla. Donde muchas búsquedas mueren en silencio. Ver →

S

SAT
Satisfacibilidad booleana: ¿existe una asignación que satisfaga cada cláusula? Los solucionadores SAT completos se atascan en el tablero entero, pero aun así prueban imposibles los subtableros. Ver →

T

tabla de transposición
Una tabla hash de estados ya evaluados, para no reexplorar subárboles idénticos. Su tasa de aciertos es baja en Eternity II. Ver →
templado (templado paralelo)
Ejecutar varias cadenas de recocido a distintas temperaturas e intercambiar periódicamente sus estados, para que la búsqueda cruce barreras que una sola cadena no puede. Ver →
todos distintos (filtro de Régin)
La restricción global que exige que cada una de las 256 piezas se use exactamente una vez, filtrada por completo en tiempo polinómico mediante un emparejamiento bipartito que descarta cualquier pieza que ya no pueda colocarse. Ver →
transición de fase
El pico de dificultad donde las soluciones son escasas pero existen. Los 22 colores de Eternity II lo sitúan justo en ese pico, por diseño. Ver →

U

URDL
Arriba, derecha, abajo, izquierda: el orden en que se escriben los cuatro colores de lado de una pieza, y el sentido de una rotación horaria. Ver →

V

vacío (void)
Un par de colores de esquina que ninguna pieza interior puede presentar, de modo que una casilla que lo exige es un callejón sin salida antes de colocar pieza alguna. Ver →
velocidad del solucionador (nodos por segundo)
El rendimiento: cuántas colocaciones evalúa un solucionador por segundo. Cambia los tableros a los que llegas, no el techo con el que chocas. Ver →

X

XCC (cobertura exacta con colores)
La extensión de Knuth de la cobertura exacta con elementos secundarios coloreados, que modela con fidelidad el emparejamiento de lados. El enunciado limpio de Eternity II como cobertura exacta. Ver →

Σ

σ-ciclo (ciclo sigma)
Un bucle entrelazado de movimientos de piezas que conecta dos configuraciones de tablero. Como toda aplicación parcial puntúa peor, no se puede pasar de una cuenca a otra de forma gradual. Ver →