Donnez gratuitement à un solveur quelques pièces correctes et le casse-tête
devient plus facile. La question évidente est de savoir combien il en faut. La
meilleure question, il s'avère, est de savoir où les placer. Sur un casse-tête
16×16 construit avec la recette de couleurs exacte d'Eternity II, dix-huit
indices posés aux bons endroits le résolvent en quelques minutes ; le même
casse-tête, lui, en réclame quatre-vingts ou plus, si on les entasse dans des
rangées contiguës, pour être aussi facile. Un facteur quatre sur le nombre,
tranché entièrement par la géométrie.
Chargement…
Le plateau de gauche est la disposition réelle qu'a employée Peter McGavin :
dix-huit indices sur un réseau régulier, une colonne sur trois, sur quelques
rangées éparses. Son backtracker à balayage de rangées, sans fioritures, a
résolu le casse-tête 16×16 façon E2 de Joe (cinq couleurs de bordure, dix-sept
couleurs intérieures, la même distribution que le casse-tête officiel) en moins
de quinze minutes sur un seul cœur, en parcourant un arbre de recherche de
41 160 067 167 placements. Descendre à quinze indices marchait encore ; la
recherche gonflait simplement à plusieurs heures. Entassez au contraire les
dix-huit indices dans les premières rangées, à la manière dont un balayage de
haut en bas les accumule naturellement, et ils n'achètent presque rien : la
partie difficile du plateau reste entièrement ouverte.
Joe l'avait abordé par l'autre bout, en amorçant des rangées contiguës entières
à partir d'une solution connue, et il lui en fallait bien davantage avant que le
casse-tête ne cède :
18
indices dispersés, résolu en minutes
88+
indices en rangées contiguës pour une facilité comparable
99%
du temps de recherche passé au-delà de la profondeur 132
70%
du temps de recherche passé au-delà de la profondeur 150
Les deux nombres de droite expliquent ceux de gauche. Joe a instrumenté son
backtracker sur plus d'un milliard d'itérations et constaté que le travail n'est
pas du tout réparti sur le plateau : 99 % s'effectue après la profondeur 132 sur
256, et 70 % après la profondeur 150. Presque toute la douleur est dans la
seconde moitié du remplissage, et l'essentiel au-delà des trois cinquièmes.
Un bloc d'indices contigus en haut est dépensé exactement là où la recherche
n'allait jamais peiner. Il raccourcit un début facile et laisse intacte la queue
coûteuse. Les indices dispersés font l'inverse : parsemés à travers le plateau,
jusque dans la région que la recherche atteint en dernier, ils devancent les
choix qui, sinon, exploseraient loin dans l'arbre. C'est le même fait que les
plateaux records portent à leur surface. Un plateau quasi parfait concentre tous
ses dégâts dans la bande de rangées sur laquelle la recherche s'est terminée,
parce que
ce sont les rangées remplies en dernier qui vous font payer le casse-tête.
Les indices n'aident que dans la mesure où ils atteignent cette bande avant la
recherche.
Cela cadre aussi avec le fait que l'intérieur ne donne aucun coup forcé :
chaque cellule intérieure acceptant encore des dizaines de voisines, la valeur
d'un indice ne tient pas à une propagation locale mais à une contrainte globale,
qui élague des sous-arbres entiers que la recherche aurait sinon dû parcourir.
Un indice loin de la région difficile n'élague que des sous-arbres qui étaient
de toute façon bon marché.
C'est un résultat sur un casse-tête 16×16 construit selon la recette de couleurs
d'Eternity II, et non sur le casse-tête officiel, dont les cinq indices fixes
constituent un cadeau différent, bien plus modeste, à des endroits différents.
Ce qui se transpose, c'est la forme de la leçon, et c'est la même que celle que
l'argument élagage contre vitesse formule par
l'autre bout : ce qui compte, c'est de changer l'endroit où la recherche dépense
son effort, et l'effort réside dans la fin de partie. Une poignée d'indices
visant cette fin de partie vaut une multitude d'indices visant n'importe où
ailleurs.
Les décomptes, l'arbre de 41 milliards de nœuds et les statistiques de
profondeur sont les mesures de Joe et de Peter McGavin, rapportées sur la
liste groups.io eternity2 en janvier 2026 ; la disposition dispersée montrée
est décodée du plateau publié par Peter (msg 11746). Le backtracker optimisé
qu'a employé Peter remonte au message de Mike de 2007 (msg 3098). Ce sont des
résultats communautaires sur un casse-tête façon E2 particulier, consignés ici
avec attribution plutôt que redérivés.