Mesures

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.

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).

The results, worked through: on these boards the five clue-shaped hints never help a backtracker, they range from a mild cost to a catastrophe, and the fill order decides how much damage they do; the scores are bimodal, not a smooth gradient; and the hint-count question is confounded by a free pinned-seam floor.

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.

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 ?

Give a backtracker five correct pieces for free, in the puzzle's own clue geometry. It turns out not to help, and depending on the fill order it can hurt badly, because a pinned piece is a hard constraint a fixed fill order must satisfy on arrival. A family of fill paths, run on the same hinted boards, single core, measured against no hints at all.

Eternity II utilise 22 couleurs, réparties entre 17 couleurs intérieures et 5 réservées au cadre - et ce chiffre de 17 correspond exactement au point où ce type de casse-tête est le plus difficile à résoudre.

Une grille quasi parfaite ne répartit pas uniformément ses rares erreurs. Elle 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 la grille, et l'on voit le reflet sur les vraies grilles record.

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.

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ù le même casse-tête réclame quatre-vingts indices ou plus, entassés dans des rangées contiguës, pour devenir aussi facile. 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.