Pourquoi c'est difficile
Eternity II n'est pas difficile par accident. Le casse-tête a été conçu pour résister à l'ingéniosité, et les murs structurels mesurables (rigidité, entropie, motifs interdits) expliquent pourquoi aucune recherche, si ingénieuse soit-elle, n'a atteint la fin.
L'idée la plus importante de la recherche combinatoire difficile : réduire l'espace que l'on explore l'emporte, d'une marge exponentielle, sur le fait de l'explorer plus vite. Eternity II est conçu pour qu'on ne puisse presque pas le réduire.
La section recherche a deux versants : les murs structurels qui rendent Eternity II difficile, et les algorithmes conçus pour les franchir. Cette page fait le pont : chaque méthode confrontée au mur qu'elle attaque réellement, et le score auquel ce mur l'a arrêtée.
L'appariement de bords est NP-complet en tant que famille, mais cela ne dit rien d'un plateau 16×16 fixé : une instance isolée est une constante, pas un problème. Ce qui est vrai, c'est la dureté au pire cas de la famille et la dureté empirique de cette instance, et comment écrire le puzzle pour un solveur SAT, de couverture exacte ou de PLNE, avec de petits croquis détaillés.
La théorie complexe de Brendan Owen estime la largeur de l'arbre de recherche à chaque profondeur, et jusqu'au nombre total de solutions. Beaucoup, dans la communauté, la tiennent pour la chose la plus importante à comprendre sur Eternity II.
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.
Eternity II applique une recette pour obtenir le casse-tête à raccords de bords le plus difficile possible : forme compacte, aucune pièce symétrique ni dupliquée, palettes cloisonnées, fréquences plates, une seule solution attendue. La communauté a rétro-conçu chaque ingrédient dès l'année du lancement.
Chaque plateau record dont nous disposons est figé sur place. Impossible de progresser par petites retouches d'un excellent plateau vers un plateau parfait, et nous pouvons le démontrer.
Si l'on ne peut pas améliorer une excellente grille en la peaufinant, peut-être peut-on sauter vers une autre excellente grille. Sur chaque paire de records testée, c'est impossible, et la raison structurelle mérite qu'on la voie.
Une grille quasi parfaite ne répartit pas uniformément ses rares erreurs. Elle les concentre dans une seule bande de cinq rangées et laisse tout le reste impeccable. Quelle bande ? Cela dépend de la direction dans laquelle la recherche a rempli la grille, et l'on voit le reflet sur les vraies grilles record.
Presque tout petit assemblage de pièces que l'on pourrait construire est impossible. Pour un carré 2×2, 99,72 % des façons de placer quatre pièces ne pourront jamais s'accorder.
La manière habituelle de résoudre un casse-tête logique consiste à repérer un emplacement où une seule pièce convient, à la poser, puis à recommencer. Ce levier n'existe pas ici : chaque pièce intérieure admet entre 73 et 137 voisines possibles, et aucune n'est jamais contrainte à une seule option.
Sur un casse-tête 16×16 construit à l'image d'Eternity II, dix-huit indices dispersés sur le plateau le résolvent en quelques minutes, là où le même casse-tête réclame quatre-vingts indices ou plus, entassés dans des rangées contiguës, pour devenir aussi facile. C'est la position, non le nombre, qui fait levier, et elle pointe droit vers la fin de partie.
Un solveur remplit quelques rangées sans effort, puis se heurte à un mur au milieu du plateau. Voici le mécanisme : une pièce rare dépensée au mauvais endroit, plusieurs rangées plus tôt.
Cinq des 22 couleurs d'Eternity II n'apparaissent que le long de l'anneau de bordure, chacune sur exactement 24 arêtes, jamais une seule fois à l'intérieur. Une séparation structurelle qui façonne la manière dont chaque solveur traite le cadre.
Une grille résolue dissimule une loi comptable toute simple : chaque couleur que le bord tend vers l'intérieur, l'intérieur la lui rend aussitôt. La violer, c'est savoir sur-le-champ que la grille est fausse ; la respecter, en revanche, ne garantit rien.
Eternity II a deux règles : les bords doivent coïncider, et chaque pièce ne sert qu'une fois. La première est généreuse. Toute la difficulté tient dans la seconde.