posté le 30/07/2007 à 12h30
Mise à jour :
  • Suite à la publication de ce billet, j'ai ouvert le site Eternity2.fr.
  • Si vous cherchez à vous procurer le jeu, je vous invite à le commander sur Amazon :

Le puzzle de base

Le puzzle indice n°1

Le puzzle indice n°2




Billet original :

La semaine dernière, Skorn m'a transmis un article du journal Le Monde sur Eternity II.
Il s'agit d'un puzzle dont vous pouvez essayer la démo sur le site officiel.
Le vrai puzzle, lui, est beaucoup plus grand car il fait 16 x 16 cases, et une prime est offerte à celui qui trouvera la (ou une) solution.
Forcément, la tentation est grande de faire un programme pour résoudre le problème de façon informatique.
C'est d'ailleurs comme ça que le premier Eternity a été résolu. Le problème était d'ailleurs plus compliqué à modéliser comme il s'agissait de pièces géométriques compliquées et non pas de simple carrés.
J'ai écris un premier algorithme récursif "brute force" qui trouve très rapidement les 2560 solutions du puzzle de test 4x4 (oui, il y a bien 2560 solutions en comptant les rotations shocked ).

En cherchant un peu plus j'ai trouvé plusieurs sites déjà actifs autour du projet (alors que le puzzle n'était pas encore sorti).
Par exemple Eternity2.net est un projet de calcul distribué utilisant la plate-forme BOINC pour résoudre le problème.
Il y a aussi un groupe Yahoo sur le puzzle qui est très actif. Je me suis donc inscrit dessus, et j'ai pu obtenir plein d'informations utiles, des petits programmes bien pratiques et des benchmarks pour comparer les performances des différents algorithmes.

Ce week-end le puzzle est sorti, donc je me suis acheté une boite à Toys"R"Us, ce qui est indispensable pour avoir les "vrais" pièces du jeu.



En ouvrant la boite on trouve les pièces à découper et le plateau de jeu :



Je préfère flouter l'image car il est interdit de diffuser les pièces du jeu.

Ca m'a pris un peu de temps pour saisir les 256 pièces du jeu afin de les importer dans mon programme laugh
Et il me reste encore du boulot pour avoir un algorithme efficace...

Si j'ai un peu de temps, j'essayerai aussi de faire un petit projet de calcul distribué... j'ai déjà le nom de domaine qui va bien !
Et qui sais, peut-être que dans quelques siècles j'aurai trouvé la solution tongue

Commentaires

Pseudo :
Message :
(pas de HTML)

cojo12 [ 05/01 - 17:43 ] : bonjour j'ai achete le puzzle j'ai visiter ton site mais je ne comprends rien en info ni en programmation y a t-il un endroit ou je peut telecharger le programme car je comprends vraiment rien a vos discutions et je suis perdus et bloquee en plus
merci pour la reponse


Bouffre [ 16/09 - 23:27 ] : et si à la place des images pièces pour la desciption on met des lettres genres RG,GH, etc... il y a violation de la diffusion?

Royale [ 02/08 - 12:15 ] : Pour info, j'ai ouvert le site http://www.eternity2.fr/

Royale [ 02/08 - 00:13 ] : Ca avance, ça avance...

docj [ 01/08 - 17:25 ] : va y royale oune les tous !

Nono [ 01/08 - 10:23 ] : Halala si toute cette énergie était utilisée pour des logiciels libres ;-P

Royale [ 31/07 - 00:14 ] : D'ailleurs je viens de trouver où mon programme perdait beaucoup de temps \o/

Royale [ 30/07 - 22:57 ] : C'est sûr j'ai de la marge sur l'algo...
Pour l'instant c'est du backtracking basique.

Nono [ 30/07 - 21:21 ] : Dans ce genre de problème, l'architecture du logiciel et les algo doivent être bien plus important que les optimisations de compilo.

Royale [ 30/07 - 14:08 ] : Pour l'instant je suis parti sur un client en C, que j'essaye de bichonner au maximum, et que je compile avec les optimisations... mais je suis encore loin des performances de certains !

Nono [ 30/07 - 12:46 ] : L'occasion de faire un peu de Java, avec Hadoop ( http://wiki.apache.org/lucene-hadoop/ProjectDescription, http://wiki.apache.org/lucene-hadoop/PoweredBy )

Infos TiBlog

Pseudo : Royale
Titre : Le blog de Royale
Description : Le blog de l'administrateur de TiBlog.fr où vous trouverez quelques détails techniques sur le fonctionnement de ce site.

Créer un blog !

blog gratuit

Recherche

Photo