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.
Tiens, un peu de pub : j'ai écrit sur ce genre de questions une page que j'aime bien : http://denis.feldmann.club.fr/grands.htm
que j'aime bien ausi...
;-)
Vicnent
Vicnent
Serge Paccalin wrote:
Je ne trouve que 256! possibilités si les pièces sont indifférenciées, et 3!×56!×196! si on distingue les coins et les bords comme sur la version d'essai à 16 pièces.
pour ma part, je dirais qu'il y a 256! pour la répartition des pièces, et 4 rotations par pièce. ce qui fait 3 10^500 (à la louche hein...)
maintenant, si dans le grand jeu, les pièces contenant du gris sont sur les bords, il y a 60 pièces dont 4 coins ce qui fait moins : 56!*4*(256-60)! = 10^400 en gros.
bref, de toute façon, comme il est indiqué, avec un jeu de 256 pièces, il est très aisé de construire des bouts de puzzle valides de 200 pièces... mais la backtracking va faire mal...
Bref, je l'achéterai je pense et verrai pour faire tourner un programme... il y a probablement quelques heuristiques à mettre en place (j'en ai qq unes déjà en tête) et d'autres choses... (mais clairement, celui qui le développe en force brute, il a le temps d'aller boire qq bières...)
-- Vicnent
Serge Paccalin wrote:
Je ne trouve que 256! possibilités si les pièces sont indifférenciées,
et 3!×56!×196! si on distingue les coins et les bords comme sur la
version d'essai à 16 pièces.
pour ma part, je dirais qu'il y a 256! pour la répartition des pièces, et 4
rotations par pièce.
ce qui fait 3 10^500 (à la louche hein...)
maintenant, si dans le grand jeu, les pièces contenant du gris sont sur les
bords, il y a 60 pièces dont 4 coins
ce qui fait moins : 56!*4*(256-60)! = 10^400 en gros.
bref, de toute façon, comme il est indiqué, avec un jeu de 256 pièces, il
est très aisé de construire des bouts de puzzle valides de 200 pièces...
mais la backtracking va faire mal...
Bref, je l'achéterai je pense et verrai pour faire tourner un programme...
il y a probablement quelques heuristiques à mettre en place (j'en ai qq unes
déjà en tête) et d'autres choses... (mais clairement, celui qui le développe
en force brute, il a le temps d'aller boire qq bières...)
Je ne trouve que 256! possibilités si les pièces sont indifférenciées, et 3!×56!×196! si on distingue les coins et les bords comme sur la version d'essai à 16 pièces.
pour ma part, je dirais qu'il y a 256! pour la répartition des pièces, et 4 rotations par pièce. ce qui fait 3 10^500 (à la louche hein...)
maintenant, si dans le grand jeu, les pièces contenant du gris sont sur les bords, il y a 60 pièces dont 4 coins ce qui fait moins : 56!*4*(256-60)! = 10^400 en gros.
bref, de toute façon, comme il est indiqué, avec un jeu de 256 pièces, il est très aisé de construire des bouts de puzzle valides de 200 pièces... mais la backtracking va faire mal...
Bref, je l'achéterai je pense et verrai pour faire tourner un programme... il y a probablement quelques heuristiques à mettre en place (j'en ai qq unes déjà en tête) et d'autres choses... (mais clairement, celui qui le développe en force brute, il a le temps d'aller boire qq bières...)
-- Vicnent
Olivier Miakinen
pour ma part, je dirais qu'il y a 256! pour la r閜artition des pi鑓es, et 4 rotations par pi鑓e. ce qui fait 3 10^500 (� la louche hein...)
Ah ? Voyons les entêtes :
X-Newsreader: Microsoft Outlook Express 6.00.2900.2180 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-RFC2646: Format=Flowed; Original
D'accord, c'est un Outlook Express avec configuration d'origine, qui n'indique donc pas le jeu de caractères utilisé. Mon SeaMonkey arrive à deviner juste la plupart du temps, mais parfois il se trompe et ce n'est pas de sa faute.
Voir par exemple <http://groups.google.fr/group/fr.usenet.8bits/msg/ad678b47a7f77c6e>.
[ copie et suivi sur fr.usenet.8bits ]
pour ma part, je dirais qu'il y a 256! pour la r閜artition des pi鑓es, et 4
rotations par pi鑓e.
ce qui fait 3 10^500 (� la louche hein...)
Ah ? Voyons les entêtes :
X-Newsreader: Microsoft Outlook Express 6.00.2900.2180
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180
X-RFC2646: Format=Flowed; Original
D'accord, c'est un Outlook Express avec configuration d'origine, qui
n'indique donc pas le jeu de caractères utilisé. Mon SeaMonkey arrive
à deviner juste la plupart du temps, mais parfois il se trompe et ce
n'est pas de sa faute.
Voir par exemple
<http://groups.google.fr/group/fr.usenet.8bits/msg/ad678b47a7f77c6e>.
pour ma part, je dirais qu'il y a 256! pour la r閜artition des pi鑓es, et 4 rotations par pi鑓e. ce qui fait 3 10^500 (� la louche hein...)
Ah ? Voyons les entêtes :
X-Newsreader: Microsoft Outlook Express 6.00.2900.2180 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-RFC2646: Format=Flowed; Original
D'accord, c'est un Outlook Express avec configuration d'origine, qui n'indique donc pas le jeu de caractères utilisé. Mon SeaMonkey arrive à deviner juste la plupart du temps, mais parfois il se trompe et ce n'est pas de sa faute.
Voir par exemple <http://groups.google.fr/group/fr.usenet.8bits/msg/ad678b47a7f77c6e>.
j'ai posté mon premier essai, dès le 3ième j'étais à la minute ou en dessous ... mais arretons-là ce concours pré-pubert cela ne me passionne guère.
Sylvain.
Free
"JL" a écrit dans le message de news:
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.
Comme ca, a premiere vue, l'idee naturelle qui vient serait de trouver une representation du puzzle (un graphe, un autre type de carre, etc) qui faciliterait la resolution sur ordinateur ...
Ce qui suppose peut etre de se pencher sur les aspects mathematiques de l'enigme ?
Evidemment on peut envisager de le faire a la main en mettant au point une methode ou des astuces mais ca parait quand meme plus dur que de faire tourner une machine en backtracking ou avec des algorithmes de recherche classique
Ma reflexion ne fait guere avancer le Schmilblick mais c'est la premiere idee qui me vient a l'esprit en voyant le puzzle
Cela dit avec 2 M$ en jeu je ne sais pas si le trouveur d'un debut de piste partagera son idee ...
"JL" <JL@jlamy.com> a écrit dans le message de news:
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.
Comme ca, a premiere vue, l'idee naturelle qui vient serait de trouver une
representation
du puzzle (un graphe, un autre type de carre, etc) qui faciliterait la
resolution sur ordinateur ...
Ce qui suppose peut etre de se pencher sur les aspects mathematiques de
l'enigme ?
Evidemment on peut envisager de le faire a la main en mettant au point une
methode ou
des astuces mais ca parait quand meme plus dur que de faire tourner une
machine
en backtracking ou avec des algorithmes de recherche classique
Ma reflexion ne fait guere avancer le Schmilblick mais c'est la premiere
idee qui me
vient a l'esprit en voyant le puzzle
Cela dit avec 2 M$ en jeu je ne sais pas si le trouveur d'un debut de piste
partagera son idee ...
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.
Comme ca, a premiere vue, l'idee naturelle qui vient serait de trouver une representation du puzzle (un graphe, un autre type de carre, etc) qui faciliterait la resolution sur ordinateur ...
Ce qui suppose peut etre de se pencher sur les aspects mathematiques de l'enigme ?
Evidemment on peut envisager de le faire a la main en mettant au point une methode ou des astuces mais ca parait quand meme plus dur que de faire tourner une machine en backtracking ou avec des algorithmes de recherche classique
Ma reflexion ne fait guere avancer le Schmilblick mais c'est la premiere idee qui me vient a l'esprit en voyant le puzzle
Cela dit avec 2 M$ en jeu je ne sais pas si le trouveur d'un debut de piste partagera son idee ...
bus.error
Cela dit avec 2 M$ en jeu je ne sais pas si le trouveur d'un debut de piste partagera son idee ...
Plutôt pas intérêt !
"Pour protéger les joueurs, ils disqualifieront aussi toute grille de réponse ayant été rendue publique avant la date du dépouillement annuel suivant son inscription, et toute personne ayant dévoilé publiquement des détails concernant des pièces dETERNITY II sous quelque forme et par le biais de quelque media que ce soit."
Le but est de vendre des puzzles.
Cela dit avec 2 M$ en jeu je ne sais pas si le trouveur d'un debut de piste
partagera son idee ...
Plutôt pas intérêt !
"Pour protéger les joueurs, ils disqualifieront aussi toute grille de
réponse ayant été rendue publique avant la date du dépouillement annuel
suivant son inscription, et toute personne ayant dévoilé publiquement
des détails concernant des pièces dETERNITY II sous quelque forme et
par le biais de quelque media que ce soit."
Cela dit avec 2 M$ en jeu je ne sais pas si le trouveur d'un debut de piste partagera son idee ...
Plutôt pas intérêt !
"Pour protéger les joueurs, ils disqualifieront aussi toute grille de réponse ayant été rendue publique avant la date du dépouillement annuel suivant son inscription, et toute personne ayant dévoilé publiquement des détails concernant des pièces dETERNITY II sous quelque forme et par le biais de quelque media que ce soit."
