Eternity II

Amis des énigmes encore non résolues, bonjour !

AMIS floodeurs, svp pas ici.

Spoiler:

Certains d'entre vous ont peut-être déjà entendu parler d'Eternity :
C'est un puzzle casse-tête, créé par Christopher Monckton en 1999. Celui-ci offrait lors du lancement un million de livres sterling à celui qui arriverait à résoudre son puzzle de 205 pièces.
Une équipe d'étudiants a trouvé la solution en 5-7 mois :

Spoiler:

Ces mêmes étudiants ont ensuite été employés pour créer avec lui THE puzzle : ETERNITY II (à ceux que le nom étonneront, je réponds pourquoi pas, Chuck Norris a bien compté jusqu'à l'infini... 2 fois.)
Il parait que c'est un problème NP-complet ou un machin du genre, selon un pote qu'a fait des études et tout et tout, bon, ok, super, mais ça m'avance pas beaucoup. Il parait aussi que c'est super super chaud de trouver une solution, mais il n'a pas réussi à me décourager, la preuve, j'suis toujours là.

Eternity II, lancé en 2007, 2 millions de dollars à la clé lors du lancement, toujours non résolu.
La récompense n'était valable que jusqu'en 2009, il ne reste "plus que" le sport.

Mais je suis curieux de voir ce que quelques Z motivés pourraient être capables de faire...
Je lance donc un appel aux informaticiens, mathématiciens, logiciens et (T) HQI (+ étoile) de tous horizons, qui seraient motivés pour relever le défi, à me rejoindre. (sans non plus s'y mettre tous les jours, gardons une vie )

Eternity II est donc un puzzle carré de 256 pièces (16*16).
Il y a des droits sur les images du puzzle et des pièces et je ne me permettrais donc pas d'en poster une photo;
Voici ici une illustration simplifiée du principe du puzzle :

Spoiler:

Le vrai puzzle est donc de 16*16, comme déjà dit, et de mémoire compte 17 motifs différents. Vous pouvez certainement trouver une image en cherchant sur google.

Le nombre de possibilités de placement et d'orientation des pièces ayant plus de 600 zéros (en système décimal, précisons...), on estime que pour le résoudre par la force brute (essayer toutes les possibilités), il faudrait toute la puissance informatique mondiale pendant 2 fois l'âge de l'univers (j'ai pas vérifié les "il parait", hein).
Des centaines de milliers de personnes ont essayé de le résoudre, autant d'ordinateurs utilisant de nombreux algorithmes différents (backtracking, etc) ont cherché une solution, sans succès.

Il y a quelques années, j'y avais passé pas mal de temps pendant une-deux semaines et vous présente ici mon angle d'attaque de l'époque, approximativement puisque j'ai depuis perdu toutes les données relatives à ça...

Je cherchais avant d'essayer de les placer à "orienter" les pièces (4 orientations possibles pour chacune).
En partant d'une constatation simple : puisque les motifs doivent s'assembler entre eux, chacun doit, sur l'ensemble de toutes les pièces, être présent autant de fois vers la gauche que vers la droite, et vers le haut que vers le bas.
J'avais défini pour chaque motif une lettre, puis représenté la pièce orientée par ABCD, par exemple, avec A en haut, B à droite, C en bas, D à gauche.
J'avais donc entré la liste de toutes les pièces sous excel, une pièce par ligne et un motif par colonne.

