[Mathématiques] Eternity II, le nouveau casse-tête serait plus simple/difficile si...

cricri · 08/08/2007, 13h43

bon j avais fait 3 erreur de codage des pieces

mon pgm avance bien mais ....
le hic il me dit qu il y a pas de solution pour l instant

j ai le choix re re verifier les pieces
ou verifier le pgm

viens de pense j ai pas penser a utiliser 2 x la meme piece dans la meme case en la tournant si elle rentre de 2 facon differente

j y retourne a ce soir avec le puzzle fini

-Black-Shadow- · 08/08/2007, 15h51

Citation :

Publié par cricri

j y retourne a ce soir avec le puzzle fini

J'aimerais bien voir ca. C'est pas que je doute des capacités des joliens mais presque :x.

Si tu gagnes les 2M tu organises une méga irl de 1 mois aux canaries tout frais payé?

Super Belette · 08/08/2007, 17h58

Citation :

Publié par cricri

mon pgm avance bien mais ....
le hic il me dit qu il y a pas de solution pour l instant

Si t'utilise une méthode brutale je pense que tu vas pouvoir attendre longtemps avant d'en trouver une

Gardien · 08/08/2007, 18h04

Citation :

Publié par Super Belette

Si t'utilise une méthode brutale je pense que tu vas pouvoir attendre longtemps avant d'en trouver une

En supposant que l'ordi analyse 100 possibilité par seconde, ca donnerai environ 3e490 année.

peut etre un peu moin avec de la chance :X

Airmed / Ildefonse · 08/08/2007, 18h06

t as une plus grosse proba en cherchant de maniere aleatoire

Super Belette · 08/08/2007, 18h16

Citation :

Publié par Airmed / Ildefonse

t as une plus grosse proba en cherchant de maniere aleatoire

non ^^

c'est comme dire qu'au loto t'a moins de chance de gagner si tu joues 1 2 3 4 5 : c'est faux!

Airmed / Ildefonse · 08/08/2007, 18h32

j'ai pas compris la comparaison avec le loto

Super Belette · 08/08/2007, 18h41

je veux dire qu'entre un algorithme qui essai de trouver les combinaisons en utilisant une méthode "ordonnée" c'est à dire qui place les pièces dans l'ordre (si on suppose qu'elle sont numerotées de 1 a 256) jusqu'a tomber sur un cul de sac, revient en arrière et recommence des qu'il peut avec une autre pièce ... et un algorithme qui essai des combinaisons en plaçant les pièces restantes de manière aléatoire (en respectant quand même les contraintes, et en se souvenant des précedentes configurations pour ne pas en recalculer une 2 fois), la proba de trouver la solution est la même ...

je sais pas si je suis clair, mais en gros dire qu'une méthode aléatoire est mieux qu'une méthode ordonnée, dans le cas de ce jeu, c'est faux

Airmed / Ildefonse · 08/08/2007, 18h59

mouais
le retour en arriere & co est beucoup trop long à calculer je pense. Imo, c'est plus simple de definir toutes les possibilites et d'optimiser au maximum le test de coherence des pieces.

Je me souviens d'une fast code sur un theme equivalent, on prend des pieces de tetris, et faut en caser un max. La solution la plus rapide etait de tout calculer à l'avance.

Super Belette · 08/08/2007, 19h09

Qu'entends tu par calculer toutes les possibilités ?

Si tu veux dire calculer toutes les configurations possibles du plateau , beh ca revient a faire la methode brute!
Mais vu le nombre de possibilité -comme il a été dit precedemment ~10^506 (quoi que ce nombre ne prend pas en compte les contraintes, ni les pieces identiques, etc..)-, ca ne semble pas etre la bonne méthode ...

Airmed / Ildefonse · 08/08/2007, 19h56

oui, tu te fais un algorythme generant un nombre compris entre 0 et 10^506 et tu tests si c est bon.
Si l'algorythme de random est bon, tu feras toutes les combinaisons mais pas dans l'ordre

