Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Eternity II

27 réponses
Avatar
JL
J'ai entendu parler de ce jeu ce soir sur BFM :
http://fr.eternityii.com/

Le principe est simple, il suffit d'assembler 256 carrés sur une grille
16x16 de manière à ce que les bords correspondent. Sauf que ça ne doit pas
être aussi simple, parce que celui qui y arrive avant fin 2010 gagne 2
millions de dollars !

J'ai testé leur version de démo en ligne à 4x4 cases sur
http://fr.eternityii.com/essayer-eternityii-en-ligne/ et en tâtonnant au
hasard sans aucune formalisation préalable j'ai fini par trouver en 15
minutes une solution (http://cjoint.com/?hBbaBZXnmZ pour les pressés). Cela
dit je n'ose même pas imaginer pouvoir y arriver comme ça avec la grille à
256 cases.

Une employée de l'éditeur était interviewée, et a indiqué qu'il y avait
20.000 solutions, et que seules 3 personnes au monde les connaissaient : le
mathématicien inventeur du jeu, et les 2 gagnants de Eternity I (je ne
connais pas la différence) avec qui il a mis au point cette 2e version. Et
que l'intérêt du jeu, c'est qu'il est _impossible_ de trouver la solution
par ordinateur.

À priori c'est un problème que l'on doit pouvoir résoudre par force brute,
sauf qu'en calculant rapidement j'arrive à un maximum de 256!x4^256
possibilités (256! pour le choix de chacune des 256 pièces sur une case,
avec à chaque fois 4 orientations possibles). En fait ça fait un peu moins
parce qu'il y a des pièces qui ne peuvent aller que dans les coins ou sur
les bords. Mais même avec ça, ça reste trop pour une bête attaque par force
brute en l'état actuel de l'informatique. Donc en comptant comme cela, la
fille semble avoir raison.

Mais en fait on sent bien qu'il y a moyen d'être un peu plus intelligent,
parce qu'une fois quelques pièces disposées, on voit vite que le nombre de
combinaisons compatibles diminue fortement. Donc j'aurais tendance à penser
qu'en l'état actuel des mathématiques et de la cryptographie, il doit bien y
avoir quelques chercheurs capables de trouver un aglorithme pour résoudre ça
avec un ordinateur pas trop futuriste.

Qu'en pensez-vous ? Quelle vous semble être la complexité du problème ?
Avez-vous déjà vu des études sur ce sujet ?

Ah, et pour finir, le jeu sort demain, au prix de 50 ¤. Je ne vais
certainement pas l'acheter, personnellement pour le prix je m'amuse beaucoup
plus avec un bon jeu sur PC, mais je trouve intéressant le concept d'essayer
de "casser" le jeu.

JL.

7 réponses

1 2 3
Avatar
William Dode
On 27-07-2007, ast wrote:

"JL" a écrit dans le message de news: 46a92e41$0$25337$

J'ai entendu parler de ce jeu ce soir sur BFM :
http://fr.eternityii.com/



Résolu en 4 mn 21 s
Qui fait mieux ?


74s... En python (langage de prog) ;-)

Je serait curieux que quelqu'un estime le nombre de coups possible pour
celui-là (16 pièces) pour comparer aux nombre de coups que le programme
a du tester avant de trouver.


--
William Dodé - http://flibuste.net
Développeur informatique indépendant


Avatar
Steph

74s... En python (langage de prog) ;-)


Pas mal, quel type d'algo ?

Avatar
William Dode
On 03-08-2007, Steph wrote:

74s... En python (langage de prog) ;-)


Pas mal, quel type d'algo ?


Je teste les combis collées aux précédentes, en espérant éliminer ainsi
pas mal de tests inutiles. Mais il n'est pas du tout optimisé...

Par contre j'avoue, j'ai eu un bol énorme, j'ai pris l'exemple donné sur
le site, hors il se trouve que c'est rapide avec l'ordre donné
uniquement, si je mélange les pièces avant de chercher ça devient hyper
long :-(

Maintenant il faudrait que je fasse une moyenne du nombre de tests
nécessaires afin de voir quelle différence ça fait par rapport aux
estimations et l'extrapoler pour 256 pièces. Mais il faut que je
l'optimise avant...

--
William Dodé - http://flibuste.net
Développeur informatique indépendant


Avatar
Free
"William Dode" a écrit

Je teste les combis collées aux précédentes, en espérant éliminer ainsi
pas mal de tests inutiles. Mais il n'est pas du tout optimisé...



C'est quoi une combi dans le puzzle ?


D'autre part je serais interesse par connaitre la structure de donnee
utilisee ;
tableau, liste, ou autre ?

Avatar
William Dode
On 04-08-2007, Free wrote:

"William Dode" a écrit

Je teste les combis collées aux précédentes, en espérant éliminer ainsi
pas mal de tests inutiles. Mais il n'est pas du tout optimisé...



C'est quoi une combi dans le puzzle ?


Une combinaison, un placement d'un certain nombre de pions



D'autre part je serais interesse par connaitre la structure de donnee
utilisee ;
tableau, liste, ou autre ?


J'ai fait vraiment au plus simple, pas du tout le plus rapide.

Un tableau 2d pour le damier et les pions dans une liste.
Avec une liste pour les pions à poser et une liste pour les pions déjà
posés.
Dès que je pose un pion je l'enlève de la première liste pour le mettre
dans la deuxième. Pour placer le pion suivant je parcours tous les pions
déjà posés et j'essaye de le mettre à côté, tant que ça marche je
continue, dès que ça ne marche plus j'essaye avec le pion suivant. Quand
ça ne marche plus du tout je déplace le pion précédent etc...

Mais comme l'indiquait vicnent, il y a peu de contrainte, je constate
que la moyenne avant échec est de 13 à 15 pions posés sur 16... Donc
c'est plutot catastrophique !

--
William Dodé - http://flibuste.net
Développeur informatique indépendant


Avatar
remy


Bien entendu, avec les motifs à raccorder, ça doit chuter.



a froid je pense un a un système récursive
en gros l'idee cree des blocs de plus en plus gros
et finir par les bords

histoire de limiter les rotations des pièces a l'interrieur de
blocs

il y a combien de motif différents ?

remy

Avatar
JL
"remy" a écrit dans le message de news:
f96obg$56j$

il y a combien de motif différents ?


22. Avec les bords gris, je suppose.

JL.

1 2 3