Eternity II utilise 22 couleurs, réparties entre 17 couleurs intérieures et 5 réservées au cadre, et ce chiffre d'environ 17 se situe près du point où ce type de casse-tête est le plus difficile à résoudre (la transition est une bande, pas un entier unique).
Reproduces the 17/5 interior/frame color split. The hardness-peak location is separately measured in-repo by the hardness-peak experiment (an 8x8 solver-effort sweep plus Owen's criterion recomputed to 17.14 at size 16); the 'one expected solution' claim for the full 16x16 board still rests on the cited external sources (Owen msg 1947, Ansótegui/Mateu).
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).
Nous l'avons mesuré ici. Le critère d'Owen n'a jamais été énoncé que pour le
plateau complet ; nous l'avons donc passé à une seconde taille pour voir s'il
tient. La même formule prédit (36!⋅436)1/72≈7.56 couleurs
intérieures pour un plateau 8x8, et un 8x8 est assez petit pour qu'un
backtracker ordinaire résolve réellement des instances aléatoires : sa courbe de
difficulté se balaie directement. En mesurant l'effort du solveur en fonction du
nombre de couleurs intérieures sur des plateaux 8x8 générés (le générateur et le
DFS du site), la bande dure, là où la recherche cesse de trouver une solution
dans le budget imparti, tombe exactement où le critère à la taille 8 le prédit.
Le balayage 16x16 complet forme l'autre moitié du tableau : un backtracker
ordinaire ne le termine à aucun nombre de couleurs, et la profondeur qu'il
atteint décroît régulièrement à mesure que les couleurs augmentent, si bien que
le vrai plateau se situe au-delà du point où la courbe est déjà devenue
verticale. L'expérience hardness-peak
contient le code, les deux balayages et le critère recalculé dans le dépôt (il
reproduit le 17,14 d'Owen à la taille 16).
▶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 aucun désaccord
(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.