Eternity II est un puzzle spécialement étudié pour être extrêmement difficile, au point que son éditeur offre 2 millions de dollars au premier qui parviendra à placer correctement ses 256 pièces carrées de façon à ce que les côtés de chacune correspondent à ceux de ses 4 voisins, comme sur ce petit exemple avec 16 pièces seulement :
D’après l’éditeur, il existe 20’000 solutions au puzzle, et il nous « aide » en nous indiquant la position d’une pièce (la 139) , et fournit 2 indices de plus si l’on résout un puzzle 6×6 et un 12×6 avec des pièces indiquées dans la boite. Il n’est pas clair si ces indices (« hints » en anglais) facilitent réellement la résolution du puzzle, où s’ils servent à limiter le nombre de solutions admises comme victorieuses à beaucoup moins de 20’000, tout en rendant la programmation d’une solution informatique plus compliquée.
Mais avant d’attaquer la résolution informatique d’Eternity II, petit flash-back sur Eternity(I)
Eternity
En 19xx, un challenge similaire avait été posé pour le puzzle « Eternity » premier du nom, dans lequel il fallait disposer 209 pièces dans un dodécagone. 2 solutions ont été trouvée, la première en mai 2000 par Alex Selby et Oliver Riordon » et quelques ordinateurs », ce qui leur valut de se partager £1’000’000. Un mois plus tard, Guenter Stertenbrink a trouvé la seconde solution présentée ci-dessous:
A l’époque, Pierre-François avait programmé un logiciel de résolution du puzzle et l’avait rendu disponible sur le web à la condition de partager le prix avec lui si le programme permettait de trouver une solution. C’était une excellente idée, malheureusement il a du retirer son logiciel car il contenait la description des pièces du jeu, protégées par le copyright de l’éditeur …
Résolution informatique d’Eternity II
J’ai recensé plusieurs logiciels de résolution d’Eternity II, qui évitent tous ces problèmes de copyright en obligeant l’utilisateur à décrire lui-même les 256 pièces du jeu qu’il est censé avoir acheté au magasin :
- Eternity2.net était le plus ambitieux : basé sur BOINC , il permettait d’utiliser la puissance combinée de milliers d’ordinateurs. Le projet a été stoppé après quelques mois, officiellement par désespoir de trouver une solution avec un algorithme « brute force » et en raison des couts du serveur. Le code source de ce programme a été rendu disponible … sur leur serveur qui ne répond plus !
- Eternity2.fr est aussi un solveur distribué, et le site (en français) est plein d’informations utiles, avec également un forum très actif. Le logiciel que vous téléchargez après inscription sur le site se synchronise avec le serveur pour calculer des configurations qui n’ont pas encore été évaluées. Si une solution est trouvée, l’auteur du logiciel s’engage à vous verser la moitié des $2M…
- GPU Eternity est basé sur le « Global Processing Unit« , un client peer-to-peer Gnutella qui non seulement partage les fichiers, mais aussi le processeur…
Le code source en Delphi de ce projet est disponible, ce qui est intéressant pour voir comment il est fait … - Tetravex II est un shareware à $10 qui vous propose de garder les $2M pour vous tout seul, mais n’utilise qu’un seul processeur pour faire tourner un algorithme présenté comme mystérieusement exclusif, mais dont les résultats montrent qu’il est très « brute force » (voir ci-dessous)
- Il y a un code source en C++ ici
- et un en Java ici. (lien restauré le 19.3.2015)
Algorithmes utilisés
Tous ces programmes utilisent faute de mieux un approche « brute force » : on place des pièces correspondantes les unes à côté des autres jusqu’à ce qu’on ne puisse plus le faire, puis on fait du « backtracking » en enlevant la dernière pièce et en essayant d’en mettre une autre qui permette de continuer, et si on n’y arrive pas on enlève encore la pièce précédente etc. La complexité de cet algorithme est monstrueuse : la probabilité de trouver une solution de cette manière en une année est très faible.
Eternity2.fr annnonce une performance de son algorithme de 15’000’000 de pièces disposées / seconde ! Une option permet de visualiser son fonctionnement dans une fenêtre graphique bougeant à toute vitesse. Une capture donne ceci :
11 commentaires sur “Eternity II”
Si ce genre de défis vous intéresse,
je vous conseille le 2048, que certains connaissent probablement déjà: https://play2048.co/
Si non j’ai trouvé ça.. ça peut aider à piger.. http://www.cril.univ-artois.fr/~cardon/fichiers/rapportCuvillier.pdf
Salut, le lien pour avoir le code source du jeu en java ne fonctionne plus. Est ce que je pourrais l’avoir svp ?
J’ai googlé « eternity 2 solver java » à votre place pour restaurer le lien 😉
Par pure coïncidence je suis en train d’écrire un article sur le problème SAT qui permet (en théorie) de résoudre ce type de problèmes de manière beaucoup plus efficace. Si je devais attaquer Eternity 2 aujourd’hui, j’utiliserais cette approche.
D’ailleurs… une petite recherche… et hop ! quelqu’un l’a déjà fait : http://www.st.ewi.tudelft.nl/~marijn/publications/eternity.pdf mais il ne s’en est pas sorti …
Bonsoir… ce jeu est-il toujours d’actualité ? Ou clos ?
Clos
Je ne vois pas la complication de ce puzzle !!
alors c’est que vous n’avez pas essayé… Il y a 256 pièces, et chacune peut être tournée de 4 façons, ça fait un nombre phénoménal de combinaisons possibles. J’ai trouvé ce document http://www.ludovicpatey.com/media/research/patey-e2-rapport.pdf qui analyse mathématiquement ce jeu.
Un premier article sur le dénombrement des combinaisons possible pour la résolution d’Eternity II ici :
http://eternity2blogger.over-blog.com/article-31823498.html
Cet article sera suivi de nombreux articles pour affiner ce dénombrement et réduire le nombre de solutions possibles en fonction des contraintes du jeu (coins, bordures, pièces fixes, nombre de motifs différents, répartition des motifs, etc..)
A vos machines ! 🙂
Pour info, aucune solution n’a été trouvée pour l’instant. Un prix de $10’000 a récompensé une solution partielle de 267 correspondances sur 280, obtenue par l’épouse de « Louis », qui collabore au site Eternity2.fr
Bonjour, je vous propose de voir quelques captures, non actuelles, mais qui présentent bien mon projet. Cordialement Guillaume