Comment cherchent réellement les solveurs qui détiennent les records. Ce sont tous, au fond, des backtrackers en profondeur d'abord ; ce qui les distingue, c'est l'ordre dans lequel ils essaient les choses et la manière dont ils assouplissent les règles à l'approche de la fin.
Tout solveur qui détient un record sérieux à Eternity II est, au fond, la même machine : un backtracker en profondeur d'abord. Ce qui les distingue, ce n'est pas la boucle, mais trois choix qui se superposent à celle-ci : l'ordre dans lequel ils visitent les cases, les heuristiques qui décident quelle pièce essayer en premier, et la manière dont ils assouplissent la fin de partie lorsqu'il n'existe plus de correspondance parfaite. Cette page est la visite neutre de ces choix. L'histoire complète et de première main de chaque moteur (décodée à partir du code source et de la littérature, puis reconstruite et mesurée) vit sur sa propre page de laboratoire, reliée depuis chaque section ci-dessous.
Avant la visite, le catalogue : une ligne par moteur, et les quatre choix qui le distinguent. Chaque portée est mesurée sur un seul cœur, sur une même machine, si bien que les chiffres se comparent à l'identique plutôt que d'un cluster à l'autre ; chaque ligne renvoie à son compte rendu complet.
| Moteur | Ordre de remplissage | Élagage | Régime matériel | Portée mesurée |
|---|---|---|---|---|
| Backtracker de Blackwood | balayage par rangée depuis le bas-gauche, pièces de bord tard | quota de couleur par profondeur plus un budget d'indice de rupture selon la profondeur | un seul cœur ; le 470 est venu de nombreux cœurs en parallèle | 248/256 pièces sans contrainte ; s'arrête vers 45 une fois les cinq indices fixés |
| eii de Verhaard | ordres de recherche en peigne | élagage anticipé face à des seuils de score réglés ; un calendrier de glissement réglé par Markov | binaire Win32 sur un cœur ; pas de source à recompiler | 467/480, le seul prix que le concours a payé |
| Backtracker C de McGavin | selon le puzzle : balayage par rangée, spirale, ou bord d'abord | code généré plus tables de correspondance et astuces de compteur pour le débit brut | un seul cœur, ~109M placements/s sur le vrai puzzle | au-delà de 200/256 pièces ; conçu pour la vitesse, pas pour un score record |
| Réimplémentation de Verhaard | recuit par échange de composition d'ensembles sous la métrique 2×2 | acceptation par recuit, constantes récupérées au bit près depuis le binaire | un seul cœur ; exécution versionnée et réexécutable | 438/480 sur le vrai puzzle à cinq indices |
| Préréglages CSP, mesurés | une douzaine de préréglages d'ordre, bord d'abord le meilleur | propagation par cohérence d'arc | un seul cœur, dix variantes ancrées par coin | près de 183 sur les variantes ancrées ; sous la moitié du score d'un prétendant |
La visite ci-dessous parcourt les trois choix que ces lignes partagent.
Remplir le plateau case par case selon un ordre fixé. À chaque case, essayer toute pièce et toute rotation dont les bords correspondent à ce qui est déjà posé ; si aucune ne convient, revenir en arrière et essayer autrement la case précédente. Correct mais lent : l'arbre de recherche est d'une largeur astronomique.
Voici exactement cela, au ralenti : un vrai backtracker sur une grille 3×3, une décision à la fois. Avancez pas à pas et observez une pièce se poser, une impasse apparaître, puis la recherche retirer la pièce et réessayer.
L'ordre dans lequel vous visitez les cases modifie la difficulté de plusieurs ordres de grandeur, car certains ordres forcent les conflits à apparaître tôt (c'est bon) tandis que d'autres les repoussent jusqu'à ce que beaucoup de travail soit gaspillé (c'est mauvais). Commencer par la bordure l'emporte largement sur un parcours ligne par ligne sur le même puzzle. C'est l'unique levier que règle chaque moteur record : les ordres de recherche en peigne de Verhaard, le balayage de Blackwood en lignes depuis le coin inférieur gauche avec les pièces de bordure intercalées tardivement, et le choix par McGavin, puzzle par puzzle, entre balayage en lignes, spirale vers l'intérieur ou bordure d'abord sont tous des réponses à la même question.
Un backtracker élémentaire essaie les candidats dans un ordre arbitraire. Un moteur record les note, de sorte que les pièces les plus susceptibles de compter se posent en premier, et il élague toute branche qui prend du retard sur un calendrier. Le solveur de Blackwood, par exemple, privilégie trois couleurs et impose un quota par profondeur qui doit être atteint pour continuer à descendre ; Verhaard élague vers l'avant en s'appuyant sur des seuils de score réglés à la main. Les détails diffèrent, mais la forme est partagée : engager tôt les pièces contraintes, couper les branches qui ne peuvent pas rentabiliser leur coût.
Un pavage parfait de 256 pièces n'a jamais été trouvé. Chaque plateau record tolère plutôt une poignée de non-correspondances tardives, et les moteurs les atteignent en planifiant l'imperfection : un budget par profondeur de bords non appariés qui se débloque au plus profond de la recherche. Verhaard appelait le sien un tableau de glissement (slip array) ; Blackwood appelle le sien les indices de rupture (break indexes). Même idée, conditionnée par la profondeur pour que le début du plateau reste propre et que les non-correspondances ne soient dépensées que là où elles rapportent le plus.
Le laboratoire ci-dessous vous permet de déplacer ce budget et d'observer comment le score atteignable évolue :
Un puzzle 8×8 fixe, le vrai solveur tournant dans votre navigateur. Une rupture — un seul défaut autorisé — n'est permise que dans les rangées du bas que vous autorisez ci-dessous, à l'image des solveurs records qui confinent les ruptures à quelques positions fixes. Sans aucune, la recherche stricte cale sous un plateau complet. Autorisez une rangée ou deux et il termine, quasi parfait.
Essayez d'abord une seule rangée : où les ruptures sont autorisées compte autant que combien. Dispersez-en autant en haut et le plateau ne finira pas — les conflits que cet ordre de balayage accumule tombent en bas.
Chaque moteur record dispose d'une page dédiée qui décode son fonctionnement, puis le reconstruit et le mesure sur une seule machine, en mono-cœur :
Le bac à sable exécute un vrai solveur en profondeur d'abord dans votre navigateur. Regardez-le chercher en direct, ou dessinez votre propre ordre de remplissage et lancez-le en course contre les classiques pour ressentir à quel point l'ordre compte.
Pour les approches qui ne fonctionnent pas, voir les impasses.