Le but était donc de trouver des orientations de pièces telles qu'il y ait autant de B, C, D etc dans la 1ère colonne que dans la 3ème, autant dans la 2nde que dans la 4ème.
Ayant défini A comme le motif "côté", je pouvais ajouter à cela qu'il fallait 16 A vers le haut, vers le bas, vers la gauche et vers la droite.
De plus, il fallait que les coins soient orientés différemment.
J'ai donc défini l'erreur A et lui ai donné un coefficient légèrement supérieur aux autres motifs (mais pas une priorité absolue pour ne pas restreindre l'exploration)

J'avais donc créé une "case" pour chaque motif qui calculait "l'erreur", définie par la valeur absolue de (nombre de motif X dans colonne 1 - nombre de X dans colonne 3) ajoutée à la valeur absolue de (nombre de X dans colonne 2 - nombre de X dans colonne 4).
Si l'erreur était de 0 pour un motif, celui ci était donc autant à gauche qu'à droite et autant en haut qu'en bas.

J'espère que je suis clair pour l'instant...

Je cherchais un moyen de trouver rapidement des solutions à ce problème d'orientations sans utiliser la force brute, insuffisante.

Avec un peu d'aide de mon père, n'y connaissant rien ou presque en programmation, j'avais fait un algo qui, pièce après pièce, cherchait à optimiser sa position par rapport à "l'erreur globale" (total des erreurs pour tous les motifs).
J'avais commencé par chercher à diminuer le total des erreurs coûte que coûte; en vain, très rapidement cela "bloquait" et plus aucune modification ne se faisait.

J'ai essayé ensuite de diminuer à chaque fois l'erreur du motif qui en comptait le plus : même chose, blocage au bout d'un certain temps.

J'avais alors bricolé une fonction polynomiale pour calculer "l'erreur globale" dont je suis pour l'instant incapable de me rappeler la forme exacte.
Je l'avais bricolée à l'instinct uniquement, mes connaissances en maths s'arrêtant en terminale (et encore).
Les carrés et autres exposants permettaient, entre autres (je ne me rappelle plus de toooutt ), de favoriser la diminution des erreurs des motifs en ayant le plus, mais sans tout de même créer trop d'erreurs supplémentaires pour les autres.
J'avais ajouté dans une très faible mesure une part de hasard dans les choix pour éviter les blocages, et, quand l'algo bloquait tout de même, une modification de l'orientation de 4 pièces au hasard.

Cette fonction et cet algo me permettait de rechercher une solution dans "l'ensemble des presque solutions", car l'erreur globale restait, autant que possible, proche de zéro.

Avec succès après quelques bricolages supplémentaires : à chaque fois que je lançais l'algo final en partant d'orientations aléatoires, je trouvais en quelques minutes à peine une solution (avec un vieil ordi tout pourri)
J'ai essayé, pour plusieurs de ces solutions (une 30aine), de les placer, sans succès.

Cette manière de faire ne permet pas, je pense, de trouver directement une solution au puzzle.

Mais, par rapport à l'angle d'attaque, je voudrais essayer quelque chose :
Représenter, avec orientation et placement, toutes les pièces dans un tableau, puis définir comme "erreur" chaque motif assemblé à un motif différent.
Puis, avec l'aide d'un algo et une fonction polynomiale à définir, à essayer de réduire l'erreur globale comme je l'avais déjà fait, en échangeant et orientant les pièces pour tendre vers le moins d'erreur possibles.

C'est à dire chercher une solution dans l'ensemble des "presque solutions", plus ou moins de la même manière.

Motivés ?

Bon, tant pis.

j'avoue que euh j'visualise pas le truc là ^^

bon j'ai vu sur le net.... beh a moins d'avoir le puzzle j'peux pas t'aider ^^ (moi j'suis nulle en calculs etc faut que "je vois" la bête)

sorry ^^

Preneur pour pousser l'analyse avec toi Tof

J'avais trouvé la solution à l'époque.

Mais ... étant uniquement mû par l'amour de la science et le goût du défi, et non par ces histoires d'argent et de jeux du cirque, j'ai préféré la garder pour moi.

Et c'est ce que je vais à nouveau faire, au cas où la récompense serait à nouveau proposée : garder la solution pour moi.

Dieu vous garde.

(lol Phiphi)
(no pb Clemelle, mais je n'ai pas le jeu moi-même, il est à ma môman...)

Ok , Mjöllnir, on en parle un de ces 4

Je vais refaire la liste des pièces au plus vite, après avoir vérifié qu'il n'en reste pas une trace sur l'ordi de mes parents, je leur demande.

Il semblerait que réussir à résoudre ce type de puzzle serait une avancée mathématique conséquente qui pourrait servir dans de nombreux domaines.
D'où la difficulté, d'où le challenge (et l'intérêt), d'où la gloire éternelle en cas de succès.
Il me semble, en toute prétention, que le type d'approche que je propose n'a pas encore été essayé.
Il est donc soit génial, soit voué à l'échec xD

Je suis content que tu sois intéressé. Je pense qu'on peut assez bien se compléter...

La gloire, la célébrité et tout, j'suis pas sur d'en vouloir, je crois que je préfère "rester dans les ombres", mais je prends la moitié du fric qui va avec si on trouve

eh beh j'ai eu du mal à le trouver mais a y é ! j'en ai acheté un sur le net ^^ (de quoi occuper nos longues soirées d'hiver en famille ^^ même si on finis jamais !)

Moi, je trouve ça rigolo.
Mais je résous pas les puzzles à coups de mathématiques. Donc, je sers à rien, désolée.

Tof, je suis in, unless you want me out (et dans ce cas là, je mettrai les rangeos et forcerai la porte... faut pas délirer non plus... y'a une énigme à résoudre, là!)

Let me know quand vous vous faîtes la soirée du siècle avec FX et ton puzzle (et d'autres esprits à rayures?)...

Toi, résoudre une énigme ???


Avec une équipe comme celle là, c'est comme si c'était fait !
On organise ça bientôt


Liste de pièces sous Excel : check.

Désolé mais c'est pas très clair ton idée, enfin pas pour moi.

Idéalement, des dessins, des schémas, des illustrations étape par étape aideraient à comprendre ?

=========================================================================================

Tof a écrit:Amis des énigmes encore non résolues, bonjour !

AMIS floodeurs, svp pas ici.

Spoiler:

Certains d'entre vous ont peut-être déjà entendu parler d'Eternity :
C'est un puzzle casse-tête, créé par Christopher Monckton en 1999. Celui-ci offrait lors du lancement un million de livres sterling à celui qui arriverait à résoudre son puzzle de 205 pièces.
Une équipe d'étudiants a trouvé la solution en 5-7 mois :

Spoiler:

Ces mêmes étudiants ont ensuite été employés pour créer avec lui THE puzzle : ETERNITY II (à ceux que le nom étonneront, je réponds pourquoi pas, Chuck Norris a bien compté jusqu'à l'infini... 2 fois.)
Il parait que c'est un problème NP-complet ou un machin du genre, selon un pote qu'a fait des études et tout et tout, bon, ok, super, mais ça m'avance pas beaucoup. Il parait aussi que c'est super super chaud de trouver une solution, mais il n'a pas réussi à me décourager, la preuve, j'suis toujours là.

Eternity II, lancé en 2007, 2 millions de dollars à la clé lors du lancement, toujours non résolu.
La récompense n'était valable que jusqu'en 2009, il ne reste "plus que" le sport.

Mais je suis curieux de voir ce que quelques Z motivés pourraient être capables de faire...
Je lance donc un appel aux informaticiens, mathématiciens, logiciens et (T) HQI (+ étoile) de tous horizons, qui seraient motivés pour relever le défi, à me rejoindre. (sans non plus s'y mettre tous les jours, gardons une vie )

-------------------------

Eternity II est donc un puzzle carré de 256 pièces (16*16).
Il y a des droits sur les images du puzzle et des pièces et je ne me permettrais donc pas d'en poster une photo;
Voici ici une illustration simplifiée du principe du puzzle :

Spoiler:

Le vrai puzzle est donc de 16*16, comme déjà dit, et de mémoire compte 17 motifs différents. Vous pouvez certainement trouver une image en cherchant sur google.

Le nombre de possibilités de placement et d'orientation des pièces ayant plus de 600 zéros (en système décimal, précisons...), on estime que pour le résoudre par la force brute (essayer toutes les possibilités), il faudrait toute la puissance informatique mondiale pendant 2 fois l'âge de l'univers (j'ai pas vérifié les "il parait", hein).
Des centaines de milliers de personnes ont essayé de le résoudre, autant d'ordinateurs utilisant de nombreux algorithmes différents (backtracking, etc) ont cherché une solution, sans succès.

------------------------

Il y a quelques années, j'y avais passé pas mal de temps pendant une-deux semaines et vous présente ici mon angle d'attaque de l'époque, approximativement puisque j'ai depuis perdu toutes les données relatives à ça...

Je cherchais avant d'essayer de les placer à "orienter" les pièces (4 orientations possibles pour chacune).
En partant d'une constatation simple : puisque les motifs doivent s'assembler entre eux, chacun doit, sur l'ensemble de toutes les pièces, être présent autant de fois vers la gauche que vers la droite, et vers le haut que vers le bas.
J'avais défini pour chaque motif une lettre, puis représenté la pièce orientée par ABCD, par exemple, avec A en haut, B à droite, C en bas, D à gauche.
J'avais donc entré la liste de toutes les pièces sous excel, une pièce par ligne et un motif par colonne.

Le but était donc de trouver des orientations de pièces telles qu'il y ait autant de B, C, D etc dans la 1ère colonne que dans la 3ème, autant dans la 2nde que dans la 4ème.
Ayant défini A comme le motif "côté", je pouvais ajouter à cela qu'il fallait 16 A vers le haut, vers le bas, vers la gauche et vers la droite.
De plus, il fallait que les coins soient orientés différemment.
J'ai donc défini l'erreur A et lui ai donné un coefficient légèrement supérieur aux autres motifs (mais pas une priorité absolue pour ne pas restreindre l'exploration)

J'avais donc créé une "case" pour chaque motif qui calculait "l'erreur", définie par la valeur absolue de (nombre de motif X dans colonne 1 - nombre de X dans colonne 3) ajoutée à la valeur absolue de (nombre de X dans colonne 2 - nombre de X dans colonne 4).
Si l'erreur était de 0 pour un motif, celui ci était donc autant à gauche qu'à droite et autant en haut qu'en bas.

J'espère que je suis clair pour l'instant...

Je cherchais un moyen de trouver rapidement des solutions à ce problème d'orientations sans utiliser la force brute, insuffisante.

Avec un peu d'aide de mon père, n'y connaissant rien ou presque en programmation, j'avais fait un algo qui, pièce après pièce, cherchait à optimiser sa position par rapport à "l'erreur globale" (total des erreurs pour tous les motifs).
J'avais commencé par chercher à diminuer le total des erreurs coûte que coûte; en vain, très rapidement cela "bloquait" et plus aucune modification ne se faisait.

J'ai essayé ensuite de diminuer à chaque fois l'erreur du motif qui en comptait le plus : même chose, blocage au bout d'un certain temps.

J'avais alors bricolé une fonction polynomiale pour calculer "l'erreur globale" dont je suis pour l'instant incapable de me rappeler la forme exacte.
Je l'avais bricolée à l'instinct uniquement, mes connaissances en maths s'arrêtant en terminale (et encore).
Les carrés et autres exposants permettaient, entre autres (je ne me rappelle plus de toooutt ), de favoriser la diminution des erreurs des motifs en ayant le plus, mais sans tout de même créer trop d'erreurs supplémentaires pour les autres.
J'avais ajouté dans une très faible mesure une part de hasard dans les choix pour éviter les blocages, et, quand l'algo bloquait tout de même, une modification de l'orientation de 4 pièces au hasard.

Cette fonction et cet algo me permettait de rechercher une solution dans "l'ensemble des presque solutions", car l'erreur globale restait, autant que possible, proche de zéro.

Avec succès après quelques bricolages supplémentaires : à chaque fois que je lançais l'algo final en partant d'orientations aléatoires, je trouvais en quelques minutes à peine une solution (avec un vieil ordi tout pourri)
J'ai essayé, pour plusieurs de ces solutions (une 30aine), de les placer, sans succès.

Cette manière de faire ne permet pas, je pense, de trouver directement une solution au puzzle.

Mais, par rapport à l'angle d'attaque, je voudrais essayer quelque chose :
Représenter, avec orientation et placement, toutes les pièces dans un tableau, puis définir comme "erreur" chaque motif assemblé à un motif différent.
Puis, avec l'aide d'un algo et une fonction polynomiale à définir, à essayer de réduire l'erreur globale comme je l'avais déjà fait, en échangeant et orientant les pièces pour tendre vers le moins d'erreur possibles.

C'est à dire chercher une solution dans l'ensemble des "presque solutions", plus ou moins de la même manière.

-----------------------

Motivés ?

FLAMICHONNouveau venu


Messages: 1
Date d'inscription: 10/01/2012

FLAMICHON a écrit:Désolé mais c'est pas très clair ton idée, enfin pas pour moi.

Idéalement, des dessins, des schémas, des illustrations étape par étape aideraient à comprendre ?

Bonjour, FLAMICHON.
Sans vouloir t'offusquer, je ne prendrais pas deux heures pour ajouter schémas et tout pour être plus clair pour toi, par contre je veux bien prendre 5 minutes pour t'expliquer pourquoi.
Etant donné que c'est ton premier message sur le forum, inscrit le jour même, et que ce sujet n'est pas le plus voyant quand on arrive ici, j'estime à environ 98% les chances que tu sois tombé dessus en cherchant Eternity II et pas ce forum en particulier. Ce n'est peut-être pas le cas, mais c'est probable.
Ajoutons à cela que je souhaitais juste présenter mon angle d'attaque, et pas fournir non plus une solution, que je n'ai pas.

Tu comprendra, j'espère, que je ne souhaite pas te détailler la manière dont (je/nous) (compte m'y/comptons nous) y prendre.
Il y a des sites/forums de discussion sur le sujet, je pense que tu les trouvera sans problème.

Bonne journée à toi.

boite reçue aujourd'hui !
déjà déballée ^^
les filles veulent y jouer... "allez y les filles me perdez pas de pièces, quand vous en aurez marre, ce sera mon tour"

On se Mpetera pour les questions tof (oué moi en partie maths pure je te servirai pas a grand chose mais on peut creuser niveau conception / possibilités éventualités peut être... (occasion de reprendre les MP ^^ )

Heu, tof, là non plus je ne te comprends pas très bien ...

Si je résume bien, tu lances sur un forum un appel à un travail collectif sur la base d'une vague idée à toi et à explorer, ensuite, tu fais machine arrière quand il s'agit d'entrer dans le vif du sujet ? Tu comptes t'y prendre comment, alors, pour travailler en groupe sans partager ta conception ?
Tu es au courant que le concours est terminé depuis un moment ? Alors à quoi ça rime, cette suspicion ?
Bien sûr que je suis arrivé sur ce forum en faisant une recherche sur le net de "ETERNITY 2", à quel sujet crois-tu qu'il faille s'intéresser pour arriver sur ton post ? Tu me renvoies sur des forums de discussion sur le sujet ... Ah ? Parce que le post que tu as ouvert n'en étais pas un ? C'était quoi, alors ?

Enfin, pour reprendre ton expression, tu comprendras, j'espère, que je ne souhaite plus maintenant répondre à ton appel. ETERNITY 2 est bel et bien enterré, j'avais bien fait d'en rester là et je m'y tiendrais.

Bonne continuation dans la chambre des secrets
==============================================================================================

Tof a écrit:

FLAMICHONNouveau venu


Messages: 1
Date d'inscription: 10/01/2012

FLAMICHON a écrit:Désolé mais c'est pas très clair ton idée, enfin pas pour moi.

Idéalement, des dessins, des schémas, des illustrations étape par étape aideraient à comprendre ?

Bonjour, FLAMICHON.
Sans vouloir t'offusquer, je ne prendrais pas deux heures pour ajouter schémas et tout pour être plus clair pour toi, par contre je veux bien prendre 5 minutes pour t'expliquer pourquoi.
Etant donné que c'est ton premier message sur le forum, inscrit le jour même, et que ce sujet n'est pas le plus voyant quand on arrive ici, j'estime à environ 98% les chances que tu sois tombé dessus en cherchant Eternity II et pas ce forum en particulier. Ce n'est peut-être pas le cas, mais c'est probable.
Ajoutons à cela que je souhaitais juste présenter mon angle d'attaque, et pas fournir non plus une solution, que je n'ai pas.

Tu comprendra, j'espère, que je ne souhaite pas te détailler la manière dont (je/nous) (compte m'y/comptons nous) y prendre.
Il y a des sites/forums de discussion sur le sujet, je pense que tu les trouvera sans problème.

Bonne journée à toi.

Tu n'as pas tort, Flamichon (et je me suis certainement mal exprimé, je m'en excuse).

Je plaide coupable, avec pour circonstance atténuante la flemme...

Flemme de refaire tout le travail (assez conséquent) de l'époque, qui serait nécessaire pour vraiment détailler la démarche. Le but n'est pas de refaire exactement la même chose, j'essayais de décrire l'angle d'approche que j'avais eu (vaguement, c'est vrai, mais mes souvenirs sont eux-mêmes assez vagues) comme base de travail.

Bien sûr que je suis arrivé sur ce forum en faisant une recherche sur le
net de "ETERNITY 2", à quel sujet crois-tu qu'il faille s'intéresser
pour arriver sur ton post ?

Je n'avais pas pensé (oui, ça m'arrive) que des gens tomberaient sur ce post uniquement en recherchant Eternity 2, étant donné le nombre de sites consacrés uniquement à ce sujet.

Le but était de faire ça avec des membres de ce forum (qui n'est à la base ni un forum d'énigmes, ni de puzzles, et qui a part pour Eternity n'a pas l'air de t'intéresser beaucoup pour l'instant, et ce n'est pas un reproche) plus que la résolution du puzzle. Des membres l'ont trouvé, comme tu peux le constater, sans rechercher "Eternity 2".
L'un des objectifs est l'échange de compétences (informatiques, mathématiques, logique, etc).

Cela dit, si tu souhaites des explications, je te répondrai (si je le peux), mais dans ce cas là, il vaudrait mieux que tu pose une question sur un point particulier.
Je ne peux pas détailler toute la démarche de manière à ce que tout le monde comprenne l'intégralité du post, même si je le voulais.

Cordialement,
Bonne continuation ou à bientôt.
Tof

Bonjour,

je viens de trouver une heuristique assez rapide pour résoudre ce puzzle par contre je ne trouve pas de solutions. Je n'arrive a placer que 251 pièces sur 256.