Eternity II 8


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 :

(cliquer sur l’image pour jouer à la version 4×4 en ligne)

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 :

  1. 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 !
  2. 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…
  3. 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 …
  4. 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)
  5. Il y a un code source en C++ ici
  6. 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 :

eternity2fr.png
On voit que, comme souvent dans ce genre de casse-tête, tout va bien presque jusqu’à la fin : ce sont les dernières pièces qui font la différence, et si on n’y arrive pas, c’est peut être les premières qui sont mal placées …
Un petit doute me tarabuste à propos d’Eternity2.fr : les anomalies cerclées de rouge : avec un vrai programme de backtracking, il ne devrait pas y avoir de pièce mal placée dans le puzzle. Peut-être est-ce un problème graphique, l’affichage étant partiellement désynchronisé …
Tetravex II a aussi une interface graphique et aborde le problème de manière identique, ligne par ligne. Je me demande si c’est judicieux car les pièces formant les bords sont connues, donc autant tenter de les placer le plus tôt possible, non ?
Je vais encore y réfléchir et peut-être me lancer dans un solveur moins “brute force”…

Références:

  • davidrempliderien

    Si non j’ai trouvé ça.. ça peut aider à piger.. http://www.cril.univ-artois.fr/~cardon/fichiers/rapportCuvillier.pdf

  • KidGramer

    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 …

  • couillandreau

    Je ne vois pas la complication de ce puzzle !!

  • 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