L'ordre dans lequel un algorithme de retour arrière visite les 256 cases est son unique liberté : il ne coûte rien à l'exécution et fait varier la taille de l'arbre de recherche de plusieurs ordres de grandeur. Vingt ans de science communautaire, des guerres fixe-contre-dynamique aux courses de stratégies, jusqu'au carré magique 10×16 et à la recherche en peigne de Verhaard, répondent tous à la même question : quel chemin à travers le plateau est le moins coûteux ?
Un algorithme de retour arrière n'a presque aucune liberté. Les pièces sont
données, la règle d'appariement est donnée, le plateau est donné. La seule
chose qui vous revient entièrement, c'est l'ordre de remplissage : la
séquence dans laquelle les 256 cases sont remplies. Cela ressemble à un détail
(la recherche est exhaustive quoi qu'il arrive), et c'est en réalité la
décision à plus fort effet de levier de tout le solveur. Brendan Owen l'a dit
sans détour en 2007 : « L'une des plus grosses économies de nombre de nœuds
que vous puissiez faire consiste à choisir un bon ordre de recherche »
(msg 2714). Le même puzzle,
parcouru dans un ordre différent, peut coûter dix ordres de grandeur de nœuds
en plus. Et le choix est gratuit, arrêté avant même que la première pièce ne
soit posée.
Voilà pourquoi la liste de diffusion en a débattu pendant vingt ans. Le
premier grand débat, à l'été 2007, opposait le fixe au dynamique : les
vétérans d'Eternity I plaidaient pour le choix dynamique, à chaque étape, de la
case la plus contrainte, l'heuristique CSP classique
(msg 2392). Les empiristes ont
répondu par des comptages de nœuds : les meilleurs résultats venaient de
chemins fixes, précalculés, et le verdict d'Owen fut qu'« un balayage par
lignes après la pose de la pièce indice semble le meilleur »
(msg 2425). Un an plus tard,
quand on lui a demandé pourquoi personne ne s'embêtait avec un placement
entièrement dynamique, istarinz a résumé le volet ingénierie de la réponse en
un mot, vitesse : un chemin fixe garde la boucle interne sans branchements et
pilotée par tables
(msg 5860). Le volet théorique a
demandé plus de temps, et fait l'objet de cette page.
Une idée sous-jacente à tout le reste : un placement de pièce n'est jamais
testé que contre les voisins déjà présents sur le plateau. Une grille 16×16
possède exactement 480 jonctions internes, et tout ordre de remplissage complet
(balayage par lignes, spirale, n'importe quoi) finit par vérifier les 480. L'ordre
ne change que l'ordonnancement : quelles jonctions sont payées tôt, tant que
l'arbre est encore étroit, et lesquelles sont reportées là où il est large. Une
case qui arrive avec deux voisins déjà posés n'admet que peu de pièces
candidates ; une case qui arrive sans aucun voisin les admet presque toutes et
n'élague rien. Les bons ordres sont ceux qui nourrissent la recherche d'un
régime régulier de cases contraintes, ce que fait précisément un balayage par
lignes : après la première rangée, presque chaque nouvelle case touche une pièce
à sa gauche et une pièce en dessous.
Owen en a fait une méthode. Pour un ordre fixe, les nœuds à la profondeur D
valent (en espérance) le nombre de façons de paver la forme que l'ordre a
construite à la profondeur D. Tout ordre candidat peut donc être noté, forme
par forme, sans l'exécuter. Sa conclusion, tirée d'une analyse exhaustive : les
formes qui dominent le total sont celles de tailles 121 à 185, et les meilleures
formes dans cette fenêtre critique « forment un simple ordre de balayage par
lignes » (msg 2714). Toute la
machinerie, probabilités de jonction comprises, est devenue la
théorie complexe ; cette page montre à quoi
ressemblent ses réponses en pratique.
Le carnet de laboratoire du projet met des chiffres sur le régime lui-même.
Notons k le nombre de côtés voisins déjà posés qu'une case présente au
moment où la recherche l'atteint. Une loi de champ moyen dit que la case
devrait admettre environ 4Rpk placements candidats, où R est le nombre
de pièces encore en main et p≈0,048 la probabilité moyenne,
pour E2, qu'un côté s'apparie à une couleur. Au début du remplissage
intérieur, cela prédit environ 38 candidats pour une case k=1, 1,8 pour
k=2, 0,09 pour k=3 et 0,004 pour k=4. Une énumération exacte contre
le vrai jeu de 256 pièces (40 essais ensemencés par configuration) tombe à
20 à 40 % de ces prédictions et confirme les trois régimes qu'elles
dessinent : les cases k=1 sont pour l'essentiel toujours remplissables ;
les cases k=2 franchissent les 50 % de cases mortes quelque part entre 50
et 62 % de remplissage du plateau ; et les cases à trois voisins posés ou
plus sont mortes dans 87 à 100 % des essais à tout niveau de remplissage, y
compris au tout premier placement intérieur. (La loi est une idéalisation
de champ moyen validée pour les statistiques de couleurs d'Eternity II, une
seule instance ; ce n'est pas une affirmation sur l'appariement d'arêtes en
général.)
Lue comme règle de conception : un bon ordre est celui dont la frontière
présente à chaque nouvelle case exactement deux voisins posés, assez pour
élaguer, assez peu pour survivre. Le balayage par lignes le fait par
construction, un k=2 constant après la première rangée ; tout ordre dont
la frontière développe des poches concaves à trois côtés paie des cases
quasi certainement mortes, quel que soit le taux de remplissage du plateau.
Les mêmes régimes mesurent aussi ce que le retour arrière achète. Sans
aucun retour arrière, un remplissage glouton aléatoire cale dans les 5 à
12 % premiers du plateau quel que soit le parcours : sur 8 graines par
ordre, le calage médian est survenu au pas 15 pour le rang-majeur, 13 pour
un parcours diagonal et 15 pour une spirale (le parcours diagonal s'étendait
de 4 à 32), et aucune des 24 exécutions n'est allée plus loin. Tout parcours fabrique un coin
concave fatal en une poignée de placements ; ce chiffre illustre la
géométrie, ce n'est pas un banc d'essai de solveur.
Le laboratoire ci-dessous rend l'ordonnancement visible. Il anime la séquence de
visite de quatre ordres prédéfinis sur une grille 16×16 et trace, en direct, le
comptage de contraintes (combien de voisins déjà posés possède chaque nouvelle
case) ainsi que le cumul des jonctions collectées. (Il montre la géométrie ;
pour faire courir de vraies résolutions le long de chemins que vous tracez
vous-même, le pendant pratique est le
terrain de jeu des chemins de recherche.)
▶Interactif : ordre de remplissage contre ramificationExplorer →
Les courses de stratégies. À la fin de 2007, la question était devenue
quantitative : puzzles de référence partagés, comptages de nœuds en recherche
complète et tableau de scores public. Le sommet du genre fut l'algorithme
entièrement automatique de recherche de stratégie de doc_s_smith, qui a conçu
un ordre de recherche épuisant le benchmark de taille 14 hints15_2 en
89 794 nœuds, battant les 141 628 réglés à la main de Txibilis : la machine
sur l'humain (msg 2896).
Txibilis a répliqué en deux jours avec 85 729
(msg 2928) ; doc_s_smith
s'interrogeait déjà sur les raisons de la force des humains dans cette
discipline (msg 2883). La leçon
qui a survécu à la course : la qualité d'un ordre est mesurable, et les écarts
ne sont jamais petits.
Dynamique contre fixe, mesuré. L'argument fixe-contre-dynamique de 2007 a
fait l'objet d'un petit test contrôlé en septembre 2008. Markus Zajc a exécuté
trois ordres sur le 8×8 sans indice, chacun sur dix ordres de tuiles
aléatoires pour annuler les effets de l'ordre d'entrée, tous sous un résolveur
de contraintes : balayage simple, un ordre par valeur restante minimale qui
prend toujours la case ayant le moins de candidats, et un ordre par réduction
maximale qui prend la case dont le placement élague le plus. La valeur restante
minimale l'a emporté ; le balayage est arrivé deuxième mais oscillait avec
l'ordre d'entrée (sa meilleure exécution restait ~2× le vainqueur) ; la
réduction maximale a fini dernière, car ensemencer tôt l'intérieur ouvert
achète une grosse première coupe mais entraîne ensuite un facteur de
ramification punitif à chaque retour arrière
(msg 5918 ; les vidages de
domaines par ordre sont dans son dossier de la zone de fichiers). C'est un
petit plateau, mais c'est le duel le plus net de l'heuristique CSP classique
contre un balayage fixe, et il atterrit là où les comptages de nœuds ultérieurs
de la communauté aboutissent : la valeur réside dans le fait de nourrir la
recherche de cases contraintes, qu'une règle dynamique ou un bon chemin fixe
vous y mène.
La victoire du balayage est un fait de conception d'E2. En avril 2008, Owen
a construit des puzzles 16×16 où l'équilibre de couleurs bordure/intérieur était
délibérément déséquilibré (2 couleurs de bordure et 19 d'intérieur, puis 14 et
15) et a noté les ordres balayage, centre d'abord et bordure d'abord sur chacun.
Les conceptions déséquilibrées sont attaquables : le centre d'abord bat le
balayage d'environ 150× sur la conception 2/19, la bordure d'abord l'emporte sur
la 14/15. Sur la véritable répartition 5/17 d'E2, chaque écart perd : le centre
d'abord coûte 1,22×1060 nœuds contre 1,07×1050 pour le
balayage, parce que la conception équilibre la pavabilité de la bordure et de
l'intérieur, donnant au puzzle « aucune zone faible par laquelle commencer à
paver » (msg 5263,
5243). Le balayage par lignes
n'est pas une loi de la nature ; c'est la bonne réponse à une conception
adverse bien précise.
Le carré magique 10×16. Pourquoi le balayage par lignes et pas, disons, un
ordre par blocs 4×4 ? La règle empirique de la forme de frontière de Louis
Verhaard : la plupart des ordres atteignent leur maximum de comptage de nœuds
autour de la profondeur 160, donc ce qui compte, c'est la forme que votre ordre
a construite à cet endroit, et la meilleure forme connue en profondeur 160 pour
E2 est un rectangle 10×16 (avec deux coins remplis). Les ordres dont la frontière
passe par « le carré magique 10×16 » sont quasi optimaux ; un balayage par blocs
2×2 le fait, un 4×4 non, ce qui est exactement l'écart que Max venait de mesurer
(msg 5868,
5879). C'est la pièce que la seule
courbe de comptage de contraintes ne peut pas voir : deux ordres peuvent payer
les jonctions selon le même ordonnancement tout en différant par le périmètre de
la région qu'ils construisent.
Pourquoi « résoudre la bordure d'abord » est un piège. L'instinct humain le
plus naturel, construire le cadre facile puis remplir le milieu, est
quantitativement l'un des pires ordres, et en 2025 Owen et Peter McGavin ont
détaillé pourquoi, précisément sur ce pic en profondeur 160. La bordure est
réellement facile : après la pièce de départ, il y a environ
5,17×1037 façons de la compléter, dont seulement 14 702 peuvent être
remplies par les 196 pièces d'intérieur, si bien qu'environ 3,5×1033
cadres doivent être essayés avant que l'un puisse ne serait-ce que finir
(msg 11572). Cela seul est déjà
sans espoir, mais ce n'est pas le vrai problème. Le problème, c'est qu'avec le
cadre fixé en premier, le comptage de nœuds continue de grimper après la
bordure jusqu'à un pic d'environ 1057 vers 160 pièces, contre environ
1043 pour le balayage par rangées. Un ordre bordure d'abord s'engage tôt
sur la bordure puis fonce droit dans un pic de quatorze ordres de grandeur plus
haut que celui du balayage par rangées, car seul environ 1 cadre sur 1031
mène quelque part et chacun est coûteux à écarter
(msg 11573). Le balayage par
lignes ne gagne pas en construisant une plus belle frontière, mais en ne payant
jamais pour une bordure dont il ne peut pas encore savoir qu'elle est condamnée.
Mais quel balayage ? Même au sein des balayages par lignes, il y a huit
orientations : quatre coins de départ, rangées ou colonnes
(msg 6018). Max a mené sur
plusieurs jours des estimations par échantillonnage de la taille de l'arbre
complet par orientation : de droite à gauche se maintenait stable juste sous
2,7×1040 nœuds, tandis que de bas en haut, de gauche à droite
(l'orientation qui connecte le plus tôt la pièce de départ obligatoire, et
celle qu'utilisait déjà Verhaard) tournait autour de 2,3×1040
(msg 6015,
6023). Un choix de folklore
devenu un ~15 % mesuré : minuscule à côté des ordres de grandeur ci-dessus,
mais gratuit.
Des écarts qui ont payé. L'orthodoxie de l'ordre de balayage a été
constamment mise à l'épreuve, et l'a le plus souvent emporté, mais pas
toujours. Owen lui-même a résolu son défi 14×14 avec un ordre en carrés
décroissants après le blocage du balayage ; sur les plateaux irréguliers,
l'argument d'équilibre ne tient plus
(msg 3124). Des hybrides ont été
proposés, débutant en carrés croissants (moins coûteux au départ) puis basculant
vers le balayage avant le pic de mi-profondeur
(msg 6142). Et Max a trouvé une
véritable amélioration intra-balayage : au début d'une rangée, les candidats de
bordure qui ne diffèrent que par leur seconde couleur de bordure non appariée
sont équivalents : réfutez-en un et vous les avez tous réfutés. Verhaard, ravi
(« Enfin quelque chose qui bat le simple balayage par rangées ! »), l'a
implémentée et a confirmé ~10 % de l'espace de recherche éliminé à un coût quasi
nul (msg 5980,
5983,
6062).
Des écarts qui n'ont pas payé (mesures du carnet)#
La communauté a surtout publié les écarts qui avaient un argument pour eux.
Le carnet de laboratoire du projet garde l'autre espèce, des ordres
séduisants qui ont perdu, et les régimes k ci-dessus savent nommer le
mécanisme de chacun.
Les spirales paient une taxe de fermeture. Sur un banc d'essai
d'intérieur 14×14 bordé (8 graines par bras), une spirale de l'extérieur
vers l'intérieur s'est coincée à la profondeur 26 sur les 8 graines, au
coin de fermeture de son premier anneau. Une spirale à pourtour libre a
calé aux profondeurs 133 à 141 avec 0 complétion, contre 344 à 347 pour un
balayage par lignes ; avec toutes les assistances du moteur activées, elle
butait encore à 131 à 140 avec 0 complétion en 300 s, contre 446 à 448 pour
le balayage. La loi en k dit pourquoi : tout le premier anneau d'une
spirale à pourtour libre tourne à un voisin posé ou moins par case, une
ramification presque impossible à élaguer, tandis qu'une spirale bordée
paie une taxe de fermeture : chaque anneau porte 4 ou 5 cases à trois
voisins posés à ses coins et à son raccord, et les cases à trois côtés sont
presque irremplissables. Le balayage par lignes est l'ordre de Boucle d'or,
deux voisins constants et une seule zone de dégâts active.
Partir des indices perd. « Commencer là où est l'information » sonne
juste et pointe à l'envers. Dans un duel de 60 s sur le vrai puzzle (une
configuration, une exécution, à lire donc comme notre test et non comme une
réfutation), un ordre centré sur les indices, s'étalant depuis les cinq
cases d'indice, a atteint la profondeur 42 (62 arêtes appariées) tandis
qu'un ordre dynamique par case la plus contrainte, qui en pratique dévore
d'abord la bordure tout en restant libre de l'abandonner (au contraire du
cadre engagé du piège plus haut), atteignait la profondeur 164 (282 arêtes
appariées). Les cases autour des indices centraux portent les domaines de
pièces les plus larges du plateau ; l'ordre centré sur les indices donne
la priorité exactement aux cases les moins contraintes.
Un X à travers les indices perd aussi. Pré-engager deux diagonales
larges de 3 cases passant par les cinq indices, puis remplir vers
l'extérieur, a fini 51 arêtes appariées sous sa référence (396 contre 447 à
budgets identiques, une seule graine).
Trois expériences, un motif, énoncé comme un motif et non comme un
théorème : chaque ordre statique que nous avons essayé qui passe tôt par
des cases intérieures à large domaine a perdu. Un ordre statique n'esquive
pas la région difficile ; il choisit quelle région devient la région
difficile. Il choisit aussi où atterrissent les échecs :
là où s'entassent les mésappariements
sur un plateau presque parfait suit l'ordre de parcours, centre-bas pour
les balayages de haut en bas, haut pour ceux de bas en haut (visible sur
les plateaux de classe 469 de la communauté elle-même), coins pour les
spirales partant du centre. Un ordre de remplissage ne décide pas seulement
combien vous échouez, mais où.
La littérature académique aboutit au même endroit. Ansotegui, Bejar,
Fernandez et Mateu, qui ont fait des puzzles d'appariement d'arêtes des
benchmarks SAT/CSP, travaillaient avec des ordres statiques de la famille
damier-plus-spirale-centrale ; rejoué dans notre moteur sans le filtrage
all-different complet que leurs modèles supposent, cet ordre a fait
exploser les comptages de nœuds d'environ 600×. Et la base de retour
arrière de l'étude hyper-heuristique de 2012 de Wauters, Vancroonenburg et
Vanden Berghe a fait courir le balayage par lignes contre spirale, spirale
inverse et ordres en miroir, et a trouvé le balayage significativement
meilleur : une redécouverte indépendante de la thèse de la liste de
diffusion.
La recherche en peigne : la géométrie des scores élevés#
Tout ce qui précède optimise une recherche complète, dont le comptage de
nœuds culmine près de la profondeur 160. En octobre 2008, alors qu'il gardait
en privé les plateaux qui allaient remporter le prix d'examen de 10 000 dollars,
Verhaard a répondu à une autre question d'Owen : quel est le meilleur ordre
lorsqu'on poursuit un score partiel, et qu'on vit donc bien plus profond dans
le plateau (msg 6111) ? Sa réponse
nommait une géométrie : les meilleurs ordres qu'il avait trouvés ressemblent à
une recherche en peigne (la plupart des rangées parcourues horizontalement,
puis les rangées restantes parcourues verticalement), avec la longueur des dents
liée à la cible : « Plus le score que vous visez est bas, plus les dents du
peigne s'allongent »
(msg 6112). Max avait convergé de
façon indépendante vers presque le même ordre (douze rangées de balayage, puis
balayage par colonnes) et a rapporté des scores « d'environ 1 arête plus bas »
que ce qu'accomplissait le solveur de Louis
(msg 6126).
L'intuition : une recherche complète doit franchir le goulet d'étranglement de
la profondeur 160 le plus économiquement possible ; une recherche de score élevé
veut au contraire de nombreuses façons peu coûteuses de terminer. Chaque dent
verticale est une colonne courte, presque indépendante, dont les échecs sont
locaux, si bien que des frontières profondes et à score élevé sont atteintes
encore et encore. Le peigne était l'une des deux moitiés de la machine derrière
le 467 ; l'autre moitié, le
glissement d'arêtes à seuil de profondeur,
décidait de ce que les dents avaient le droit de placer. Et les deux étaient
réglées conjointement : Verhaard optimisait l'ordre de remplissage et le
tableau de glissements ensemble à l'aide d'une chaîne de Markov sur (profondeur,
glissements utilisés), construite à partir de probabilités d'ajustement par
profondeur mesurées
(msg 6423). Conception d'ordre par
le calcul, non par le folklore. Le moteur complet est sur
la page eii de Verhaard.
Le peigne a dormi dix-huit ans dans l'histoire des records avant que nous
ne l'essayions chez nous ; c'est la relecture des messages ci-dessus qui a
fait remonter le levier. Greffer la géométrie du peigne sur un producteur à
recherche en faisceau écrit de zéro (rangées hautes en rang-majeur, rangées
basses remplies en courtes dents verticales) a fait passer son meilleur
partiel brut de 455 à 457 arêtes appariées sur 480, sur des plateaux aux
cinq indices stricts, par le seul ordre de visite ; rien d'autre n'a
changé. Derrière cette phrase il y a un balayage, pas un coup de chance :
cinq ordres (rang-majeur plus des coupes de peigne après les rangées 8, 10,
12 et 14) croisés avec trois largeurs de faisceau (2048, 8192 et 16384),
24 graines chacun à calcul égal, sur 8 cœurs. Le nouveau plafond
n'apparaît qu'au faisceau le plus large, où la coupe 14 a atteint 457 sur
une graine et la coupe 12 456 sur deux, chaque plateau vérifié de trois
façons indépendantes (un re-scoreur indépendant, un vérificateur externe et
le compte propre du producteur ; placement strict des cinq indices, 256
pièces toutes distinctes). Aux largeurs plus petites, le peigne égale le
meilleur du rang-majeur.
Ce que le peigne déplace de façon fiable, c'est le plancher et le milieu de
la distribution. À faisceau 2048, les coupes 10 et 12 relèvent le minimum
sur 24 graines de 446 à 449 et la médiane de 449 à 451 ; au faisceau le
plus large, la médiane de la coupe 12 gagne une arête. La coupe 12 atteint
aussi 455, l'ancien plafond du rang-majeur, à la moitié de la largeur de
faisceau, et à faisceau 8192 un balayage de 24 graines produit 15 plateaux
à 453 ou mieux contre 9 pour le rang-majeur : +67 % de bons plateaux de
départ par unité de calcul. La règle de Verhaard sur la longueur des dents
tient aussi par le haut. Les dents longues (coupe 8, dents de 8 cases)
régressent sous le rang-majeur à toutes les largeurs ; les dents courtes
gagnent. La coupe 12, l'exact « douze rangées, puis colonnes » de Max, est
la meilleure pour toute la distribution, tandis que la coupe 14 et ses
dents de 2 cases trouve le meilleur plateau isolé sur une médiane plus
basse : une géométrie de finition plus fine, à plus forte variance. Le
mécanisme est l'intuition énoncée plus haut, désormais mesurée : chaque
dent courte est une colonne presque indépendante dont les échecs restent
confinés, si bien que des frontières profondes à score élevé sont
atteintes encore et encore.
L'ordre décide aussi où finit le mou récupérable. Une re-résolution exacte
des trois dernières rangées hisse un plateau rang-majeur de 455 à 457 et ne
fait rien pour un plateau peigne à 457 : la région remplie en dernier et la
moins contrainte du peigne, ce sont ses dents verticales, pas ses rangées
basses, donc une réparation par bande de rangées vise le mauvais endroit.
Une re-résolution exacte alignée sur les dents, par bande de colonnes,
amène les plateaux peigne à 459 et pas plus loin, parce que les dents
sortent du faisceau déjà exactement optimales (un solveur exact a prouvé
optimale une région de dents de 32 cases en 21 s environ) ; le peigne
dépense pendant la construction le mou que la réparation aurait récupéré.
Les deux routes convergent à 459 : le peigne encaisse le score en avance,
le rang-majeur le laisse dans une queue récupérable, et ordre plus
réparation de fin de partie moissonnent le même mou. Pour l'échelle, 455,
457 et 459 sont des comptes d'arêtes appariées sur plateaux aux cinq
indices stricts, issus d'un producteur de carnet sur 8 cœurs ; les
plateaux communautaires sont plus haut, et
la page des records tient le classement.
Tout ce qui précède ordonne des cases. Le bouton jumeau est l'ordre des
pièces essayées dans une case : le duel de Zajc portait sur la prochaine
case à ouvrir, celui-ci porte sur le candidat à y glisser en premier. La
réponse du carnet est un nul propre. Au sein d'un remplissage rang-majeur
fixe, réordonner la liste de candidats de chaque case par rareté globale
des couleurs (couleurs les plus rares d'abord) n'a rien changé de mesurable
sur 8 graines par bras : à 60 s d'horloge égales, la médiane était de 389
arêtes appariées (indices épinglés, puzzle à cinq indices) dans chaque
bras, ordre de référence, rareté d'abord, et un contre-ordre délibéré
(couleurs les plus abondantes d'abord) conçu pour perdre. Le contrôle n'a
pas perdu ; sa meilleure exécution (419) a battu la meilleure de la
référence (415). Le débit de nœuds était plat d'un bras à l'autre, 8,2 à
9,6 millions de nœuds par seconde : le réordonnancement est gratuit, et
sans valeur, dans les deux sens. (Avant la comparaison, le bras de
référence a été vérifié identique nœud à nœud au moteur non modifié.)
Le mécanisme est un signal affamé. Quand un balayage rang-majeur atteint
une case, la liste de candidats est déjà filtrée à la poignée de pièces
s'appariant à deux couleurs fixées, et un élagage global de faisabilité
offre-demande exploite déjà la rareté des couleurs sur tout le stock
restant ; l'ordre par rareté re-dérive, plus grossièrement, une information
que la recherche utilise déjà, et savoir laquelle de trois pièces légales
passe en premier compte peu quand le seau sera de toute façon épuisé.
Cadrons-le comme mesuré : l'ordre des candidats a été inerte dans notre
moteur à un point de fonctionnement (une pile d'élagages, un budget de
60 s, des signaux de rareté globaux seulement), et non « l'ordre des
valeurs ne compte jamais nulle part ». Cela rime avec la seule victoire
intra-balayage plus haut : les ~10 % de Max venaient de la suppression de
candidats de bordure, pas de leur réordonnancement. Les gains vivent dans
l'élagage et dans l'ordre des cases.
Observez le balayage par lignes. Après la première rangée, presque chaque
placement rencontre exactement deux voisins posés : à gauche et en dessous. La
courbe de contraintes se stabilise à 2, et le cumul des jonctions grimpe
régulièrement : la recherche paie au fur et à mesure.
Passez à la spirale. Tout le premier anneau (60 placements) arrive avec au
plus un voisin posé : soixante choix quasiment sans contrainte empilés avant
que l'intérieur ne commence à les rembourser. La courbe cumulée fléchit
sous la référence du balayage par lignes exactement là où l'arbre peut le
moins se le permettre.
Essayez la diagonale. Surprise : les comptages ressemblent presque à ceux
du balayage par lignes. C'est la limite du point de vue par comptage de
voisins : la frontière de la diagonale est plus longue que celle d'un balayage
pendant une bonne partie du milieu de partie, un effet de forme que seule la
théorie complexe (ou la règle magique du
10×16) peut noter.
Sélectionnez le peigne à des dents de 4. Douze rangées de balayage, puis
des dents verticales, l'ordre de Max du
msg 6126. Remarquez la petite
falaise à chaque nouvelle dent : la première colonne paie une case faible, à 1
voisin, à sa base, le prix de la géométrie des scores élevés.
Allongez les dents. Une plus grande part du plateau passe en mode vertical
et les placements faibles se multiplient. C'est le compromis de Verhaard, dit
visuellement : plus le score que vous visez est bas (plus vous autoriserez de
glissements), plus les dents que vous pouvez vous permettre sont longues.
Puis faites-le courir pour de vrai. Le
terrain de jeu des chemins de recherche vous permet de
tracer n'importe lequel de ces chemins, ou le vôtre, sur un vrai puzzle et de
regarder des solveurs les parcourir en course, avec une estimation de pic de
plateau en direct à côté.
À l'exécution, rien : un ordre de remplissage fixe est un tableau précalculé de
256 indices de case, et « choisir la case suivante » est un incrément d'indice :
O(1), zéro branchement, ce qui est précisément l'argument de vitesse qui a tué
l'ordonnancement dynamique pour E2
(msg 5860). Tout le coût et tout le
bénéfice résident dans l'arbre que l'ordre induit :
Entre familles d'ordres, des ordres de grandeur. Le centre d'abord sur E2
est 1010 fois plus coûteux que le balayage
(msg 5263) ; un ordre par blocs
4×4 coûte ~70× de plus que le balayage 1×1 selon les estimations de théorie
complexe de Max, l'écart que résume la règle magique du 10×16
(msg 5867).
Au sein d'une famille, des pourcentages mesurables. Bas-haut-gauche-droite
contre balayage droite-à-gauche : ~15 %
(msg 6023) ; élagage par
équivalence des pièces de bordure : ~10 %
(msg 6062). Bon à prendre,
jamais décisif.
Choisir de travers est invisible. Un mauvais ordre ne produit aucune
erreur, juste un arbre 1010 fois plus gros, silencieusement. Voilà
pourquoi la véritable avancée de la communauté ne fut aucun ordre en
particulier, mais la capacité à noter un ordre avant de l'exécuter : les
comptages de formes d'Owen, puis la
théorie complexe, puis le réglage par chaîne de
Markov de Verhaard combinant ordre et calendrier de glissements
(msg 6423).
Chaque moteur record depuis lors a traité l'ordre comme un objet conçu et
calculé : le peigne-plus-tableau-de-glissements de Verhaard
(eii), le balayage bas-gauche
choisi par théorie complexe de McGavin, et l'ordre de balayage fixe sous les
coupures à seuil de profondeur de
Blackwood. Vingt ans de
science de l'ordre de balayage se condensent en une seule instruction : avant de
dépenser la moindre heure-CPU, dépensez une milliseconde à noter le chemin.