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.
Mesurez les 256 pièces officielles sans aucun solveur en vue et chaque porte structurelle est fermée : aucune pièce symétrique par rotation, 5 paires jumelles sur 32 640 appariements, un plafond de 307 sur 480 si rien ne tourne, des budgets de couleurs qui s'apparient à exactement 480 sans aucun jeu, et une palette 17+5 posée au point d'une-solution-attendue.
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. Une mesure sur plateaux plantés chiffre le choix de la formulation : une falaise de résolubilité qu'un paradigme de recherche heurte et qu'un autre franchit, et qui bouge avec le nombre de couleurs.
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.
Un argument de comptage sur le jeu de pièces officiel interdit un score d'exactement 479/480 : les demi-arêtes de chaque couleur viennent en nombre pair, et un unique raccord cassé laisserait deux comptes impairs. Le plancher sous le parfait est 478, et au plus 76 quasi-solutions à un coup peuvent entourer une solution.
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).
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.
Le plateau communautaire dans les hauts 460 se lit comme une frontière de phase entropique de l'instance, pas comme une limite du génie logiciel : le calcul exact sur le jeu officiel donne une densité de contraintes proche de 0,0094, un paysage recuit qui s'effondre au-delà de 470 et ne franchit 1 qu'à 480, et un nombre attendu de 10 à 20 solutions parfaites quasi orthogonales entre elles. Les nombres côté instance sont exacts ; le tableau du fossé de recouvrement en 16x16 est une conjecture assumée.
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.
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.
Cinq des 22 couleurs ne touchent jamais les 196 pièces intérieures. La liste des pièces force toute solution valide à dépenser les 120 demi-arêtes de cadre sur l'anneau du bord : un sous-puzzle autonome à jeu exactement nul (120 = 120), un circuit eulérien sur cinq sommets, relié à l'intérieur par seulement 56 arêtes tournées vers le centre.
Pondérez chaque couleur d'arête et lisez chaque pièce comme un vecteur signé, est moins ouest sur un axe, sud moins nord sur l'autre. Sommé sur une région quelconque, les coutures intérieures s'annulent et seule la bordure survit, si bien que le plateau totalise zéro. Un quart de tour pivote le vecteur d'un angle droit, ce qui fait de la loi une algèbre dans les entiers de Gauss.
Si l'on ne peut pas améliorer un excellent plateau en le peaufinant, peut-être peut-on sauter vers un autre excellent plateau. Sur chaque paire de records testée, c'est impossible, et la raison structurelle mérite qu'on la voie.
Empruntez l'astuce du physicien qui rend les défauts cristallins solubles et tentez de transformer un joint dépareillé en dislocation dotée d'une charge conservée. Cela échoue de trois façons : une hauteur scalaire est aveugle aux ruptures, l'ensemble des ruptures forme des chaînes ouvertes et non des boucles fermées, et le courant orienté par couleur n'est pas conservé. Seul un bit de parité non signé survit.
Un plateau quasi parfait ne répartit pas uniformément ses rares erreurs. Il 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 le plateau, et l'on voit le reflet sur les vrais plateaux record.
Remplissez un plateau dans un ordre fixe et les trois quarts du haut se posent librement, tandis que la difficulté s'entasse dans la bande que vous terminez en dernier. Sur quarante plateaux générés, tout le reste tombe dans la moitié basse à chaque fois ; mélangez l'ordre de remplissage et il se disperse, donc la région difficile est fabriquée par le balayage, pas cachée dans le plateau.
Sommez, pour n'importe quel ordre de visite du plateau 16x16, le nombre de voisins déjà posés que chaque case affronte à l'instant où elle est remplie : le total vaut exactement 480, quel que soit l'ordre. Un ordre de remplissage ne peut pas ajouter de restriction ; il choisit seulement quand chaque restriction s'applique. Ce qui sépare les ordres, c'est l'immédiateté, la distance entre une décision et sa réfutation, et seuls les extrêmes de ce classement appartiennent au puzzle plutôt qu'au moteur.
Lisez un plateau complet comme un mot de code dont les 480 jointures intérieures sont des contrôles de type parité, et le score d'arêtes appariées devient 480 moins le nombre de contrôles en échec. C'est une lentille nette reposant sur une seule identité porteuse, et il vaut la peine d'être précis sur ce que la vue par codes correcteurs apporte et sur ce qu'elle ne fait que renommer.
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.
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ù les entasser en rangées contiguës en réclame une centaine rien que pour ramener la recherche à des dizaines de milliards de placements. C'est la position, non le nombre, qui fait levier, et elle pointe droit vers la fin de partie.
Relier les paires d'indices par des couloirs de pièces posés tôt donne l'impression d'ajouter des contraintes. Le comptage dit le contraire : un couloir de largeur 1 entre les deux indices les plus proches admet environ deux millions de milliards de remplissages distincts, donc il n'exclut presque rien tout en dépensant des pièces dont la fin de partie aura besoin. Dans un A/B contrôlé, chaque bras couloir a perdu face à son propre témoin à chaque taille de plateau.
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.
L'anneau de bordure est la partie la plus contrainte du casse-tête ; une bordure forte différente devrait donc fixer un intérieur haut différent. Il n'en est rien. De nombreuses bordures entièrement appariées et distinctes, chacune complétée par un même producteur d'intérieur fixe, donnent des sommets quasi maximalement différents les uns des autres mais uniformément bas, aucun près de la zone record. La bordure diversifie le plateau sans en prédire le plafond.
Un plateau résolu 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 le plateau est faux ; la respecter, en revanche, ne garantit rien.
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.
Un seul arc de recherche, treize familles de théorèmes structurels : pureté de l'anneau, le plancher de parité à 479, le mur des 470 comme frontière de phase, les invariants de flux, la loi d'aire entropique, et les résultats d'impossibilité qui chiffrent chaque raccourci classique. Cette page est la carte.