NintendojoFR : Le forum

Z'êtes pas trop Pokémon vous sur ce forum, si ?

Il me le faut.

Bon, je vais programmer un solveur pour ce jeu, la seule chose qu'il va me falloir c'est un bon ordi, j'imagine déjà les Stack overflows dès les calculs dans un arbre de profondeur 100...

Je vais faire tourner les ordis de mon labo la nuit je pense.

Urd a écrit :un bon ordi

Il existe des milliers de combinaisons gagnantes possibles, mais aucune machine ou aucun ordinateur ne saurait les résoudre car le codage de l'énigme invoque la mathématique des nombres complexes, l'analyse combinatoire, la théorie des probabilités, mais aussi et surtout la théorie des pavages dits quasi périodiques, dont l'un des grands découvreurs, Roger Penrose, n'a jeté les fondements qu'en 1974.

Pour mettre au point Eternity II, il a fallu avoir recours à la physique des quasi-cristaux, mais aussi à la statistique et aux mathématiques dites "discrètes" dont le succès tient à leurs applications dans la sphère informatique. Jusqu'au dernier moment et au dernier placement de la 256e pièce, nul ne pourra dire s'il est proche ou loin de la solution.

Chauuuuud Mais qui ne tente rien n'a rien

Ca se trouve on y arrivera totalement par hasard Y en a bien qui gagnent au loto

j'ai réussi leur démo 16 pieces en 2 minutes 19, youpi !

$poke a écrit :Vous avez deja acheté des billets d'avions sur Expedia.fr ????
Parce que j'ai acheté mes billets hier soir et j'ai reçu un mail confirmant une reservation mais pas de justificatif à présenter dans les zones d'enregistremnt.

j'aimerai donc bien savoir comment ça se passe chez eux ^^

Et bien si c'est un billet electronique comme pour air france, tu te présentes à l'enregistrement avec une pièce d'identité. Passe un coup de fil à la compagnie aérienne si tu as un doute, mais bon ça c'était passé comme ça pour mon dernier voyage.

The_lascar a écrit :

gné a écrit :c'est une image de ciel bleu sans nuage ?

edit: ptain c'est trop bon ce truc en fait

sa coute combien?

49,98 €

Donc ils vendent un jeu que quasi personne ne peut résoudre (le quasi semble de trop vu la description).

Faut être un pigeon pour acheter ça 50euros alors. C'est comme acheter un coffre fort que tu ne peux pas ouvrir.

Personnellement, ça ne me paraît pas difficile à coder, surtout qu'à part la physique des quasi-cristaux dont je n'avais jamais entendu parler avant hier, c'est exactement ce que j'étudie. Je viens d'écrire un brouillon approximatif permettant de le résoudre en moins de 50 lignes. C'est juste comme je disais, un problème de puissance de calculs, car travailler dans un arbre de profondeur 256 (sachant que l'espace demandé croît exponentiellement avec la profondeur de l'arbre), je ne vois pas quel ordi peut le faire (oui Bust, je savais que c'était impossible ).

J'imagine bien que le problème est d'optimiser le code pour que l'on arrive à traiter un cas de 256 cases

Il faudra que j'en parle avec un de mes profs spécialiste du domaine que je croise souvent.

Ca ferait un excellent sujet de thèse si personne ne l'a résolu avant l'année prochaine.

Bonne vacances a tout le monde
De retour en septembre .

bisous.

TONTON Nicky

Tu vas où ?

(DTC Shield)

Tonton Nicky part 3 secondes apres avoir écrit un message d'au revoir, c'est la classe Tonton Nicky ! Il ne te répondra donc qu'en septembre ...

Je pense aussi, mais j'ai demandé quand même, on sait jamais.

D'ailleurs, si il ne répond pas là, il ne répondra pas en septembre non plus . (En plus on est sur le Vous avez des choses à dire ? ^^'.)

bah si i lrepondra.
Il fera un "ouaaaa trop bon les vacances a XXXX tkt tro dla balle champ a gogo"

En effet .

The_lascar a écrit :Aujourd'hui on a reçu un puzzle assez spécial, de 256 pièces, qui a la particularité d'être très dur D'ailleurs le premier qui arrive à le finir gagne 2 millions $
Edit : c'est sur Wikipedia d'ailleurs.

Je suis sur qu'informatiquement on peut trouver la solution rapidement !

Ben c'est ce que Urd répète depuis quelques posts non ?

Non, lui parle de le faire rapidement alors que je vois une complexité de l'ordre de n!, même en limitant l'algo, je vois une complexité de l'ordre de 196! Ce qui signifie quelques milliards de milliards de milliards d'opérations.

A moins d'être chanceux et de tomber dès les premiers coups sur la solution, il y a quand même pas mal de configurations possibles à vérifier.

La seule façon avec laquelle je vois de résoudre le problème est d'utiliser les CSP (Constraint Satisfaction Problem) et donc d'utiliser un langage spécifique à ce genre de problèmes. Mais Cyrare est sûrement plus qualifié que moi dans le domaine.

