Aller au contenu
Eternity II

Glossaire

Les mots sur lesquels le wiki s'appuie, définis une bonne fois. Le jargon de la communauté, les termes d'informatique au sens précis ici, et la notation dans laquelle les plateaux s'écrivent ; chacun avec un lien vers la page qui approfondit.

A

ALNS
Recherche adaptative à grand voisinage : on détruit une partie du plateau, on la reconstruit en mieux, et on apprend quelles démolitions rapportent. Le polisseur de plateau le plus fiable mesuré ici. Voir →
apprentissage de no-goods
Enregistrer qu'un état partiel donné ne s'étend pas, pour que la recherche n'y revienne jamais. Rentable sur les petits plateaux ; le nombre de no-goods distincts dépasse la mémoire en 16×16. Voir →
arbre de recherche
L'arbre exponentiel de toutes les séquences de placement qu'un backtracker pourrait explorer. Sur Eternity II il est astronomiquement grand et à peine réductible. Voir →
argument de parité
Compter quelque chose sur le plateau deux fois, une fois de chaque côté ; les totaux doivent concorder, ce qui donne des preuves d'impossibilité en une passe. Voir →

B

bord (couture)
Une frontière partagée entre deux cases adjacentes. Le plateau 16×16 compte 480 bords intérieurs, qui doivent tous correspondre dans une solution complète. Voir →
bord apparié
Un bord montrant la même couleur des deux côtés. Le score est le nombre de bords appariés, sur 480 ; un défaut en est l'opposé. Voir →
bord gris
Un bord tourné vers l'extérieur, coloré en gris et jamais compté. Les pièces intérieures n'en ont aucun ; les pièces de bord et de coin en montrent un ou deux. Voir →
bordure (cadre)
L'anneau extérieur du plateau : les quatre coins et les 56 pièces de bord, qui présentent un bord gris (non compté) vers l'extérieur. Le reste sont des pièces intérieures. Voir →

C

case
L'une des 256 cases du plateau 16×16. Voir →
cohérence d'arc (AC-3)
Propagation qui force la liste de candidats de chaque case à tenir face à ses voisines jusqu'à un point fixe, allant plus loin que le forward checking à un coup d'avance. Élague fort sur les petits plateaux, s'estompe à deux cases environ sur le plateau complet. Voir →
couverture exacte
Le problème de choisir des options pour que chaque élément soit couvert exactement une fois. Eternity II s'énonce proprement comme couverture exacte avec couleurs (XCC), l'algorithme X de Knuth en étant la machine classique. Voir →

D

