Reprise du message précédent :
Tu veras bien en juillet
 
Pourquoi en juillet ?
C'est pas en décembre qu'ils dépouille le courrier ?

oui, on vera en decembre

Petit déterrage de topic en cette fin de soirée ou je me suis dit "tiens, ça en est où Eternity II ?".

J'avais envi de faire une appli tournant sur pas mal de PCs auxquels j'avais accès et gérée via une bdd unique, mais j'ai appris l'existence du jeu 1 semaine après sa sortie et en comptant bien 2-3 semaines, voire un mois, au mieux, pour pondre un truc potable, je pensais que c'était déjà grillé...
J'ai quand même commencé l'algo à l'époque, sans avoir eu la motivation pour passe plus de quelques heures dessus (je me voyais mal partir avec un train de retard sur un travail de plusieurs mois ou je me serais posé la question à chaque seconde de savoir si quelqu'un n'avait pas trouvé avant même que mon appli tourne...), en partant sur les idées suivantes :

- Générer d'abord la liste des cadres possibles à partir des 4 pièces d'angles et de celles de bordures. J'aurais pu (j'avais commencé) laisser un PC tourner pour faire toutes ces combinaisons pendant que je codais le reste.
- Chacune de ces combinaisons de cadres en donnerait en fait 4, par rotations successives de 90°, pour représenter toutes les possibilités par rapport à la pièce fixe, donc un petit algo aurait fait cette multiplication une fois le premier terminé. Ou alors la rotation aurait été faite au moment de l'arrivée sur la pièce unique pour gagner du temps.
- L'appli aurait ensuite pris aléatoirement une de ces combinaisons (en retenant bien sûr celle qui ont été gérées, chaque PC piochant donc aléatoirement dans la liste), et calculé toutes les "croix" possible de pièce pour relier la pièce fixe au 4 cotés du cadre (et ce pour chacune des 4 rotations du cadre).
- Ensuite, on attaque l'escargot en partant aléatoirement d'un des 4 angles internes du cadre, et à chaque fois qu'on croise le chemin de la croix reliant la pièce fixe aux bordures, on teste qu'au moins une des crois existantes contient la pièce qu'on est en train de tester à cette place. Du coup, à chaque fois qu'on croise le chemin de cette croix, on réduit la liste des croix répondant à tous les croisements déjà effectués. Ca devrait donc permettre d'arrêter assez rapidement un escargot (si aucune croix n'est valide pour aucune des pièces restantes) qui pourrait prendre beaucoup de temps si l'algo passe son temps à revenir de plus en plus loin en arrière depuis les 2 derniers tours (puisque là on bloque bien plus tôt et revient en arrière plus tôt, en zappant beaucoup de possibilités).

S'il y avait trop de croix possibles pour chaque cadre, j'aurais pris ça dans l'autre sens, en ne calculant pas la liste des croix possibles mais en calculant à chaque fois qu'on teste une pièce sur une case alignée avec la pièce fixe si au moins une croix peut encore être formée avec les pièces restantes pour compléter la grille courante. J'aurais même certainement fait ça, car il est bien plus simple de générer des croix à partir des pièces restantes que d'exclure toutes les croix déjà générées qui contiennent des pièces déjà utilisées (sauf si elles sont à leur place) dans la grille actuelle.

J'aurais probablement géré les 4 rotations de chaque cadre en même temps, en calculant et testant toutes les croix pour les 4 rotations d'un cadre. Même chose pour la fin de l'escargot, quand ça arrive au contact de la pièce fixe, j'aurais testé à chaque fois pour les 4 rotations. Bien sûr c'est la pièce fixe qui aurait été tournée, et si une combinaison avait été trouvée, une rotation de la solution aurait été faite pour correspondre à la position originale de la pièce fixe. Bref, pas mal de petits trucs du genre pour optimiser vaguement.

