Il existe trois routes classiques vers Eternity II. Le retour arrière parcourt
l'arbre. Les
encodages SAT et CSP confient la
logique à un solveur industriel. La troisième route appartient aux
optimiseurs : écrire le puzzle comme un programme en nombres entiers
(variables, contraintes linéaires, objectif) et appeler CPLEX. C'est la route
que tout spécialiste de recherche opérationnelle essaie en premier, car elle
s'accompagne d'un coup que les deux autres n'ont pas : la relaxation.
Supprimez l'exigence que les variables soient entières et le programme en
nombres entiers, NP-difficile, devient un programme linéaire, résoluble en
temps polynomial. Résolvez la version facile, espérez que la réponse soit
presque entière, réparez le reste.
La communauté a emprunté cette route à répétition entre 2007 et 2025, avec des
solveurs allant de glpsol à CPLEX en passant par des Newton–Raphson codés à
la main, et le résultat a été mesuré assez précisément pour mériter une page :
la relaxation se résout vite et rapporte un plateau presque parfait, fait de
fractions de pièces. Forcez les pièces à être entières et le score s'effondre
sur un plateau autour de 420–440 des 480 arêtes. L'écart entre l'optimum
fractionnaire et l'optimum entier n'est pas un détail technique. C'est
exactement l'endroit où vit le puzzle.
Une variable binaire par placement, exactement comme dans l'encodage SAT :
soit xc,p,r∈{0,1} signifiant « la pièce p occupe la case c avec
la rotation r ». Deux familles de contraintes d'affectation et un décompte
par joint donnent le modèle complet :
maxs.t.s∑ysp,r∑xc,p,r=1c,r∑xc,p,r=1ys≤k∑min(fs,k1,fs,k2)(matched seams)∀cell c∀piece p∀seam s
où fs,ki est le flux de couleur, le poids total des placements du
côté i du joint s qui exposent la couleur k à travers celui-ci,
fs,ki=∑(p,r)showingkxci,p,r. Le min est
linéarisé avec une variable auxiliaire par joint et par couleur ; pour la
version de faisabilité, on exige plutôt un flux de couleur égal des deux
côtés de chaque joint. Les modèles de la communauté atterrissent exactement
là où l'arithmétique le prédit. Le LP de Benjamin de 2009 comptait ~50 000
variables (placements élagués aux positions valides) et 7 952 équations : 256
par case, 256 par pièce, et 60×5+420×17=7,440
contraintes d'équilibre couleur-joint
(message 6910). Le modèle de
Vlasta de 2008 portait 160 254 binaires
(message 5602) ; le programme
binaire AMPL/CPLEX de Jimmy Timmermans, 272 704 variables et 24 566 équations
(message 6728). Günter
Stertenbrink avait déjà posé la forme graphe équivalente en 2007 : faire des
262 144 placements des sommets, relier les paires compatibles, et demander une
clique de taille 256 (message 627),
la formulation vers laquelle la littérature académique est revenue une
décennie plus tard.
La relaxation ne demande qu'une seule modification : remplacer
xc,p,r∈{0,1} par 0≤xc,p,r≤1. Ce simple changement fait
franchir au problème la frontière la plus importante de l'optimisation. Le
programme en nombres entiers est NP-difficile : la programmation en 0–1 est
l'un des 21 problèmes complets originaux de Karp. Le programme linéaire est
résoluble en temps polynomial (ellipsoïde, points intérieurs), et en pratique
le simplexe expédie ces tailles de modèle presque instantanément. Benjamin l'a
mesuré : son système à 50 000 variables a atteint une erreur inférieure à 0,01
en une dizaine de secondes
(message 6913).
Deux propriétés rendent la relaxation véritablement utile, et pas seulement
rapide. Toute solution entière est aussi une solution fractionnaire, donc
l'optimum du LP est une borne : aucun plateau réel ne peut jamais marquer
plus que ne le dit la relaxation. Et les solveurs LP renvoient des certificats
(valeurs duales, preuves d'infaisabilité) que les méthodes sans variables
entières n'offrent pas. Toute la question est de savoir quelle part de cette
rapidité survit au retour vers les pièces entières.
Voici à quoi ressemble réellement l'optimum du LP, dans les mots de celui qui
l'a calculé. Le système de Benjamin « a convergé relativement vite vers une
erreur nulle » (un plateau parfait, autant que les contraintes pouvaient le
voir), et le coin supérieur gauche contenait « 30 % pièce 1, 20 % pièce 2,
10 % pièce 3, 40 % pièce 4 »
(message 6905). L'expérience
parallèle d'Andrew menait la même idée comme une ascension itérée sur une
grille de poids 256×256×4 : « chaque pièce est partout »
(message 6911).
La relaxation est satisfaite parce qu'une superposition peut se couvrir. Un
quart d'une pièce à arête bleue plus trois quarts d'une pièce à arête rose
présente un mélange qui correspond simultanément en partie à un voisin bleu et
à un voisin rose, une correspondance qu'aucun plateau physique ne peut
réaliser. Les contraintes linéaires savent tarifer quelle part de chaque pièce
se trouve où ; elles ne peuvent pas exprimer « exactement l'une de celles-ci
est réelle », car une-parmi n'est pas un fait linéaire. Il faut une
contrainte quadratique (ou une contrainte d'intégralité) pour le dire.
Benjamin a utilisé (∑vi)2−∑vi2=0, qui force toutes les
variables d'un groupe sauf une à zéro
(message 6913), et dès qu'il l'a
ajoutée, la convergence est morte : le système « stagne à des valeurs plus
élevées qui ressemblent à des résultats du type 420-440 / 480 arêtes
correctes » (message 6905).
Une théorie limpide sous-tend l'observation. Les deux familles d'affectation à
elles seules définissent un polytope dont tous les sommets sont entiers (c'est
Birkhoff–von Neumann, et c'est précisément pourquoi l'algorithme hongrois
résout l'affectation pure en temps polynomial). Ajoutez les contraintes de
joint et cette propriété d'intégralité est détruite : le polytope acquiert des
sommets fractionnaires, et l'optimum du LP se pose sur l'un d'eux. La
rétrospective de David Munjak comprime cela en une ligne, listant parmi ses
approches essayées « Problème d'affectation (solutions entières) » suivi de
« Problème d'affectation avec contraintes latérales (solutions pas
nécessairement entières) »
(message 8791). Les contraintes
latérales (les arêtes, le puzzle véritable) sont exactement ce qui brise la
garantie. Eternity II est un problème d'affectation facile soudé à un couplage
difficile, et la relaxation optimise discrètement la seule moitié facile.
Tous les quelques années, un nouveau venu empruntait la route, avec de
meilleurs solveurs et davantage de mémoire, et se heurtait aux trois mêmes
murs : la PLNE complète est insoluble au-delà des tailles jouets ; le LP est
soluble et fractionnaire ; arrondir ou contraindre vers l'intégralité
aboutit dans les 400 et quelques. Les campagnes, dans l'ordre :
| Année | Qui | Modèle | Où elle s'est arrêtée | Msg |
|---|
| 2007 | Günter Stertenbrink | Clique maximum, 262 144 sommets | Formulation seule ; jamais passée à l'échelle | 166, 627 |
| 2007 | dmitri_ulitski | PLNE (glpsol) sur des ensembles de rotations | Résolu en ~5 s par ensemble ; le sous-problème est facile | 3320 |
| 2008 | Vlasta | PLNE, 160 254 binaires | « Applicable seulement aux puzzles 8x8 » ; passé au SAT, atteint 428 | 5602 |
| 2008–09 | Andrew (bozmo2004) | Ascension continue, Newton–Raphson sur ~250k poids | ~800 000 jours projetés avec son prototype VBA | 5304, 6911 |
| 2009 | Benjamin (okifinoki) | LP, ~50 000 var., 7 952 contraintes | Erreur nulle en ~10 s, fractionnaire ; forcé entier : stagne à 420–440/480 | 6905, 6913 |
| 2009–10 | Jimmy Timmermans | Idéaux toriques ; BIP AMPL/CPLEX, 272 704 puis 153k var. | Limite de 32k variables de Singular ; un 12x12 « résolu » à 5,3 % d'infaisabilité (converge, pas l'intégralité) | 6716, 6728, 6745, 8077 |
| 2010 | Vlasta | MILP (164 256 booléens) converti en SAT | 8x8 en ~1 min ; à parité avec les retours arrière, sans aller plus loin | 7858 |
| 2008–10 | David Munjak | Affectation avec contraintes latérales, valeurs fractionnaires comme probabilités | 200–224 pièces placées, puis une impasse détectée ; jamais de retour arrière | 8791 |
| 2012 | Groupe Wauters | Hyper-heuristique (évaluée par les pairs) | 461/480 en une heure (la ligne académique) | 9023 |
| 2012 | Tony Wauters | MILP pour les ensembles de rotations | Millisecondes ; encore une fois, le sous-problème facile | 9071 |
| 2017 | Salassa, Vancroonenburg, Wauters et al. | Formulations MILP + clique maximum | « Computationnellement insoluble pour les instances de taille moyenne et grande » ; recyclées en décompositions heuristiques | 9683, arXiv |
| 2025 | Marcus Garvie | PLNE moderne | 10x10 à 6 couleurs en ~19 min ; l'E2 complet hors de portée | 11502 |
Trois lectures du tableau. D'abord, remarquez où la PLNE gagne : les
ensembles de rotations, où l'on fixe uniquement l'orientation de chaque pièce
de sorte que les comptes d'arêtes directionnels s'équilibrent, sont tombés
sous glpsol en cinq secondes en 2007 et sous CPLEX en quelques millisecondes
en 2012. Quand la structure entière est authentiquement facile, le solveur le
dit immédiatement ; le silence du puzzle complet est un verdict, pas un
problème d'outillage. Ensuite, les chiffres du plateau s'accordent à travers
des machineries totalement différentes : les 420–440 de Benjamin par LP
pénalisé, les 200–224 pièces placées sans faute de Munjak par affectation
itérée, les 461 du groupe Wauters avec une heure de réparation
métaheuristique par-dessus. Tout ce qui a une forme d'optimiseur atterrit dans
la même bande des 400 et quelques que la simple
recherche locale atteint
sans aucun LP. Enfin, l'article de 2017, le traitement académique le plus
solide, avec à la fois une formulation MILP et une formulation en clique
maximum, concède l'insolubilité dans son résumé et bascule vers l'usage des
formulations à l'intérieur d'heuristiques. Les bâtisseurs de la route
eux-mêmes ont posé le panneau de déviation.
Le versant « borne » de l'histoire a la même forme et vit sur le
registre des impasses : le plafond LP mesuré de ce
projet se situe autour de 478 alors que les meilleurs plateaux réels avoisinent
458, un écart bien trop large pour certifier quoi que ce soit, pour exactement
la raison de couverture fractionnaire évoquée plus haut.
- Le LP : polynomial, authentiquement rapide. Les méthodes de points
intérieurs résolvent les programmes linéaires en temps polynomial ; sur des
modèles de cette taille (50k–270k variables, de quelques milliers à quelques
centaines de milliers de contraintes), les solveurs modernes terminent en
quelques secondes à quelques minutes. C'est le seul objet authentiquement
bon marché de la page.
- La PLNE : NP-difficile, et pas dans l'abstrait. Le séparation-évaluation
est un retour arrière avec une borne LP à chaque nœud : exponentiel dans le
pire cas, et une instance
construite au pic de difficulté est conçue
pour réaliser ce pire cas. La forme mesurée du coût : un solveur qui gère le
8×8 (64 pièces) ne renvoie rien sur le 16×16, car l'arbre sous la racine est
élevé au carré, pas doublé.
- Le saut d'intégralité est la vraie monnaie. Toute la valeur de la
méthode est la distance entre l'optimum du LP et la meilleure solution
entière. Ici cette distance est d'environ 478 contre 458-et-ça-stagne : la
relaxation dépense son budget polynomial à répondre à une question sur un
puzzle différent, fractionnaire. Les plans coupants existent pour réduire cet
écart ; personne n'a rapporté de coupes qui en ferment ne serait-ce qu'une
entaille sur l'E2, et la structure par joint qui simule les correspondances
régénère le mou partout.
- Le séparation-évaluation élague avec la borne qu'il a. Un nœud n'est
coupé que lorsque sa borne LP tombe sous l'incumbent. Avec la borne qui
flotte à ~20 arêtes au-dessus de tout ce qui est réel, presque rien n'est
élagué : l'analogue exact des clauses apprises larges et inutiles dans
CDCL, la route d'à côté.
La conclusion juste est une relocalisation, pas un rejet, la même que celle que
la page SAT atteint pour le CDCL.
- Des bornes, énoncées avec leurs barres d'erreur. La relaxation est un
plafond valide, calculé en temps polynomial ; elle est simplement lâche ici.
L'entrée des impasses consigne le verdict pour
que personne ne le redémontre en espérant un certificat.
- Des sous-problèmes d'affectation, où l'intégralité est gratuite. Au sein
des boucles de réparation, recombler k trous deux à deux non adjacents est
un pur problème d'affectation k×k : polytope de Birkhoff, sommets
entiers, algorithme hongrois en O(k3). C'est le voisinage Eternity II de
Schaus, et c'est le seul endroit de ce wiki où la machinerie de l'optimiseur
tourne à pleine puissance : voir
recherche locale et ALNS.
- Des sous-problèmes entiers faciles, expédiés instantanément. Les
ensembles de rotations par MILP en quelques millisecondes
(message 9071) sont le motif :
quand une sous-question a une structure traitable, un solveur MIP est le
moyen fiable le plus rapide de la trancher, y compris de trancher que la
réponse n'aide pas.
- L'infaisabilité comme théorème. Une PLNE qui revient infaisable sur une
région épinglée prouve la même impossibilité qu'un appel SAT UNSAT : la
monnaie-certificat derrière le
mur de rigidité. Ce projet frappe ces
certificats avec le SAT, plus rapide sur cet encodage ; un solveur MIP est un
second atelier de frappe légitime, et le placeur de Munjak a utilisé
exactement ce signal, « identifiant un problème qui empêcherait le placement
des 256 pièces »
(message 8791).
- Des formulations comme générateurs de voisinages. La contribution
durable de l'article de 2017 est méthodologique : des méthodes constructives
fondées sur le MILP amorçant une recherche locale à voisinages multiples,
plus de nouvelles instances de référence difficiles pour la communauté
(arXiv:1709.00252). La formulation
survit comme une pièce, à l'intérieur d'une heuristique qui s'approprie le
problème d'intégralité au lieu de le relâcher.
La route de l'optimiseur, parcourue jusqu'au bout, enseigne un fait limpide sur
Eternity II : le puzzle est exactement la contrainte d'intégralité. Tout ce
qui est linéaire en lui, les flux, les équilibres, le squelette d'affectation,
est polynomial et a été résolu dès 2009, à erreur nulle, en dix secondes. Ce
qui reste, c'est l'exigence que chaque pièce soit quelque part, entière, une
fois. Le joyeux plateau fractionnaire de la relaxation est l'image la plus nette
que quiconque ait dessinée de ce à quoi ressemblent les 99 % faciles sans le
1 % difficile.