edit : on peut certes noter la redondance des pièces (plusieurs pièces peuvent être identiques) et le fait qu'on puisse obtenir la solution du carré par rotation de toutes les pièces, mais cela reste quand même peu significatif.

Ca à l'air roxooor ce puzzle

KFC c'est bon

Urd a écrit :Non, lui parle de le faire rapidement alors que je vois une complexité de l'ordre de n!, même en limitant l'algo, je vois une complexité de l'ordre de 196! Ce qui signifie quelques milliards de milliards de milliards d'opérations.

A moins d'être chanceux et de tomber dès les premiers coups sur la solution, il y a quand même pas mal de configurations possibles à vérifier.

La seule façon avec laquelle je vois de résoudre le problème est d'utiliser les CSP (Constraint Satisfaction Problem) et donc d'utiliser un langage spécifique à ce genre de problèmes. Mais Cyrare est sûrement plus qualifié que moi dans le domaine.

edit : on peut certes noter la redondance des pièces (plusieurs pièces peuvent être identiques) et le fait qu'on puisse obtenir la solution du carré par rotation de toutes les pièces, mais cela reste quand même peu significatif.

Ouais, mais sur toutes ces solutions, tu en as un max qui sont refusées direct sur un simple test...
Je suis pas un dieu de ce genre de truc, loin de là, mais ne peut-on pas imaginer réussir à faire des assemblages petits par petits, genre identifier chaque pièce, et laisser penser que la pièce x, ne peut en avoir à sa droite que n pièces correspondant à la bonne couleur ?

C'est comme le petit programme de résolution de picross que j'ai fait, des 15x15, ça donne pas mal de solutions, mais finalement, on est loin de toutes les faire, c'est juste un simple raisonnement.

Ca me rappelle un des tout premiers programmes dans le genre que j'avais fait en qbasic ! C'était la résolution d'un jeu qu'on faisait en cours quand on se faisait chier. ça réussissait les petites surface, mais ça devenait tout de suite plus long avec les plus grosses.

Le problème, c'est que tout est directement lié. Comme le disait un article de je sais plus quel site, tant que tu n'as pas fini le puzzle, tu ne peux pas savoir si tu es proche où non du but, même avec les 3 quarts des pièces posées, si ça se trouve tu vas te rendre compte que ta configuration actuelle est impossible.

Justement, c'est là tout l'intérêt de l'informatique, là où c'est complètement desespérant pour un humain, un programme lui, il s'en branler, il change un truc et recommence, d'autant qu'il n'a perdu que quelques secondes.

Cyrare a écrit :Ouais, mais sur toutes ces solutions, tu en as un max qui sont refusées direct sur un simple test...

Pour faire simple et donner une échelle de la complexité du problème :

Pour une pièce du milieu, on n'a que 3 couleurs possibles sur les côtés. Si l'on compte qu'une même pièce tournée 4 fois donne 4 pièces différentes, on se retrouve avec environ une centaine de pièces différentes.
Si l'on procède par la méthode classique (assemblage petits par petits), à chaque nouveau placement, une pièce n'a besoin de vérifier que 2 conditions (si on les assemble de la gauche vers la droite, et du haut vers le bas, alors chaque pièce doit avoir la même couleur du haut que la pièce du haut et la même couleur de gauche que la pièce de gauche), on peut donc se retrouver avec 9 pièces possibles par case (explication : si une pièce est représentée par la séquence a,b,c,d où a représente la couleur de gauche et b la couleur du haut alors c et d peuvent avoir 3 valeurs chacune, soit 3x3=9), à condition qu'elles soient toutes dans la base (sinon tu ne prends qu'autant de pièces, qu'il y a dans la base, qui vérifient les 2 conditions citées, c'est-à-dire un nombre inférieur à 9. Plus on avance dans les cases traitées, plus ce nombre diminue car les pièces ont été placées). Ce qui signifie rien que pour le carré 14x14 du milieu, une estimation très grossière (car c'est complètement faux) de 9^196 configurations possibles. Pour une estimation plus correcte (mais toujours grossière), pour les 100 premières cases traitées, tu as environ 9^100 configurations possibles.

Si tu arrives à traiter ça d'une manière rapide alors fais-moi savoir comment, ça m'aidera pour l'an prochain.

Ouais, mais là, tu réfléchis comme si le puzzle avait un sens, hors le motif n'en a pas. Il y a donc 4 solutions exactes.

La première pièce que tu poses est forcément exacte finalement, si tu ne te bornes pas à la placer de manière absolue.

Donc si on essaye de faire des blocs de 4 qui s'assemblent, bien, ça réduit considérabement le nombre de tests à faire.

D'autre part, si c'est comme la démo, avec des bords gris, il pourrait être intéressant de voir le nombre de possibilités réalistes pour assembler juste le bord.