J'ai beau me douter qu'en pratique ce soit bien trop simpliste et trop long même pour plusieurs PCs, avec probablement énormément de cadres et de croix possibles pour chaque rotation de chaque cadre (que ce soit en les calculant à l'avance ou en testant à chaque fois qu'une pièce est placée alignée avec la pièce fixe), que d'autres ont pensé à ça ou à des solutions bien meilleures et les ont appliquées bien avant, avec bien plus de moyens informatiques, et que les mathématiciens sont bien plus avantagés et efficaces que les programmeurs, je ne peux pas m'empêcher de penser qu'il doit y avoir de bonnes chances de tomber sur une des 20000 combinaisons, que ça devrait tourner assez vite en éliminant rapidement de nombreuses combinaisons, et que 5 ou 6 PC tournant 24/24 devraient finir par trouver une bonne combinaisons.
J'ai plus que certainement tort, surtout quand on voit le nombre mirobolant de combinaisons possibles (même si statistiquement on peut espérer trouver une solution au bout d'1/20000e des combinaisons, en en ayant sauté une bonne portion d'invalides), en ayant du mal à imaginer qu'un PC, bien que rapide, ça ne peut pas tester autant de possibilités en quelques heures ou jours (et pourtant, j'ai vu divers calculs du temps que ça prendrait de tester toutes les combinaisons et ai même pu avoir un aperçu avec mes premiers tests...).

Enfin, j'espère que la solution aura été trouvée par des mathématiciens avec des formules bien complexes et qu'il sera montré que le type de solution que j'envisageais n'aurait pu en aucun cas être assez rapide, histoire de ne pas être dégouté

J'ai rendez vous demain chez l'opticien  

 
sympa ton idée, en gros tu divises par deux les espaces vides, ca fait penser à une recherche dichotomique, sauf que là l'ensemble n'est pas trié, je pense qu'en fin de compte tu te retrouverais devant le même problème que tous ceux qui appliquent un backtracking en variant seulement l'ordre de remplissage de la grille...
 
quelqu'un a essayé autre chose que du backtracking ? allez-y, dites vos idées ratées ou inexploitées, même farfelues (je dirais même surtout si elles sont farfelues), je réclame du rêve et du rire sur ce coup-là... marre de la rigueur mathématique...
 
sinon pour ceux qui espèrent encore un peu : deux nouvelles boites indices sortent en ce moment pour deux nouvelles pièces sur le plateau de jeu...

 
 
Malheureusement ça ne peut pas marcher. En effet il n'y a que quelques motifs (5 me semble-t-il) différents pour assurer les jointures des bords, et aucune pièce n'est en double.
Dès la première pièce, tu as donc une dizaine de possibilités, puis encore une dizaine, suivi d'une dizaine, etc...
le tout 56 fois (14*4, le nombre de bords à poser). On est donc parti pour du 10^56 bords différents !
Bref calculer tous les bords possibles, c'est déjà une opération monstrueuse...

Arf, je sentais venir ce coup là. Pour faire quelques tests j'avais généré une bordure aléatoire avec pas mal de pièces, en me disant "je paris que ces vicelards on mis peu de motifs différentes sur le tour et on étudiés les pièces du jeux pour maximiser le nombre de combinaisons arrivant presque au bout".

En fait, ça me rassure, puisque le combo "ceux qui ont tenté le backtracking ont vite été coincés" + "peu de motifs et pas de pièce en double pour former les bords" me permet de ne pas avoir de regrets, mais au contraire d'être content de ne pas avoir perdu mon temps (et mon l'argent pour acheter le jeu pour découvrir ces pièces) inutilement

Ceci dit j'ai pas suivi pour le backtracking à quel niveau ça coince, parce que techniquement ça reste viable, et j'avais 6 ou 7 PCs qui pouvaient tourner pour ça il y a 1 an, mais bon rien que le peu de motifs sur les bords et l'absence de pièces en double (et je paris qu'il y en a peu ou pas hors bords aussi) suffit à rendre la chose limite ingérable.

meme avec 10 PC, tu passerais de 10^56 a.... a peine 10^55 autrement dit, c'est negligeable, et meme avec tout les PC de la terre rien que pour toi, il resterait encore quelquechose comme 10^45
Je sais pas trop ce que ca va donner, si personne n'a trouve de solution a la fin de l'annee, je tenterai ptete de m'y replonger pour l'annee d'apres, mais pour l'instant j'avoue que j'ai complètement laissé tomber...

 
Certes, quelques centaines de jours de plus ou de moins...
 
