Mesures

Quinze solveurs, les nôtres et nos implémentations des deux backtrackers record de la communauté, chacun exécuté une fois sur dix variantes à coins épinglés du casse-tête officiel, un seul cœur, 60 secondes par exécution. Le constat : le nombre de nœuds n'est pas le score.

Le backtracker C de Peter McGavin, le plus rapide de la communauté : une recette d'optimisation de 2007 capitalisée pendant deux décennies via code généré, tables de correspondance et astuces de compteur, puis compilée sur mon M1 et pointée vers le vrai puzzle à 256 pièces, où en mono-cœur elle dépasse 200 des 256 pièces à ~109M placements/s.

Le backtracker record de Joshua Blackwood, décodé grâce aux notes de Jef Bucas (un échéancier de quotas de couleurs et une tolérance aux mismatchs en fin de partie, réglés presque optimalement), puis construit et exécuté sur mon M1 : tel que publié, il file jusqu'à 248 des 256 pièces en ignorant les indices ; épinglez les cinq indices officiels et le même moteur cale autour de 45.

Un seul moteur de propagation de contraintes, exécuté sous une douzaine de presets d'ordonnancement et de propagateurs, sur les dix mêmes variantes à coins fixés que le classement. Une étude de ce qu'apporte chaque réglage, tenue à l'écart du classement principal parce que le meilleur preset atteint moins de la moitié du score d'un prétendant.

Les cinq comparaisons au cœur de l'étude sur la réparation, décortiquées : la destruction aléatoire aveugle l'emporte tandis que tout opérateur ciblant les conflits perd ; la construction fixe le plancher ; le recuit simulé est la règle d'acceptation la plus forte ; et les raffinements astucieux (recharge exacte, redémarrages) ne rapportent rien à ce budget.

Les trois comparaisons au cœur de l'étude DFS, menées jusqu'au bout : l'ordre de remplissage (le balayage par lignes gagne, un mauvais ordre est catastrophique), les heuristiques (MRV sauve le remplissage du bord d'abord mais coûte du débit ; davantage de propagation n'a rien apporté) et les ruptures (elles brisent le mur de profondeur ; le levier, c'est le calendrier de ruptures, pas le plafond par cellule).

Les résultats, développés : sur ces plateaux les cinq indices en forme d'indices officiels n'aident jamais un backtracker, ils vont d'un coût modéré à une catastrophe, et l'ordre de remplissage décide de l'ampleur des dégâts ; les scores sont bimodaux, pas un gradient lisse ; et la question du nombre d'indices est confondue par un plancher gratuit de coutures épinglées.

Une seule question, posée avec soin : parmi les backtrackers en profondeur d'abord pour Eternity II, qu'apporte réellement chaque ordre de remplissage, chaque heuristique et le mécanisme de rupture ? Une famille de backtrackers écrits de zéro, séparés chacun par un seul changement, exécutés sur les mêmes dix variantes à coins fixés, sur un seul cœur, pendant soixante secondes.

Donner à un backtracker cinq pièces correctes gratuitement, dans la géométrie même des indices du puzzle. Il s'avère que cela n'aide pas, et selon l'ordre de remplissage cela peut nuire gravement, car une pièce épinglée est une contrainte dure qu'un ordre de remplissage fixe doit satisfaire à son arrivée. Une famille d'ordres de remplissage, exécutée sur les mêmes plateaux indicés, un seul cœur, mesurée contre l'absence totale d'indices.

La jumelle de l'étude DFS, pour l'autre manière d'attaquer Eternity II : détruire une partie d'un plateau, la reconstruire, garder le changement s'il aide. Une question, posée avec soin. Que rapporte chaque décision de cette boucle : quelle région détruire, comment la reconstruire, quand garder un mouvement, quand redémarrer, et de quel plateau partir ?

Un backtracker Rust en profondeur d'abord, sûr et portable, spécialisé à l'exécution en émettant puis compilant du Rust propre à chaque puzzle, porté de 43 à 123 millions de nœuds de recherche par seconde sur un cœur. Mesuré équitablement face au C de Peter McGavin sur la même machine : à égalité sur les plateaux difficiles et profonds comme le vrai Eternity II, et à environ 44 % de sa vitesse sur les faciles. Chaque échelon parcourt l'arbre identique ; tout le gain vient du code, pas de l'algorithme.

Mesurez les 256 pièces officielles sans aucun solveur en vue et chaque porte structurelle est fermée : aucune pièce symétrique par rotation, 5 paires jumelles sur 32 640 appariements, un plafond de 307 sur 480 si rien ne tourne, des budgets de couleurs qui s'apparient à exactement 480 sans aucun jeu, et une palette 17+5 posée au point d'une-solution-attendue.

Eternity II utilise 22 couleurs, réparties entre 17 couleurs intérieures et 5 réservées au cadre, et ce chiffre d'environ 17 se situe près du point où ce type de casse-tête est le plus difficile à résoudre (la transition est une bande, pas un entier unique).

La manière habituelle de résoudre un casse-tête logique consiste à repérer un emplacement où une seule pièce convient, à la poser, puis à recommencer. Ce levier n'existe pas ici : chaque pièce intérieure admet entre 73 et 137 voisines possibles, et aucune n'est jamais contrainte à une seule option.

Un plateau quasi parfait ne répartit pas uniformément ses rares erreurs. Il les concentre dans une seule bande de cinq rangées et laisse tout le reste impeccable. Quelle bande ? Cela dépend de la direction dans laquelle la recherche a rempli le plateau, et l'on voit le reflet sur les vrais plateaux record.

Sur un casse-tête 16×16 construit à l'image d'Eternity II, dix-huit indices dispersés sur le plateau le résolvent en quelques minutes, là où les entasser en rangées contiguës en réclame une centaine rien que pour ramener la recherche à des dizaines de milliards de placements. C'est la position, non le nombre, qui fait levier, et elle pointe droit vers la fin de partie.

Cinq des 22 couleurs d'Eternity II n'apparaissent que le long de l'anneau de bordure, chacune sur exactement 24 arêtes, jamais une seule fois à l'intérieur. Une séparation structurelle qui façonne la manière dont chaque solveur traite le cadre.