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 ; les entasser
au contraire dans des rangées contiguës, une mesure en a réclamé une centaine
(soixante de bordure plus quarante intérieurs) rien que pour ramener la
recherche à des dizaines de milliards de placements. Pour établir nous-mêmes le
seuil de bascule, nous avons rejoué le même affrontement sur un plateau assez
petit pour être résolu jusqu'au bout : égaler un réseau dispersé de seize
indices a demandé cinq rangées contiguës, quarante indices, environ deux
fois et demie le nombre, tranché par la seule 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. 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 pour ramener
la recherche à une taille maniable : une centaine d'indices (soixante de bordure
plus quarante rangées intérieures) laissait encore un arbre d'environ 47
milliards de placements
(msg 11725).
Ni l'un ni l'autre de ces chiffres n'établit le seuil avec précision, car un
plateau 16×16 ne se termine jamais en quelques secondes et le décompte brut est
brouillé par les correspondances gratuites qu'un bloc plein vous offre. Nous
avons donc réduit le casse-tête à une taille qui, elle, se termine, un 8×8
construit selon la même recette de couleurs, et mesuré la vraie grandeur : le
nombre de nœuds jusqu'à une résolution complète, sur trente instances graines
par disposition. Là, un réseau dispersé de seize indices résout chaque instance
en quelques milliers de nœuds de recherche. Les rangées contiguës doivent grimper
à cinq rangées pleines, quarante indices, avant de résoudre chaque instance dans
le même budget de nœuds. À nombre égal, seize indices dispersés l'emportent
sur seize entassés en deux rangées de plus de deux ordres de grandeur en nœuds de
recherche, et le bloc échoue à en résoudre six sur trente. Le réseau atteint la
fin de partie ; le bloc ne l'atteint jamais avant de presque l'ensevelir.
18
indices dispersés, résolu en minutes
2,5×
d'indices en plus, en rangées contiguës, pour égaler un réseau dispersé (mesuré jusqu'à la résolution)
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. Le seuil des cinq rangées est notre
propre mesure, sur nos propres plateaux 8×8 générés et notre backtracker : le
plus petit nombre de rangées contiguës dont le taux de résolution et le nombre
médian de nœuds jusqu'à la solution égalent tous deux un réseau dispersé de
seize indices, sur trente instances graines par disposition. Reproduisez-le
avec just experiments hint-study-solve.