Et puis quand je vois comme je crève de chaud avec seulement 2 PCs qui tournent, tous les PCs de la terre dans mon appart Montpellierain, non merci
 

 
Et tu auras 2 ans de retard sur ceux qui planchent depuis le début, donc trop de retard pour une solution purement informatique, et certainement totalement largué pour une solution mathématique (à moins que tu sois un gros matheux). Donc au final, au mieux tu t'amuseras un peu, au pire tu perdras ton temps

 
Je me suis penché un peu sur le probleme, personnelement au debut je suis allé par force brute, du haut a gauche vers le bas. je me rappelle plus si je començais par faire le cadre d'abord ça commence a faire vieux    d'ailleurs j'ai meme pas chercher par où il etais plus judicieux de commencer.  
 
Mais ma premiere amélioration étais la bonne ;
le systeme qui marchait le mieux pour moi c'etait quand je pouvais plus placer de pieces, je regardais si y avais des pieces utilisés qui aurai été utile, tres souvent oui y a une piece qui permet d'avancer un peu plus le puzzle mais qui etais deja utilisé, alors par la suite j'evitais de les utiliser en debut de puzzle.  
Voila c'est pas un miracle non plus mais chez moi ça a marché j'ai noté une tres sensible amélioration. apres impossible a dire si c'est de la chance ou pas.
 
ensuite j'ai essayé d'approfondir, si j'avais besoin d'une piece qui été deja utilisé ben je la prenais quand meme, et j'agrandissais le trou autour de la piece que je prenais afin de le reconstituer d'une autre maniere. c'etait bete et ça marche pas du tout, car bien souvent meme si on fais un trou de 6*6 sur le puzzle la seule solution qu'on trouve avec les bons bords y en a qu'une, donc impossible de remplacer la piece qu'on prend par une autre. Enfin c'est potable si on aggrandi le trou de la taille du puzzle quasiment    
 
apres je suis parti sur autre chose, pour savoir quel piece placer, je posais une piece (parmis celle a tester) et fesais une simulation qui posaient les autres pieces possible aléatoirement, la piece qui avais le meilleur score été placé definitivement. mais ça marche pas non plus niveau efficacité.
 
et puis experimentalement je me suis arreté la car finalement on est bien loin du compte, et j'arrive pas a voire de solution miracle.
 
 
 
apres en théorie j'avais et j'ai toujours des idées ;
je pense que si on doit choisir entre 2 pieces il faut mettre la piece la plus probable. et on peut se faire une idée en calculant tous les carré 7*7 possible et determiner quel piece a le plus de chance d'etre a coté de tel piece.
 
Et puis y a trop de possibilité ; la clé doit aussi resider dans le fait qu'on doit pouvoir dire que si la piece X est ici la piece Y ne pourra pas etre 5 cran a gauche et 1 cran en bas. ça doit etre possible en calculant toute les possibilité de rectangles de differentes formes, encore que je suis sceptique.
 
 
je dois surement oublié des idées que j'ai eu, mais en tout cas ce que je me rappel, c'est que je me suis bien amusé a reflechir sur ce probleme qui peut paraitre facile au premier abord  

Avec un travail d'optimisation poussé, ça pourrait prendre beaucoup moins de temps que ça.

 
Ah oui j'avais aussi pensé à ça ! Mais la mise en oeuvre me paraissait trop compliquée, il fallait gérer les bords + les pièces imposées, et donc limiter sérieusement la taille des trous possibles... Je suis content que quelqu'un ait quand même testé ça.
 
Dans la série des trucs qui ne marchent pas, il y a aussi le fait de précalculer toutes les paires de pièces possibles, pour ne plus travailler que sur un puzzle de 8*16. Je me souviens que ça m'avait pris un peu de temps à coder, et  qu'au final les perfs étaient à peu de chose près identiques (à 10-15 % près) qu'avec mon algo de départ...  

 
Euh, non ce n'est pas négligeable puisqu'il aurait alors couvert 90% des possibilités...

