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.
Les problèmes de recherche difficiles possèdent un bouton de réglage de la
difficulté. Desserrez-le et les solutions se multiplient : une recherche en
trouve une presque aussitôt. Serrez-le et il n'en existe plus, ce qui est
souvent facile à prouver. Entre les deux se trouve une bande étroite où les
solutions sont rares mais bien réelles, et c'est là que la recherche explose.
On parle de transition de phase, comme l'eau qui gèle.
Pour les casse-tête à appariement de bords, ce bouton est le nombre de
couleurs. Trop peu et les pièces s'emboîtent d'innombrables façons ; trop et
elles ne s'ajustent presque plus. L'
analyse publiée
situe le pic autour de 17 couleurs intérieures, le réglage pour lequel un
casse-tête de cette taille possède environ une seule solution. Eternity II en
utilise 17.
La communauté disposait de ce chiffre quelques semaines après le lancement :
en août 2007, Brendan Owen a dérivé I=(196!⋅4196)1/392≈17.14
couleurs intérieures à partir du critère « environ une solution attendue »,
exactement les paramètres publiés, des années avant les analyses académiques
(Concevoir le casse-tête le plus difficile, msg 1947).
▶Interactif : le pic de difficulté selon le nombre de couleursExplorer →
Voici les mêmes données que la page Algorithmes : le travail médian pour résoudre un puzzle généré, selon la taille du plateau et le nombre de couleurs. L'axe vertical est logarithmique : chaque ligne vaut dix fois celle du dessous. Lisez-le comme le bouton de difficulté du puzzle.
Taille du plateau:
Chargement du graphique…
Sur un plateau 7x7, le travail dépasse les soixante millions autour de cinq ou six couleurs, puis chute d'un facteur cent mille à mesure que les couleurs augmentent. Plus le plateau est grand, plus le pic est net et décalé vers la droite. Le 16x16 complet se situe bien plus haut et à droite que tout ce qu'on peut tracer ici, et c'est pourquoi son réglage à 17 couleurs tombe en pleine région difficile.
Le travail est le nombre de placements effectués par le solveur ; les valeurs sont des médianes sur de nombreux puzzles générés. Les points du côté pauvre en couleurs sont des bornes inférieures là où une exécution a été arrêtée tôt.
Le graphique ci-dessus est précalculé. Celui-ci ne l'est pas : le moteur
résout en direct des casse-tête inédits, un par nombre de couleurs, et trace le
pic à partir de véritables exécutions dans votre navigateur.
▶Interactif : résoudre en direct de part et d'autre du pic de difficultéExplorer →
L'argument fondé sur le nombre de couleurs indique où se trouve le pic. En
mars 2008, Brendan Owen est allé observer une transition de phase directement,
sur les pièces réelles. Il a pris un mince rectangle intérieur de 2 par L et l'a
pavé avec des ensembles aléatoires de pièces intérieures d'E2 - quatre cents
ensembles aléatoires pour chaque longueur - en notant combien pouvaient être
complétés sans aucune non-concordance
(msg 4909).
Chargement du graphique…
La forme obtenue est la transition de phase en miniature. Une bande de 2 par 1
ou 2 par 2 est si courte que des pièces aléatoires s'y ajustent souvent : 58 %
de cas résolubles à la longueur 1. Puis tout s'effondre. De la longueur 4 à la
longueur 15, pas un seul ensemble aléatoire sur quatre cents ne pave le
rectangle, quelle que soit la longueur : les solutions sont si rares qu'elles
n'existent pratiquement pas. Et elles reviennent ensuite. À la longueur 16, un
ensemble sur quatre cents fonctionne ; à 19, on atteint 8,5 % ; à 21, 57 % ; et
à 22, près de neuf sur dix. La région où les solutions sont extrêmement rares
sans être encore impossibles est précisément la bande difficile, et ici ce
n'est ni un récit ni un modèle : c'est un décompte. C'est aussi pourquoi un
intérieur large de 14 cases est si redoutable : il se situe dans la partie
raide de cette montée, là où une solution existe mais où presque aucun
arrangement aléatoire n'en est une.
C'est le signe le plus net qu'Eternity II a été rendu difficile
délibérément. La taille du plateau, le nombre de pièces et la répartition des
couleurs visent tous la même cible : un casse-tête à environ une seule
solution, placé à l'endroit le plus défavorable qui soit pour n'importe quelle
recherche. La difficulté a été choisie, comme un bon examen n'est ni trivial ni
impossible.
Comment savons-nous que ce pic est réel et non un simple récit ? Deux voies se
rejoignent ici. L'analyse publiée le
dérive :
pour les casse-tête à appariement de bords avec cadre, le nombre de couleurs
pour lequel on attendrait environ une solution tombe près de 17, et c'est le
réglage le plus difficile à explorer. Et vous pouvez en observer une part
vous-même dans la démonstration ci-dessus : construisez de vrais casse-tête,
comptez le travail effectué, et voyez-le exploser lorsque les couleurs se font
rares. La conséquence est concrète. Elle signifie que l'écart jusqu'à une
solution n'est pas un problème de réglage que l'on peut réduire à force d'une
machine plus rapide ; le casse-tête a été placé là où la recherche est la pire,
volontairement, de sorte que le vaincre exige une idée réellement meilleure, et
non simplement plus d'efforts.