Rafa · 08/08/2007, 20h08

Une méthode un peu moins brute permettrait de réduire les calculs j'imagine : avec les pièces de départ, on fait l'inventaire des dalles de couleur que ça va former (x rouges, y bleues, etc), et l'on regarde tous les pavages possibles avec ces dalles. Puis l'on découpe et l'on cherche parmi les découpages obtenus les stocks de pièces qui correspondent à celui de départ

Sur un 16*16, on doit avoir si y a pas d'erreur 480 (476 avec la pièce de départ) emplacements de dalles colorées, mais au plus 22 possibilités pour les remplir (puis ça baisse au fur et à mesure qu'on épuise le stock de verts, rouges, etc).

Après, un problème serait de trouver comment "nommer" de manière efficace les types de pièce, histoire de ne pas être gêné par les problèmes de rotation, mais ça semble déjà donner moins de calcul que le placement des pièces au hasard. Et pour profiter pleinement d'une telle méthode, il faudrait surtout pouvoir comparer efficacement ces stocks de 256 pièces

Airmed / Ildefonse · 08/08/2007, 20h44

oui c'est une idée aussi, mais la question serait de savoir si ce post traitement va pas etre trop long ensuite.

Enfin globallement, imo, des bons gros algorythmiciens doivent deja etre dessus, et a moins de tomber sur la solution par hasard ...

Segura · 08/08/2007, 21h12

J'utilise le même principe que Rafa. ^^ (plus ou moins)

Zouave321 · 09/08/2007, 16h50

si on met tous les pc du monde a la recherche de la solution par force brute, on mettra combien de temps a trouver ? car j'ai l'impression que meme 4 milliards d'années ça suffirai pas... (en 1journé mon ordi n'a meme pas fais 1/10^20 du travail environ..)

Rafa · 09/08/2007, 17h47

Mettre un ordinateur ou tous sur la méthode gros sabots, ça change pas grand chose en efficacité. Même si on gagne 50 à l'exposant (donc si on va 10^50 fois plus vite. Déjà, bonne chance pour gagner 50), ça reste que dalle face à l'énormité d'un 10^500.

Cool, on se réparti les tâches, j'ai "plus que" 10^450 possibilités à vérifier !

Wé, ça le fait vraiment pas

BadProsper · 09/08/2007, 17h50

Bin c'est vrai qu'en admettant qu'un ordinateur calcule 1 milliard de combinaisons par seconde, donc 31 536 000 000 000 000 par an (31*10^15) ce qui est déjà je pense impossible actuellement
En imaginant qu'il y ait 5 milliards d'ordinateur sur la terre ça ferait :

157 680 000 000 000 000 000 000 000 soit 157*10^24 combinaisons par an

Il faudrait en gros (sans compter les rotations) :

256! / 157*10^24 = 5*10^480 années pour réaliser toutes les combinaisons possibles avec 256 pièces

Soit 5 milliard de milliard (53 fois) d'années

(ou alors j'ai calculé n'importe comment)

Gardien · 09/08/2007, 17h56

Citation :

Publié par BadProsper

Soit 5 milliard de milliard (53 fois) d'années (ou alors j'ai calculé n'importe comment)

si t'as faux tu dois pas etre tres loin de la verité

a ce niveau on est plus a un ou 2 exposant pret

GuiWald · 09/08/2007, 19h27

Citation :

Publié par Messire Moustache

plus difficile, sans aucun doute. Pour s'en persuader, on a qu'à prendre l'hypothèse inverse : si il n'y avait que deux motifs différents, il suffirait de mettre les pièces d'une couleur d'un côté, celles de l'autre couleur de l'autre côté, et s'arranger au milieu avec ce qu'il reste.

