Jusqu'ici, chaque méthode de ce rayonnage traite Eternity II comme une
recherche discrète : placer, vérifier, revenir en arrière. La communauté des
physiciens a proposé quelque chose de plus étrange. Le groupe de Veit Elser à
Cornell a reformulé la satisfaction de contraintes comme de la géométrie, un
point rebondissant entre deux ensembles dans un espace de grande dimension, et
a fait chevaucher un même schéma d'itération de la reconstruction de phase en
cristallographie aux rayons X jusqu'au Sudoku, au 3-SAT et au repliement des
protéines, portant la méthode en couverture de PNAS
(Elser, Rankenburg & Thibault, 2007).
Les puzzles à appariement d'arêtes en sont presque l'illustration idéale, et la
couverture de ce numéro de PNAS en montrait précisément un, comme l'a fait
remarquer le membre qui a apporté ces travaux à la liste
(message groups.io 9347).
Cette page explique la méthode comme il se doit, car elle est réellement
frappante et réellement différente de tout le reste du catalogue. Elle rapporte
ensuite ce que la communauté Eternity II en a effectivement fait : un accès
d'intérêt en 2014–2015, un test empirique, une archive du propre code d'Elser
partagée, et aucune campagne. C'est une voie connue, ici peu fréquentée.
On plonge un état du plateau comme un point x dans un espace euclidien,
disons un vecteur réel avec une coordonnée par triplet (case, pièce, rotation),
où un plateau légal est une assignation 0/1. Définissons maintenant deux
ensembles de contraintes :
- C1, pièces utilisées une fois : chaque case contient exactement une
pièce-rotation, et chaque pièce est utilisée exactement une fois. Les
couleurs des arêtes sont ignorées.
- C2, arêtes concordantes : chaque paire d'arêtes en contact s'accorde
en couleur, et le bord est gris. L'inventaire des pièces est ignoré, si bien
que les cases peuvent contenir des mélanges fractionnaires ou des pièces
dupliquées.
Un Eternity II résolu est exactement un point de C1∩C2. L'astuce qui
rend la formulation utile, c'est que chaque ensemble pris seul est facile à
projeter. Étant donné un x arbitraire, on peut calculer à moindre coût le
point le plus proche de l'ensemble :
- P1(x), l'assignation de pièces valide la plus proche, est un problème
d'appariement biparti : affecter 256 pièces à 256 cases pour maximiser
l'affinité totale. L'algorithme hongrois le résout exactement en temps
polynomial, le même moteur d'affectation qui alimente l'étape de recomplétion
de la recherche locale.
- P2(x), le coloriage cohérent en arêtes le plus proche, se décompose arête
par arête : chaque jointure intérieure moyenne simplement ses deux côtés vers
l'accord. Purement local, massivement parallèle.
Chaque projection est un problème résolu. Toute la difficulté d'Eternity II
réside entièrement dans l'intersection, et le schéma naïf, l'alternance de
projections x↦P1(P2(x)), échoue exactement comme on l'imagine : il
converge vers une paire de points, un dans chaque ensemble, localement aussi
proches que possible et globalement faux. Un minimum local, déguisé en
projection.
Cette vision à deux faces a atteint la liste indépendamment d'Elser. Dès 2008,
antminder proposait de découper les pièces en triangles d'arête et de chercher
dans le domaine des losanges colorés
(message 6184), et JSA y a
aussitôt reconnu le problème dual
(message 6185) : Eternity II,
c'est 256 pièces à disposer pour que 480 arêtes concordent, ou 480 carrés
d'arête colorés à disposer pour qu'ils engendrent les 256 pièces correctes.
Résoudre, c'est rendre les deux descriptions vraies à la fois.
La réponse d'Elser au piège du minimum local n'est pas d'alterner les
projections, mais d'itérer une difference map. Sous la forme publiée, avec le
paramètre fixé à β=1, un pas s'écrit
x↦D(x)=x+P1(2P2(x)−x)−P2(x),
et la famille à β général interpole autour de cette expression au moyen
de points « estimés » internes fi(x) construits à partir des projections
(PNAS 2007). Trois propriétés font
tout le travail :
- Point fixe = solution. Si D(x∗)=x∗, alors
P1(2P2(x∗)−x∗)=P2(x∗) : le même point appartient aux
deux ensembles. On lit la solution comme P2(x∗), et non comme
x∗ lui-même : l'itéré est un chercheur, non un plateau. La
terminaison est détectée lorsque le déplacement
Δ=∥D(x)−x∥ passe sous un seuil, et le candidat est
alors vérifié exactement.
- Aucune fonction de coût. L'application ne descend rien. Cela ressemble à
un défaut, et c'est précisément l'intérêt : un hill-climber reste bloqué là
où sa fonction de score présente un optimum local, mais la difference map
n'a aucun score pour la flatter et la retenir. Loin des points fixes elle
continue de bouger, en pratique de façon chaotique, si bien que les
configurations quasi-optimales qui piègent la
recherche locale sont des
lieux qu'elle visite puis quitte. C'est l'« effet tunnel » que les
physiciens prisaient.
- L'itéré vit hors des deux ensembles. x n'a pas besoin de satisfaire
l'une ou l'autre contrainte pendant la recherche. Comme les plateaux
fractionnaires de la
relaxation LP, il explore une
superposition de plateaux. À la différence du LP, il n'a aucun objectif à
optimiser et aucun optimum sur lequel plafonner : ses seuls lieux de repos
sont les solutions.
Pour β=1 la difference map coïncide avec l'itération de
Douglas–Rachford, une méthode de projection que les analystes convexes
étudient depuis les années 1950 ; la convergence est démontrable lorsque les
deux ensembles sont convexes, et totalement non garantie ici, où C1 est un
nuage de points de permutation. La liste Eternity II n'a appris le nom de la
famille qu'en 2025, quand Wyatt Carpenter a trouvé Wikipédia créditant
« l'algorithme de Douglas–Rachford » pour la résolution de TetraVex et l'a
signalé comme une piste possiblement prometteuse que personne n'avait soulevée
(message 11592) ; JSA a bouclé
la boucle, renvoyant au fil Elser de 2014–2016 et présentant Douglas–Rachford
comme la vision par décomposition f(x)+g(x) de la même attaque
(message 11594). La littérature
d'optimisation avait bel et bien adopté la méthode pour exactement cette
famille de puzzles
(Aragón Artacho, Borwein & Tam).
L'image à deux ensembles ci-dessus exigeait une projection globale (P1 est
un unique gros appariement). L'article suivant de Gravel et Elser,
Divide and concur
(préprint ouvert), rend la construction
mécanique pour n'importe quel CSP. On donne à chaque contrainte sa propre
réplique privée de chaque variable qu'elle touche :
- La projection divide satisfait chaque contrainte indépendamment sur ses
propres répliques. Chaque contrainte devient un petit problème local (pour
Eternity II : une arête, deux côtés de pièce), trivialement projetable.
- La projection concur force toutes les répliques d'une même variable à
s'accorder, en remplaçant chacune par leur moyenne, la projection la moins
coûteuse qu'on puisse imaginer.
Faites tourner la difference map entre divide et concur et vous obtenez un
solveur CSP général dont le travail par itération est entièrement local,
l'étape de moyennage jouant le rôle de la communication. Gravel et Elser l'ont
comparé au 3-SAT, où il passait à l'échelle de façon comparable à WalkSAT, et
s'en sont servis pour améliorer des empilements de sphères connus. Lorsque la
méthode a atteint la liste, Dima en a immédiatement reconnu la structure venue
de son propre domaine : le schéma de moyennage des répliques est un proche
parent de la propagation de croyance sur le graphe de contraintes, un lien que
les auteurs eux-mêmes établissent
(message 9348). Pour les lecteurs
de ce wiki l'air de famille va plus loin : une recherche par passage de
messages sur un graphe qui n'est localement arborescent nulle part (chaque bloc
2×2 est un cycle) est exactement le cadre où les méthodes apparentées de la page
impasses (propagation d'enquête, ordonnancement
des coups par propagation de croyance) se sont aplaties et éteintes.
Le compte rendu, intégral, car il est court.
- 2008, un rejet en passant. La première mention de la méthode sur la liste
est Don Milne rangeant la « difference map » parmi les techniques
d'optimisation qu'il jugeait incapables de résoudre des CSP complexes : elles
ne brillent que lorsque les solutions sont denses, et Eternity II a été
conçu pour n'en avoir presque exactement qu'une
(message 5479).
- 2014, la véritable introduction. Le schéma du réseau d'arêtes du puzzle
proposé par un membre a conduit JSA à énoncer le problème dual et à présenter
les travaux d'Elser : la difference map « fait des allers-retours entre les
deux problèmes duaux »
(message 9347), avec des renvois
vers l'article de PNAS et l'article divide-and-concur de Physical Review
(message 9350). Les propres
diapositives ICCOPT-MOPTA 2007 d'Elser, qui mentionnent Eternity II dans
leurs trois dernières diapositives, ont été déposées dans les fichiers du
groupe (message 9349).
- 2014, l'unique test empirique. Dima a lu l'article de PNAS, l'a apprécié,
et l'a vérifié : il a écrit un simple hill-climber pour le propre benchmark de
3-coloriage de graphe de l'article et a résolu l'instance N=16 en quelques
secondes, là où la Table 2 de l'article donne à la difference map de l'ordre
de dix minutes. « Ce qui me fait me demander si c'est vraiment à la hauteur de
la hype » (message 9351), tout
en jugeant encore l'idée à deux faces pièces-contre-arêtes digne d'être
explorée pour E2.
- 2015, du code et une promesse. Quelqu'un a obtenu du code source d'Elser
en personne, avec un exemple d'appariement d'arêtes 5×5 traité, et l'a partagé
dans les fichiers du groupe
(message 9362). Dans le fil
« New Approach? » cet été-là, JSA a récapitulé le statut de la méthode : elle
« a résolu de petites versions du modèle d'Eternity II », et si elle avait
résolu la grande « nous en aurions entendu parler »
(message 9442). Juraj Pivovarov
a demandé une difference map concrète écrite noir sur blanc pour Eternity II
(message 9443) ; JSA a promis un
bref exposé (message 9446) qui
n'apparaît jamais dans l'archive. Dans le même fil Dima a esquissé
explicitement le transfert primal–dual (transporter une solution de coloriage
d'arêtes vers l'assignation de pièces la plus proche avec l'algorithme
hongrois, et retour) et a rapporté que son propre recuit côté dual plafonnait
à 48/49 tuiles correctes sur le 7×7 de Brendan Owen
(message 9445), tandis que Mike
Pringle rappelait le cousin maison de la liste, l'approche d'échange d'arêtes
SRD de 2007 : capable du 8×8, jamais du 10×10
(message 9447).
- 2025, un nom et un haussement d'épaules. Le fil Douglas–Rachford
(message 11592) n'a suscité
qu'une évaluation rapide, utile pour la théorie, « mais guère plus »
(message 11593), et la réflexion
de JSA selon laquelle, sur un puzzle bâti pour être optimalement difficile, il
s'attendrait à ce que le nombre d'itérations soit « de l'ordre de » celui des
nœuds d'un backtracker de toute façon
(message 11594).
Voilà le compte rendu tout entier : aucun membre n'a jamais rapporté avoir fait
tourner la difference map ou divide-and-concur sur le puzzle complet à 480
arêtes, ni même sur l'échelle de benchmarks 10×10. La littérature à comité de
lecture a une forme comparable. Le groupe d'Elser a publié les succès de la
méthode sur le coloriage, le SAT, l'empilement et le repliement, et a réservé
Eternity II aux exposés, aux illustrations de couverture et au code d'exemple.
Personne n'a publié de résultat de difference map sur le puzzle complet, positif
ou négatif.
Pourquoi si peu de reprise ?
En partie le calendrier (le fil de 2014 est tombé dans les années les plus
calmes de l'archive) et en partie le point de données de Dima, qui a vite
terni l'éclat. Mais la raison plus profonde est celle que Don Milne a donnée
en 2008 et que JSA a répétée en 2025 : les méthodes stochastiques continues
paient lorsque les solutions sont abondantes relativement à l'espace, et
Eternity II siège au
pic de difficulté conçu où elles ne le sont
pas. La méthode est célèbre parce que l'appariement d'arêtes l'illustre à
merveille, non parce qu'elle résout l'appariement d'arêtes à grande échelle.
L'écart entre « discuté » et « mesuré » est assez étroit pour qu'une seule
personne puisse le combler. Une tentative moderne consisterait à :
- Fixer le plongement. Vecteurs one-hot par case sur 1 024
pièces-rotations (la version à deux ensembles), ou répliques divide-and-concur
par contrainte d'arête. C'est l'étape que Juraj a réclamée en 2015 et que
personne n'a écrite pour E2 ; le code 5x5 partagé par Elser
(message 9362) en est le
gabarit de départ naturel.
- Implémenter les deux projections. L'accord d'arête est une moyenne
locale ; la validité de pièce est une résolution hongroise par itération (256
cases x 1 024 candidats), ou du pur moyennage de répliques sous la forme
divide-and-concur.
- Gravir l'échelle des benchmarks. Confronter à la
suite de puzzles de Brendan Owen, le même 7×7
où le recuit dual de Dima a atteint 48/49, puis 8×8, 9×9, 10×10, avec un
simple hill-climber et un backtracker à redémarrages comme témoins, en
traçant les itérations-jusqu'à-solution en fonction de la difficulté de
l'instance.
- Rapporter la courbe, pas l'anecdote. La sortie intéressante est
l'exposant de passage à l'échelle : les propres articles d'Elser rapportent
des nombres d'itérations croissant fortement avec la difficulté de
l'instance, et la question ouverte que JSA a posée en 2014, comment cela
passe-t-il à l'échelle pour des instances de classe E2 ?
(message 9350), n'a jamais reçu
de réponse chiffrée sous forme de graphe.
Le meilleur cas réaliste n'est pas un puzzle résolu. C'est une méthode
caractérisée : soit une courbe de passage à l'échelle qui croise celle du
backtracker en un point intéressant, ce qui serait une nouvelle, soit une
entrée négative propre pour le registre des
impasses, ce qui est aussi un progrès.
- Par itération : deux projections. La projection d'arête est linéaire en
le nombre d'arêtes. La projection de pièce est la coûteuse : une résolution
d'affectation exacte est en O(n3) pour l'algorithme hongrois, et à
n=256 cases cela fait des millions d'opérations par itération, face aux
dizaines de millions de placements par
seconde d'un backtracker réglé.
Divide-and-concur échange cela contre du pur moyennage local, au prix d'un
état répliqué bien plus volumineux.
- Aucune garantie de convergence. La théorie de convergence de
Douglas–Rachford est convexe ; les deux ensembles d'Eternity II sont des
nuages combinatoires. Sur les instances faisables, l'application trouve
généralement des points fixes en pratique (c'est le contenu empirique des
articles), mais rien ne borne le nombre d'itérations, et sur ce puzzle
l'attente de JSA est qu'il égale le nombre de nœuds du backtracking
(message 11594).
- Point fixe = solution, et rien de moindre. La méthode n'offre aucune
sortie partielle utile : jusqu'à ce que Δ→0 vous avez un point
errant dans un espace fractionnaire, et non un plateau scoré. Il n'y a aucun
lot de consolation à 460 arêtes en chemin, ce qui importe sur le seul puzzle
où l'échelle des records se compte en scores partiels.
- Le tableau des scores. Un test communautaire, perdu face à un
hill-climber sur le propre benchmark de la méthode
(message 9351) ; de petits
modèles d'appariement d'arêtes résolus dans les matériaux d'Elser ; le puzzle
complet intouché. Élégante, rigoureuse, ici non démontrée, et, chose
inhabituelle pour ce wiki, encore non mesurée plutôt que mesurée-et-enterrée.