Salut les chercheurs ! (s'il en reste, lol)
Plus que quelques jours et on va savoir si la solution a été trouvée ousi on repart pour un an de plus...
Bonne fêtes à tous !

Tu viens d'illustrer qu'il faut toujours faire tres attention avec les pourcentages. Un album dont les ventes font +600%, ca pourrait sembler bien... sauf si en realite elles passent de 1 a 7. Ici c'est pareil, meme en eliminant 90%, il reste encore un nombre tellement enorme de possibilites qu'au final c'est negligeable ( )
 

Oui, il en reste
Je m'y suis remis serieusement depuis quelques jours Je regardais un sondage sur le groupe yahoo, plus de 80% des gens(dont moi) pensent qu'il ne sera pas resolu cette annee...

 
je ne pense pas qu'il sera resolut aussi cette année, mais on peut s'attendre a tout  

Hum...
Moi je pense qu'il est tout a fait possible qu'une équipe de matheux et d'informaticiens l'ai résolu. Puisque le puzzle à été conçu grace aux mathématiques, d'autres mathématiciens doivent être capables de trouver des formules limitant suffisament le nombre de configurations pour le rendre accessible à un ordinateur.
On sera bientôt fixé.

y a plus qu'a attendre demain

oui,vivement demain !

annonce des resultats imminente je pense

Toujour rien sur le site !
Qu'est ce qu'ils foutent ?

Alors trouvé ou pas ?
Y en marre d'attendre !
A moins que tous ceci ne soit qu'une vaste arnaque et que nos trois lascars ne se soient envolé dans la nature avec le bénéfice gagné sur la vente des boites ?

Toujours rien sur le site ce matin !
Le compteur reste bloqué à 0 mais que faut-il en déduire ?
Ont-ils reçu tellement de réponses qu'ils mettent si longtemps pour les dépouiller ?
Ou bien la solution a-t'elle été trouvée ?
Ou alors c'était vraiment une arnaque ?
Qu'en pensez-vous ?

arnaque ?

D'après le liste yahoo, ce serait cette solution, apparement c'était déja comme ca pour le 1...

Attendons, alors...
Ce qui est moche si la solution à été trouvé, c'est que des gens continuent à acheter des boites alors qu'ils n'ont plus aucune chance de gagner.

Pour le premier Eternity, ils avaient donné la réponse au bout de combien de temps ?

Et si la réponse a été trouvée, vont-ils sortir un Eternity III ?

Bizarre...
J'ai envoyé un mél à leur service de relation public (erwan.massiot@news-paper.fr) pour essayer d'avoir des infos et il m'est revenu paure cause de destinataire inconnu !
Je trouve que ça craint de plus en plus cette histoire...

oups ! lire our cause de

re-oups ! lire : pour cause de

apparement sur eternity2.FR avec la puissance des ordis de la communauté ils auraient trouvé 467 motifs correspondant sur 480. 30 solutions de 467 motifs auraient été trouvé mais 0 avec 468.
 
Je doute tres fortement que quelqu'un ai trouvé la solution parfaite cette année.

Sur le site zaloudek.kabel1.cz ils montre un dessin d'un puzzle 16x16 entierement terminé. Bien entendu, ils ont changé les motifs, et comme je ne connait pas le tchéque je ne sais pas s'ils ont vraiments trouvé une solution ou si c'est seulement une illustration pour montrer à quoi devrait ressembler la solution.
Si quelqu'un parle cette langue et peut traduire...
En entendant, sur le site internity, il n'y a toujours aucune info !

oups ! lire : ils montrent
et : sur le site eternity

c'est pas tres difficile de montrer un puzzle 16*16 fini. il suffit d'en acheter 2 et d'en faire qu'un seul

oui, mais quel interêt ?

toujours aucune info sur le site !
j'espère qu'ils vont pas faire comme Dan Brown avec son hypothétique 5ème bouquin ! Au départ il devait sortir mi 2006, on  est en 2009 et toujours rien à l'horizon !

Allez plutôt lire le site anglais qui est plus souvent mis à jour que la version française (qui semble complètement délaissée).
Le dépouillement est terminé et aucune solution complète n'a été envoyée.
C'est celle à 467 qui a été récompensée de $10 000 (apparament trouvée avec un algo, cf le site non officiel www.eternity2.fr).
Donc on peut continuer à se creuser les méninges (enfin pour ceux qui cherchent avec leurs ménainges ;0)

Merci pour l'info !
continuons donc à chercher !
bon courage à tous !

Hello !
Plus personne ne viens sur ce forum ?

les chercheuses et les chercheurs !
ça avance vos recherches ?