Et pour se persuader que tu as tord, prenons maintenant le cas du puzzle avec non pas 2, ni 4, mais... 480 couleurs, soit le nombre de contacts entre 2 pièces sur le gros puzzle. La solution se présenterai alors d'elle même, n'ayant pas plus d'une possibilité de mettre en contact 2 mêmes couleurs (en gros la condition inverse de s'il n'y avait qu'une couleur)

Maintenant, savoir avec quel nombre de couleurs le puzzle serai le plus difficile, ben je sais pas

cricri · 09/08/2007, 19h57

faut arreter avec 10 e500 possibilite lol
en a boucoup moins que ca
si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere

BadProsper · 09/08/2007, 20h10

Citation :

Publié par cricri

faut arreter avec 10 e500 possibilite lol
en a boucoup moins que ca
si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere

ha ba ouais !

jasper · 09/08/2007, 21h02

Citation :

Publié par cricri

faut arreter avec 10 e500 possibilite lol
en a boucoup moins que ca
si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere

désolé mais MDR §§

Chibi Luffy · 09/08/2007, 21h06

Citation :

Publié par cricri

faut arreter avec 10 e500 possibilite lol
en a boucoup moins que ca
si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere

Ok on te laisse le faire alors.

*JeuxOnline, et tout est plus simple.*

Super Belette · 09/08/2007, 21h08

oh my lol je suis plié

*imagine l'algorithme qui commence par placer 5 pieces sur le plateau de 256 cases et qui revient en arriere *

Gardien · 09/08/2007, 22h36

Citation :

Publié par cricri

faut arreter avec 10 e500 possibilite lol
en a boucoup moins que ca
si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere

Ok ! Donc si on considere que ce que tu dis est vrai, on est pas a 10e500 mais 20e256 alors? bon ben c'est super tu a gagné environs quelques milliards d'années, il t'en reste plus que beaucoups et t'y est

cricri Alpha & Oméga	bon j avais fait 3 erreur de codage des pieces mon pgm avance bien mais .... le hic il me dit qu il y a pas de solution pour l instant j ai le choix re re verifier les pieces ou verifier le pgm viens de pense j ai pas penser a utiliser 2 x la meme piece dans la meme case en la tournant si elle rentre de 2 facon differente j y retourne a ce soir avec le puzzle fini
08/08/2007, 13h43

-Black-Shadow- Alpha & Oméga	Citation : Publié par cricri j y retourne a ce soir avec le puzzle fini J'aimerais bien voir ca. C'est pas que je doute des capacités des joliens mais presque :x. Si tu gagnes les 2M tu organises une méga irl de 1 mois aux canaries tout frais payé?
08/08/2007, 15h51

Super Belette Oracle	Citation : Publié par cricri mon pgm avance bien mais .... le hic il me dit qu il y a pas de solution pour l instant Si t'utilise une méthode brutale je pense que tu vas pouvoir attendre longtemps avant d'en trouver une
08/08/2007, 17h58

Gardien Alpha & Oméga	Citation : Publié par Super Belette Si t'utilise une méthode brutale je pense que tu vas pouvoir attendre longtemps avant d'en trouver une En supposant que l'ordi analyse 100 possibilité par seconde, ca donnerai environ 3e490 année. peut etre un peu moin avec de la chance :X
08/08/2007, 18h04

Airmed / Ildefonse Alpha & Oméga	t as une plus grosse proba en cherchant de maniere aleatoire
08/08/2007, 18h06

Super Belette Oracle	Citation : Publié par Airmed / Ildefonse t as une plus grosse proba en cherchant de maniere aleatoire non ^^ c'est comme dire qu'au loto t'a moins de chance de gagner si tu joues 1 2 3 4 5 : c'est faux!
08/08/2007, 18h16

Airmed / Ildefonse Alpha & Oméga	j'ai pas compris la comparaison avec le loto
08/08/2007, 18h32