déficit (équilibre de bordure)
Un déséquilibre sur la couture entre l'anneau de bordure et l'intérieur. Un plateau complétable exige qu'il soit nul, ce qui donne une condition nécessaire bon marché. Voir →
domaine (d'une variable)
L'ensemble des valeurs qu'une variable peut encore prendre. Ici, les options pièce-et-rotation restantes pour une case. Voir →

É

élagage
Écarter toute une branche de la recherche sans l'explorer, au moyen d'une contrainte, d'une borne ou d'une preuve d'impossibilité. Voir →

E

encodage
Réécrire le puzzle dans le langage d'entrée d'un autre solveur, par exemple en clauses SAT ou en contraintes CSP, pour emprunter une décennie d'ingénierie de ce solveur. Voir →
entropie (loi d'aire)
La richesse de la grammaire d'appariement par case. L'entropie 2D brute est modeste, et la règle tous-distincts l'effondre exponentiellement, ce qui rend les quasi-solutions si rares. Voir →

F

facteur de branchement
Le nombre moyen de placements candidats qu'offre une case pendant la recherche. Sur Eternity II il reste élevé jusqu'au fond du plateau, et c'est pourquoi l'arbre de recherche ne s'effondre jamais. Voir →

G

glissement de bord
Placer délibérément une pièce en défaut selon un calendrier dépendant de la profondeur, afin que la recherche franchisse une barrière où elle calerait sinon. Le levier derrière le 467 de Verhaard. Voir →

H

heuristique
Une règle qui guide la recherche sans aucune garantie de justesse, par exemple visiter d'abord la case la plus contrainte, ou départager par la rareté des pièces. Voir →

I

impasse
Un plateau partiel dont on peut prouver qu'il ne s'étend à aucun plateau complet. Les reconnaître tôt, c'est tout l'objet de l'élagage. Voir →
indice
Une case dont la pièce et la rotation sont données d'avance, qu'il s'agisse de l'indice central obligatoire ou d'un indice révélé par un puzzle indice. L'emplacement des indices compte plus que leur nombre. Voir →
indice de rupture
Le nombre de bords en défaut (rompus) sur un plateau. Une solution complète en a zéro ; le record de la communauté en laisse dix. Le score bon marché que tout solveur optimise, et un mauvais guide de la distance réelle à la solution. Voir →
ingénierie de solveur
L'artisanat sous l'algorithme : tables de correspondance, structures taillées pour le cache, code généré. Il décide si un nœud coûte 26 cycles ou 2 600, et c'est pourquoi les moteurs record tournent tout court. Voir →
invariant
Une propriété vraie de toute solution complète (parité, équilibre de bordure, comptes de couleurs). En briser une, et l'on tient une preuve d'impossibilité rapide. Voir →

L

liens dansants (DLX)
La structure de données de Knuth pour la couverture exacte : des listes doublement chaînées qui couvrent et découvrent une colonne en O(1) par chirurgie de pointeurs, rendant le retour arrière peu coûteux. Voir →
liste de candidats
L'ensemble des options pièce-et-rotation encore légales pour une case après propagation. La réduire est tout l'objet de la propagation de contraintes. Voir →

M

motif
Le glyphe imprimé qui représente chaque couleur de bord sur les tuiles physiques. Ce site sait afficher les plateaux avec les vrais motifs. Voir →
motif interdit
Une petite configuration locale qui ne peut jamais correspondre, donc qu'aucune solution ne contient. Sur Eternity II, presque tout agencement 2×2 de pièces est interdit. Voir →
mur
Une barrière qui arrête un solveur à un score : le mur de rigidité (aucune amélioration locale), le mur des σ-cycles (aucun saut de bassin), le mur de profondeur (la recherche en largeur cale). Chaque méthode meurt sur un mur différent. Voir →
mur de rigidité
Le fait prouvé que les plateaux record sont localement figés : libérer et réoptimiser le halo autour des défauts ne trouve aucune amélioration. La barrière centrale du puzzle. Voir →

N

nœud
Un état de l'arbre de recherche. Le coût par nœud, le temps d'en évaluer un, est ce que l'ingénierie de solveur cherche à réduire. Voir →
notation Bucas
Le format texte partagé par la communauté pour un plateau, issu du visualiseur de Jef Bucas : lignes A à P, colonnes 1 à 16, chaque case étant un identifiant de pièce et une rotation. La langue commune que tout solveur lit et écrit. Voir →

O

optimum local
Un plateau sans aucun coup améliorant. Les plateaux record y sont figés : le pas vers un plateau parfait n'est pas une amélioration locale. Voir →
ordre de remplissage
La séquence dans laquelle un backtracker visite les 256 cases. Son seul choix libre, et il déplace la taille de l'arbre de recherche de plusieurs ordres de grandeur sans coût d'exécution. Voir →

P

pièce
L'une des 256 tuiles carrées, chacune à quatre bords colorés. Aussi appelée tuile. Voir →
pièce intérieure
L'une des 196 pièces sans bord gris, qui ne peut se placer qu'à l'écart de la bordure. Voir →
placement
L'affectation d'une pièce donnée, à une rotation donnée, à une case donnée. Voir →
portefeuille de redémarrages
Lancer le même solveur de nombreuses fois avec des graines aléatoires différentes, en coupant chaque exécution tôt. Tout solveur record depuis 2007 en est un. Voir →
propagation
Voir propagation de contraintes : retirer les candidats rendus morts par un placement, en cascade jusqu'à un point fixe. Voir →
propagation de contraintes
Suppression automatique des candidats qui ne peuvent plus mener à un plateau légal, l'effet se propageant jusqu'à ce que plus rien ne puisse être retiré (un point fixe). Voir →
puzzle indice
L'un des quatre puzzles compagnons optionnels (deux 6×6 et deux 12×6) qui, une fois résolus, révélaient chacun un placement de pièce sur le plateau principal. Voir →

Q

queue lourde
Une distribution de temps d'exécution où quelques exécutions malchanceuses durent plusieurs ordres de grandeur de plus que la médiane. C'est ce qui rend les redémarrages rentables. Voir →

R

recherche en peigne
Un ordre de remplissage qui balaie la plupart des lignes horizontalement, puis parcourt les lignes restantes verticalement, la longueur de la dent étant réglée sur un score cible. L'ordre de Verhaard. Voir →
recherche locale
Partir d'un plateau complet mais imparfait et l'améliorer par des coups (échanges, relocalisations, détruire-et-réparer) guidés par le nombre de défauts. Voir →
recherche tolérante aux défauts
Un backtracker qui autorise un budget de défauts délibérés, visant un score partiel élevé (467, 469, 470) plutôt qu'un 480 parfait. Voir →
recuit (recuit simulé)
Recherche locale qui traite les défauts comme de l'énergie et la température comme une tolérance à l'aggravation, refroidissant lentement vers un bon plateau. Détient le plus ancien record de sa famille. Voir →
relaxation (LP/ILP)
Abandonner l'exigence de pièces entières pour qu'un solveur linéaire puisse placer des fractions de pièces et atteindre une erreur nulle, puis le payer lorsqu'on rétablit l'intégralité. Voir →
rencontre au milieu
Énumérer deux moitiés du plateau et les joindre sur une interface commune, échangeant de la mémoire contre la moitié de l'exposant. Réel sur des bandes, mesuré comme cessant de payer à taille pleine. Voir →
retour arrière (backtracking)
Recherche en profondeur qui pose les pièces une à une dans un ordre fixe ou calculé, défaisant un placement dès qu'il mène à une impasse. Tout moteur record appartient à cette famille. Voir →

S

SAT
Satisfiabilité booléenne : existe-t-il une affectation satisfaisant chaque clause ? Les solveurs SAT complets calent sur le plateau entier mais prouvent tout de même l'impossibilité de sous-plateaux. Voir →
score
Le nombre de bords appariés sur un plateau, sur 480. Une solution parfaite fait 480 ; le record de la communauté fait 470. Voir →
strict-5 (strict-canonique)
Un plateau qui respecte les cinq indices officiels : la pièce centrale obligatoire plus les quatre placements révélés par les puzzles indices. La plupart des records ne respectent que le centre. Voir →

T

table de transposition
Une table de hachage des états déjà évalués, pour ne pas réexplorer des sous-arbres identiques. Son taux de succès est faible sur Eternity II. Voir →
tous différents (filtre de Régin)
La contrainte globale qui impose que chacune des 256 pièces serve exactement une fois, filtrée entièrement en temps polynomial par un test de couplage biparti qui écarte toute pièce devenue improuvable. Voir →
transition de phase
Le pic de difficulté où les solutions sont rares mais existent bel et bien. Les 22 couleurs d'Eternity II le placent pile sur ce pic, par conception. Voir →
trempe (trempe parallèle)
Faire tourner plusieurs chaînes de recuit à des températures différentes et échanger périodiquement leurs états, pour que la recherche franchisse des barrières qu'une seule chaîne ne peut passer. Voir →

U

URDL
Haut, droite, bas, gauche : l'ordre dans lequel s'écrivent les quatre couleurs de bord d'une pièce, et le sens d'une rotation horaire. Voir →

V

vérification anticipée (forward checking)
La propagation la plus légère : quand une pièce est posée, on la retire, ainsi que toute pièce devenue incompatible, des listes de candidats des cases voisines. Voir →
vide (void)
Une paire de couleurs d'angle qu'aucune pièce intérieure ne peut présenter, si bien qu'une case qui l'exige est une impasse avant même qu'aucune pièce ne soit posée. Voir →
vitesse de solveur (nœuds par seconde)
Le débit : combien de placements un solveur évalue par seconde. Il change les plateaux que l'on atteint, pas le plafond auquel on se heurte. Voir →
vol de pièce
Dépenser tôt une pièce rare au mauvais endroit, si bien qu'une case ultérieure qui en avait besoin n'a plus rien pour la remplir. Là où bien des recherches meurent en silence. Voir →

X

XCC (couverture exacte avec couleurs)
L'extension par Knuth de la couverture exacte avec des éléments secondaires colorés, qui modélise fidèlement l'appariement des bords. L'énoncé propre d'Eternity II comme couverture exacte. Voir →

Σ

σ-cycle (cycle sigma)
Une boucle imbriquée de mouvements de pièces reliant deux configurations de plateau. Comme toute application partielle score moins bien, on ne peut passer d'un bassin à l'autre progressivement. Voir →