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.
Tout solveur d'Eternity II détenteur d'un record (Blackwood, Verhaard, McGavin)
est un backtracker en profondeur d'abord. Ce qui les distingue d'un backtracker
de premier devoir de la semaine ne tient pas à leur nature mais à une poignée de
décisions : l'ordre dans lequel ils remplissent les cases, l'anticipation qu'ils
appliquent, et le fait de laisser ou non une arête rompre. Cette étude démonte
ces décisions. Elle construit de zéro une famille de backtrackers en profondeur
d'abord, chacun séparé de son voisin par un seul changement, et les exécute tous
sur les mêmes dix variantes à coins fixés du puzzle officiel, sur un seul cœur,
soixante secondes par exécution. Le score maximal est de 480 arêtes appariées.
Le but n'est pas de gagner. La variante la plus forte présentée ici tourne en
moyenne autour de 430 tout juste, bien en deçà des 464 de la communauté sur ces
cinq indices, car soixante secondes sur un cœur ne représentent qu'une fraction
infime du calcul qu'ont demandé les records. Le but est d'isoler ce que vaut
chaque idée en ne changeant qu'une chose à la fois et en mesurant le résultat
avec le même scoreur canonique pour chaque plateau.
Les dix puzzles de départ
Chaque moteur tourne sur ces dix instances : le puzzle officiel de 256 pièces avec huit cases fixées (les cinq indices officiels et trois coins), disposées différemment à chaque fois. Seules les cases fixées sont montrées ; le reste est ce que la recherche doit remplir.
Quatre familles, disposées de sorte que des voisins diffèrent d'une seule
décision. Baseline est le backtracker le plus brut possible, accompagné d'un
jumeau spécialisé à la main qui chiffre le coût de l'ingénierie bas niveau.
Path order fixe tout sauf la séquence dans laquelle les cases sont remplies.
Heuristic fixe l'ordre et ajoute un propagateur à la fois. Break est
l'axe d'élite : le mécanisme de rupture d'arête à seuil de profondeur sur lequel
reposent les records. Les moteurs record de la communauté, le C de McGavin et le
C# de Blackwood, sont eux-mêmes des backtrackers à rupture, ils prennent donc
place dans la famille break, et non dans une catégorie à part. Savoir de qui est
le code d'un moteur reste affaire d'étiquetage, non de couleur. Les deux
apparaissent dans le classement à leur score à coins fixés, marqués d'un badge là
où ils s'effondrent, puis de nouveau sur une grille sans fixation plus bas, où
ils tournent tels qu'ils ont été conçus.
Le classement — score moyen par variante
Score moyen (arêtes appariées) sur dix variantes à coins fixés du puzzle officiel, un cœur, 60 s par run. La couleur marque la famille, nommée sur chaque barre : la couleur n'est jamais le seul signal. Le C de McGavin et le C# de Blackwood y figurent aussi, au score que leur parcours figé atteint avant qu'un coin fixé ne le bloque, étiquetés là où ils calent ; la section à deux grilles plus bas les montre tourner correctement une fois les coins ôtés.
Tracé…
référenceordre de parcoursheuristiquecassures
Jusqu'où chaque recherche est allée, et à quelle vitesse
La profondeur maximale atteinte par chaque variante, sur 256. Les backtrackers stricts plafonnent autour de 200 (le plus rapide, NAIVE-CODEGEN, atteint 216) ; la famille des cassures va nettement plus loin, 243 à 245, parce qu'elle peut franchir une arête localement inappariable au lieu de rebrousser chemin. Le tableau ci-dessous ajoute le débit médian, en nœuds de recherche par seconde, jamais comparé entre familles car un nœud avec propagation n'est pas un nœud naïf.
Tracé…
référenceordre de parcoursheuristiquecassures
variante
famille
profondeur max atteinte (sur 256)
débit médian
BREAK-1
cassures
245
4.6M
BREAK-2
cassures
245
5.2M
VERHAARD-SLIP
cassures
243
2.3M
NAIVE-CLEAN
référence
208
32.4M
ROWMAJOR
ordre de parcours
208
31.5M
NAIVE-CODEGEN
référence
216
44.9M
VERHAARD-COMB
ordre de parcours
197
23.3M
BLACKWOOD-COMB-BREAK
cassures
197
17.9M
BORDER-MRV
heuristique
194
6K
MRV-RARE
heuristique
194
7K
MRV-FC
heuristique
193
7K
MRV-AC3
heuristique
192
8K
MRV-GACOLOR
heuristique
192
8K
ROWMAJOR-BOTTOMUP
ordre de parcours
201
273K
SPIRAL-IN
ordre de parcours
79
13.3M
BLACKWOOD-CS
cassures
47
—
BORDER-FIRST
ordre de parcours
77
365K
SPIRAL-OUT
ordre de parcours
31
20.1M
MCGAVIN-C
cassures
21
—
Ce qui s'empile sur quoi
Chaque variante est un backtracking en profondeur déclaré comme un seul changement par rapport à son parent. Ce tableau est généré depuis le registre du moteur : il correspond toujours au code exécuté.
variante
famille
le changement qu'elle ajoute à son parent
cassures
moy.
prof.
NAIVE-CLEAN
référence
the rawest depth-first backtracker: row-major, no heuristics, no breaks
strict
376.8
208
NAIVE-CODEGEN
référence
same algorithm, a 16×16-specialised unrolled hot loop
strict
372.1
216
ROWMAJOR
ordre de parcours
the row-major control (same as NAIVE-CLEAN, named for the path study)
strict
376.6
208
ROWMAJOR-BOTTOMUP
ordre de parcours
fill bottom-to-top instead of top-to-bottom (Blackwood's scan direction)
strict
225.9
201
SPIRAL-IN
ordre de parcours
fill the outer ring inward instead of row-major (the cloister spiral)
strict
80.2
79
SPIRAL-OUT
ordre de parcours
spiral from the centre outward instead of inward
strict
24.5
31
BORDER-FIRST
ordre de parcours
fill the whole border ring first, then the interior
strict
66.6
77
VERHAARD-COMB
ordre de parcours
a horizontal band then vertical teeth (Verhaard's COMB order)
strict
357
197
BORDER-MRV
heuristique
choose the most-constrained empty cell dynamically (MRV) instead of a fixed order
strict
324.1
194
MRV-RARE
heuristique
try pieces carrying globally-rare colours first (Selby/Riordan rarity)
strict
323.7
194
MRV-FC
heuristique
add forward-checking: reject a placement that empties any neighbour's domain
strict
322.2
193
MRV-AC3
heuristique
extend the look-ahead to arc-consistency (AC-3) over the frontier
strict
320.6
192
MRV-GACOLOR
heuristique
add Régin per-colour all-different reasoning on the remaining supply
strict
320.6
192
BREAK-1
cassures
allow ≤1 broken edge per cell on a depth schedule (Blackwood's ladder)
break (≤1/cell)
431.3
245
BREAK-2
cassures
allow up to 2 broken edges at one cell (double-breaks the community 460s use)
break (≤2/cell)
428.5
245
VERHAARD-SLIP
cassures
Verhaard's interior edge-slip schedule instead of Blackwood's ladder
break (≤1/cell)
399.3
243
BLACKWOOD-COMB-BREAK
cassures
run the Blackwood break ladder on Verhaard's COMB fill order
break (≤1/cell)
356.4
197
MCGAVIN-C
cassures
the community's fastest DFS, run here; it collapses on our corner pins
break (≤1/cell)
13
21
BLACKWOOD-CS
cassures
Blackwood's C# record engine, run here; it stalls on our pins
break (≤1/cell)
75
47
Les moteurs record de la communauté, exécutés ici
Le C de McGavin et le C# de Blackwood se compilent et tournent sur la même machine. Aucun ne peut prendre la grille à coins fixés ci-dessus : chacun est bâti autour d'une configuration d'indices précise, si bien qu'un coin fixé que son parcours n'atteint jamais tôt le bloque aussitôt. Les deux panneaux ci-dessous en montrent les deux faces. D'abord, les coins fixés de l'étude les effondrent. Ensuite, sur une grille équitable réduite au seul indice central obligatoire, ils tournent comme prévu.
Même budget, même cœur : 60 s à froid
Les mêmes moteurs sur les pièces officielles avec le seul indice central obligatoire, si bien que rien ne se bloque sur un coin arbitraire. Chaque score est recalculé canoniquement depuis le plateau du moteur, un cœur, 60 secondes, à froid. C'est une comparaison à budget contrôlé, conditions identiques pour les quatre, non un concours de force maximale : elle montre jusqu'où chacun va en une minute sur un cœur, pas le plafond de chaque moteur. Cet unique indice fixé pèse quand même : Blackwood n'obtient ici que 214, bien en deçà des 454 de sa page solveur, où sa recherche place chaque pièce librement au lieu d'ancrer l'indice central d'emblée (un plateau légal malgré tout, puisque seul l'indice central est contraignant, mais une recherche plus facile). Le repère pâle sur les deux moteurs étrangers est leur meilleur score documenté, qui exige de longs runs multi-cœurs qu'un budget d'une minute ne peut atteindre. Ce que la grille montre : les quatre tournent correctement une fois ôtés les coins fixés qui brisent un parcours figé, ce que la grille fixée refusait aux deux moteurs étrangers.
Tracé…
La ligne pointillée sur chaque moteur étranger marque son meilleur score documenté (Blackwood ~470, McGavin 469) : le puzzle officiel n'a jamais été résolu, aucun moteur n'atteint donc un véritable 480. Ces records exigent de longs runs multi-cœurs qu'un budget d'une minute sur un cœur ne peut atteindre ; le propre run plus long de Blackwood sur cette même machine atteignait déjà 454. Le débit est étiqueté par moteur (McGavin compte des tuiles, les autres des nœuds de recherche) et n'est jamais comparé entre moteurs, car les unités ne mesurent pas le même travail. McGavin est compilé avec les propres options ARM de son auteur (réglage natif et optimisation à l'édition de liens).
moteur
moy.
profondeur atteinte
débit
McGavin (C)
392
211
85M tiles/s
break-2 (ours)
344
192
33M search-nodes/s
Verhaard (our reimpl)
286
172
8k search-nodes/s
Blackwood (C#)
214
119
9M search-nodes/s
Fixé : l'effondrement, en score
Les deux mêmes moteurs étrangers sur la configuration fixée de l'étude. La barre est le score canonique que leur plateau atteint avant que le parcours figé ne les bloque ; la barre pâle derrière est ce que le même moteur atteint sans coins fixés. L'écart est l'effondrement.
MCGAVIN-C(C)coins fixés 13 · indice central seul 392
depth 21
BLACKWOOD-CS(C#)coins fixés 75 · indice central seul 214
depth 47
L'effondrement dû aux coins fixés. Adding the study's three corner pins collapses its fixed scan path to depth 21 (canonical score 13), confirmed on 2 pinned variants: the scan never reaches a corner early, so a pinned corner dead-ends it at once.
L'effondrement dû aux coins fixés. It hardcodes its piece set and scan, so it cannot express the study's arbitrary corner pins; the matching constrained test is the five official clues, where its heuristic phase thrashes to depth 47 (canonical score 75) in 60 s.
L'ordre de parcours est le plus grand levier gratuit, et le mauvais ordre est
catastrophique. Un simple parcours ligne par ligne tourne en moyenne à 377 ;
un remplissage strict bord d'abord ou en spirale, sans heuristique pour le
sauver, plafonne autour de 67. Même moteur, même budget, un écart de plus de
300 points dû au seul ordre de remplissage.
L'heuristique de la case la plus contrainte (MRV) est ce qui rend le bord
d'abord viable. Elle fait passer un bord d'abord en panne de la soixantaine à
une moyenne de 324, au prix de trois ordres de grandeur sur le débit de nœuds.
Le débit de nœuds et le score sont deux axes distincts, une distinction sur
laquelle l'étude revient de bout en bout.
Davantage de propagation n'a pas acheté davantage de score à ce budget. Le
forward-checking, l'arc-cohérence et le raisonnement par couleur atterrissent à
un point près l'un de l'autre (322, 321, 321), un écart bien à l'intérieur de la
dispersion d'une exécution à l'autre : une anticipation plus lourde n'a donc ni
aidé ni clairement nui. Elle dépense les soixante secondes à prouver de petites
régions plutôt qu'à descendre plus profond.
Les ruptures descendent plus profond que n'importe quelle recherche stricte.
Les backtrackers stricts plafonnent dans les 200 tout juste (le plus rapide,
NAIVE-CODEGEN, à 216) ; un budget de rupture à seuil de profondeur dépasse 245 et
tourne en moyenne autour de 430, car il peut forcer le passage au-delà d'une
arête localement inappariable au lieu de remonter pour en sortir. Le facteur
décisif est le calendrier des ruptures : déverrouiller les ruptures trop tôt
(l'échelle de Verhaard, moyenne 399) score bien en deçà de l'échelle plus
tardive de Blackwood (moyenne 431). Relever le plafond par case de un à deux n'a
pas aidé à ce budget, un résultat nul rapporté comme mesuré.
Chacun de ces points a sa propre page : la construction du moteur et la
signification de chaque statistique relevée figurent sur la
page de méthode, et les
comparaisons de parcours, d'heuristique et de rupture sont détaillées sur la
page des résultats.
Chaque plateau est re-scoré par un unique scoreur canonique, et le score
auto-déclaré d'aucun moteur n'est pris pour argent comptant. Le débit est rapporté
en nœuds de recherche par seconde et n'est jamais comparé d'une famille à
l'autre, car un nœud qui exécute une arc-cohérence complète n'est pas la même
unité de travail qu'un placement naïf. La profondeur est le placement le plus
profond qu'a atteint une variante, sur 256.
Le nombre de ruptures mérite une définition précise, car il est facile de
l'énoncer de façon vague. Le score d'un plateau est le nombre de ses arêtes
intérieures appariées, et l'écart 480 − score est le déficit total d'arêtes
non appariées du plateau. Sur un plateau achevé, chaque arête non appariée est
une véritable rupture, si bien que là le score vaut exactement 480 − #ruptures.
Soixante secondes suffisent rarement à remplir le plateau, cependant, de sorte que
la plupart des plateaux de variantes à rupture présentés ici sont partiels, et
leur déficit est dominé par des arêtes simplement encore vides plutôt que rompues.
Cette étude rapporte donc le vrai nombre de ruptures, c'est-à-dire les
non-appariements intérieurs que la recherche a effectivement engagés sous son
budget, suivis par la recherche elle-même plutôt qu'inférés du score. Ce nombre
reste petit même quand le déficit est grand. Chaque plateau porte une .url bucas
qui s'ouvre dans le visualiseur, de sorte que le score comme les arêtes
rompues peuvent se vérifier directement.
Tout l'appareillage (l'espace de travail du moteur, les dix variantes, les
résultats par exécution versionnés et les scripts de grille) réside sous le
répertoire d'appui
de l'étude, et just experiments dfs-study reconstruit le moteur et relance toute
la grille.