Airmed / Ildefonse Alpha & Oméga	mouais le retour en arriere & co est beucoup trop long à calculer je pense. Imo, c'est plus simple de definir toutes les possibilites et d'optimiser au maximum le test de coherence des pieces. Je me souviens d'une fast code sur un theme equivalent, on prend des pieces de tetris, et faut en caser un max. La solution la plus rapide etait de tout calculer à l'avance.
08/08/2007, 18h59

Super Belette Oracle	Qu'entends tu par calculer toutes les possibilités ? Si tu veux dire calculer toutes les configurations possibles du plateau , beh ca revient a faire la methode brute! Mais vu le nombre de possibilité -comme il a été dit precedemment ~10^506 (quoi que ce nombre ne prend pas en compte les contraintes, ni les pieces identiques, etc..)-, ca ne semble pas etre la bonne méthode ...
08/08/2007, 19h09

Airmed / Ildefonse Alpha & Oméga	oui, tu te fais un algorythme generant un nombre compris entre 0 et 10^506 et tu tests si c est bon. Si l'algorythme de random est bon, tu feras toutes les combinaisons mais pas dans l'ordre
08/08/2007, 19h56

Airmed / Ildefonse Alpha & Oméga	oui c'est une idée aussi, mais la question serait de savoir si ce post traitement va pas etre trop long ensuite. Enfin globallement, imo, des bons gros algorythmiciens doivent deja etre dessus, et a moins de tomber sur la solution par hasard ...
08/08/2007, 20h44

Segura Oracle	J'utilise le même principe que Rafa. ^^ (plus ou moins)
08/08/2007, 21h12

Zouave321 Oracle	si on met tous les pc du monde a la recherche de la solution par force brute, on mettra combien de temps a trouver ? car j'ai l'impression que meme 4 milliards d'années ça suffirai pas... (en 1journé mon ordi n'a meme pas fais 1/10^20 du travail environ..)
09/08/2007, 16h50

Rafa Alpha & Oméga	Mettre un ordinateur ou tous sur la méthode gros sabots, ça change pas grand chose en efficacité. Même si on gagne 50 à l'exposant (donc si on va 10^50 fois plus vite. Déjà, bonne chance pour gagner 50), ça reste que dalle face à l'énormité d'un 10^500. Cool, on se réparti les tâches, j'ai "plus que" 10^450 possibilités à vérifier ! Wé, ça le fait vraiment pas
09/08/2007, 17h47

Gardien Alpha & Oméga	Citation : Publié par BadProsper Soit 5 milliard de milliard (53 fois) d'années (ou alors j'ai calculé n'importe comment) si t'as faux tu dois pas etre tres loin de la verité a ce niveau on est plus a un ou 2 exposant pret
09/08/2007, 17h56

cricri Alpha & Oméga	faut arreter avec 10 e500 possibilite lol en a boucoup moins que ca si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere
09/08/2007, 19h57

BadProsper Alpha & Oméga	Citation : Publié par cricri faut arreter avec 10 e500 possibilite lol en a boucoup moins que ca si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere ha ba ouais !
09/08/2007, 20h10

jasper Alpha & Oméga	Citation : Publié par cricri faut arreter avec 10 e500 possibilite lol en a boucoup moins que ca si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere désolé mais MDR §§
09/08/2007, 21h02

Chibi Luffy Légende	Citation : Publié par cricri faut arreter avec 10 e500 possibilite lol en a boucoup moins que ca si on essaye de coller 2 carre il y a environ 20 possibilite mais rajoute 1 c est moins que 20 puis etc apres 5 6 truc place c est quasiment qu on tombe a 0 et qu il faut revenir en arriere Ok on te laisse le faire alors. JeuxOnline, et tout est plus simple.
09/08/2007, 21h06

Super Belette Oracle	oh my lol je suis plié imagine l'algorithme qui commence par placer 5 pieces sur le plateau de 256 cases et qui revient en arriere
09/08/2007, 21h08

[Mathématiques] Eternity II, le nouveau casse-tête serait plus simple/difficile si...

Connectés sur ce fil