Reprise du message précédent :
Quel est l'intérêt de ceux qui mettent en ligne des cd, des films, la première traduction d'Harry Potter, des virus qui vont bousiller tes fichiers, etc... ?? Pourtant on trouve tout ça à proffusion. D'autant qu'ici il s'agit de quelques images, c'est fait en 5 sec (contrairement à traduire un bouquin...)

je vois pas le rapport

Je vois que tout le monde s'excite sur la puissance des ordinateurs. Mais le nombre de combinaison possible est un arrangement de 256 pieces, soir factoriel 256!, soit quelque chois plus grand que 10^500. Imaginez un ordinateur ou un cluster ou ce que vous voulez qui peut tester 1 milliards de puzzle par seconde (perso, je ne pense pas qu'un tel cluster existe etant donné le nombre d'opération a faire pour tester la validité d'un puzzle), il lui faudrait quand 10^491 s pour tous les tester et dans 3 ans il y a meme pas 100 millions de secondes (10^8s), ce qui veut dire que cet hypothetique ordinateur n'aura testé en 3 ans que 10^-480 % des puzzles possibles.
Donc non seulement le plus puissant des ordinateurs n'arrivera jamais a tester tous les puzzles avant que l'Univers ne se recontracte, mais il a encore tres peu de chance de trouver une seule solution valide en 3 ans.
Ce qui fera la difference, ce n'est pas la puissance de calcul brut de l'ordinateur, mais bien l'intelligence humaine qui se doit de reduire le nombre de possibilité de maniere a le rendre accessible pour un ordinateur (c'est d'ailleurs ce que l'on fait intuitivement en reconnaissant les coins et les bords).
Tout le monde a toutes ses chances.
Maintenant admettons que qqun ait accés à un super cluster ou calculateur. OK, mais il faut du temps pour coder un programme qui tirera parti du multithread (perte de temps), mais surtout, cette personne utilisera sans doute un ordinateur d'une societé ou d'un institut. Ce genre d'ordinateur est souvent fortement utilisé et cela m'étonnerai que qq'un puisse se le réserver plusieurs mois pour faire un calcul pour un jeu perso. Celui qui peut se payer un tel cluster (genre ordi pour la meteo ou les calculs de physique nucléaire), n'a vraiment pas besoin de souffrir autant pour gagner 2000000$.
On est vraiment tous sur le meme pieds d'égalité.
 
PS: le premier a été trouvé par des étudiants en math, donc des apprentis mathématiciens. Cela dit, on ne sait pas comment on procédés les autres trouveurs de solution.

Justement on ne parle pas de la puissance d'un ordinateur mais de la puissance de plusieurs centaines (voire milliers, j'ai pas le nombre exact de participants sous la main) de PC qui travaillent conjointement, ce qui est complètement différent.

Quelle difference entre un ordinateur et une multitude d'ordinateur ?
Moi je ne crois pas aux calculs partagés par internet: le reseau est trop lent. Et vu le nombre de possibilités, même avec 10 milliards d'ordinateurs tres puissants, le calcul de toutes les combinaisons prendrait des milliards d'années (sachant que l'age de l'Univers est estimé à 15 milliards d'année, ça laisse reveur). Donc une grosse puissance de calcul est incapable de venir a bout de se probleme. Désolé.

5 min pour les 16 pièces \o/

1er essai aussi

 
si tu ne connais rien en calculs distribués et en algorithmes (autre que la force brute), je te conseille de faire qqs recherches sur internet.

C'est justement parce que je m'y connais un petit peu, en maths et en programmation que je me permets de dire que la force brute n'a aucune chance.
Par contre, un algorithme bien pensé doit y arriver. Dans ce genre de problème, c'est l'algo qui nécessitera le moins d'opérations qui y arrivera. Ca me fait un peu penser au problème de la résolution d'un système linéaire à 100 équations à 100 inconnues. Avec la méthode du pivot de gauss il faut plusieurs milliards d'année à un ordi balèze pour y arriver alors qu'avec d'autres méthodes (certes plus sophistiquées) baser sur des calculs de determinants ou autres décompositions, quelques secondes suffisent avec un pentium 90. Le puzzle c'est la même histoire, la force brute c'est le pivot de Gauss, au vainqueur de trouver une autre voie.
 
Quant au calcul distribué, il ne faut pas lui attribuer des pouvoirs qu'il n'a pas. Les calculs massivement distribués sont difficiles à mettre en oeuvre. Lorsque le calcul est réalisé sur un cluster, une limite importante est la vitesse du réseau et surtout sa vitesse d'accès. Bref, ça ne s'improvise pas et ça coute tres cher. A moins de faire des ptites bidouilles comme seti et cie. Mais dans ce genre de cas, c'est pas la rapidité qui prime mais le partage des moyens.
 

les données propre au jeu font pas plusieurs kilos ^^
partitionner le problème ne me semble pas infaisable

mouais
le probleme du voyageur de commerce aussi ne fait quelque kilos, pourtant il n'est pas possible de trouver LA meilleure solution (à ma connaissance), mais seulement une tres bonne solution.
Quand tu parles de partition, tu veux faire de la classification ?

qu'entends tu par classification pour ce problème?
 
une approche naïve de partitionnement pourrait être:
 
découper le puzzle 4 (ou plus) calculer l'ensemble des solutions
avec toutes les pièces pour chaque partition.
 
distribuer l'ensemble des solutions sur le nombre de noeuds du systèmes
qui appliqueraient un algorithme comme ceux discutés précédemment (recuit simulé ? génétique?)
 
je n'ai pas calculé la faisabilité de cette méthode par exemple.
Qu'en penses tu ?

le fait de séparer les calculs sur plusieurs pc n'apporte rien algorithmiquement parlant.
 
l'approche recursive en divisant en 4 puzzle, eux memes decoupés en 4 puzzle reste beaucoup trop longue (c'est celle que j'ai mise en oeuvre, sur un 4x4 ou un 8x8 ca passe sans pbs, c'est en revanche ingérable pour un 16x16).
il faut tomber dans des considérations :
- algorithmiques : chercher a couper au maximum les cas 'invalides' le plus bas possible (c'est a dire avec un nombre minimum de piece posées). Pour ca j'ai tenté d'établir des "schémas" possible (ex : tu calcule l'ensemble des contours globaux du puzzle et tu en déduit une contrainte que doivent respecter les carrès 14x14 - l'objectif étant bien sur de travailler avec des schems bcp plus petit que 14x14), mais j'avou patiner un peu la dessus.
- mathematiques : se donner les moyens d'evaluer une solution : le fait que 254 pieces soient posées ne veut pas dire qu'on est plus proche de la solution (si on ne peut pas poser les 2 dernieres on aura aucun moyen de savoir combien de pieces sont fausses). donc il faut trouver une autre evaluation. la c'est de l'algebre je pense (faire des projections dans l'univers des solution possibles ?) mais j'avoue que mon pti cerveau n'as plus l'habitude de mouliner sur ces trucs la

que tu prennes le quart ou le contour du problème, le principe est identique ? ^^
 
(pour le contour c'est quand même plus intelligent ^^)

oui bien sur tu peux définir des schémas acceptable de 8*8, mais cela implique de trouver tous les ensemble de contour 9*9 possibles !
(en fait c'est l'inverse de l'approche 'naive' qui consiste a chercher tous les 8*8 et voir ensuite lesquels sont valides)
 
le pb est ensuite qu'un meme schema peut etre obtenu par des combinaisons de pieces differentes

le pb est ensuite qu'un meme schema peut etre obtenu par des combinaisons de pieces differentes[/quotemsg]
 
   bah ? uniquement si les pièces sont identiques !? je comprend pas.

non quand tu considère un carré 4x4 par exemple, la seule chose qui compte c'est le contour : le schéma représenté par les faces ; peu importe comment c'est organisé dedans (sinon tu descend au niveau de la pièce et non plus du carré).
c'est ca que j'appelle schema ! du coup un meme schema 4x4 peut etre obtenu par différentes combinaisons de pieces.

oki j'avais pas compris ça ^^

ce que j'appelle la classification, c'est comme ton partionnement, mais en s'arrangeant pour réduire les nombres de combinaisons. C'est ce qu'on fait intuitivement en séparant les coins, les bords et le centre. On peut peut etre découper plus, mais ça devient compliqué. Parce que si tu pars arbitrairement sur des 4x4 ou 8x8, tes petits puzzles risquent de se partager les même pieces donc tu ne réduits pas le nombre de combinaison.
 
Je partage sinon votre point de vue qui est de savoir très tot que la solution n'est pas viable. L'idéal serait qu'à partir d'une piece posée, l'algo magique te dises si le puzzle est encore possible avec le reste des pieces a poser. Le problème c'est que le fait que la solution ne soit pas unique n'arrange pas forcément.

Salut a tous!
 
Je vois que les discussions s emballent!
 
Puis je rapeller à tous qu'un rubik's Cube possede 43 252 003 274 489 856 000 possibilités! Pourtant avec le bon algo, n'importe qui peut le faire en moins d'une minute! Il faut donc se concentrer sur l'algorithme!
 
J'aimerais savoir si des gens ici ont un des puzzle indices afin de voir si on ne peut pas s arranger pour le resoudre en vitesse? ( tous les tests sur des 6*6 que nous avons fait se résolvent en quelques secondes, mais de la a faire un 16*16 il y a de la marche!)
 
Savez vous aussi si il existe une vraie communaute d entraide qui le fait pour le plaisir? Nous avons en effet pas mal de bonnes idées à partager a mon avis!
 
N'hesitez pas a me contacter

 
 
je vois pas le rapport
on sait ou doivent être les pièces du Rubiks Cube ^^

ce que je voulais dire, c est que ce n'est pas pasqu il y a énormement de possibilites qu on va mettre 3 ans pour le resoudre!
 
Je repondais a quelques messages plus haut qui disait
 

Vu que c'est ma citation, pour clarifier les choses c'était pour démontrer qu'il faut effectivement bosser sur l'algo et ne pas tenter le test de toutes les possibilités et ce quelque soit l'ordinateur. Voilà.

mathématiquement il a été démontré que si justement pour ce type de calcul qu'il n'existe pas d'algo exact rapide....

Pourrais tu donner les références de cette démonstration ?
N'oublie pas que le puzzle est un cas tres particulier de part sa pièce imposée et son jeu de pièces.
Par exemple, le cas hyper simple selon lequel il y a un unique motif est trivial. Il est très facile de trouver un algo exact et rapide.
Pourrais-tu donc préciser ta réponse ? Merci.

En fait on s'est peut etre mal compris:  
 
Un utilisateur disait il y a x milliards de milliards etc. de possibilités donc c'est impossible en le faisant par PC.  
Je lui dit que la bonne maniere d'avancer est de réduire ces possibilités par des constations logiques et un algorithme "malin" et que alors tout redeviendra résolvable par PC....
 
J ai comparé avec le rubik's cube qui possede certe bcp moins de possibilites! on a les 6 pieces centrales imposées et on doit faire correspondre des faces de couleurs! on est exactement dans le meme cas avec certes beaucoup moins de possibilités et plus de contraintes ( 1 seule piece imposée au lieu de 6 et 255 pieces restantes au lieu de 20, etc....)
 
Les rubik's cube est resolvable par n importe qui qui connait le "truc" ou le "bon algorithme" en 45 sec et en quelques millisecondes par PC...
 
 
 
Je ne dis pas que l'algorithme final sera trouvable tout de suite mais a terme on y arrivera....

Je suis de ton avis.
 
Mais c'est quand même balèze ...

pour "ce type de calcul" et "algo exact rapide".. mwé c'est du NP-C, et donc peut etre resolu avec une complexité polynomiale ?
suffit juste de trouver l'algo

je faisais effectivement référence à ce type de problème :
http://www.apprendre-en-ligne.net/ [...] ternity-ii
et  
http://fr.wikipedia.org/wiki/Th%C3 [...] exit%C3%A9  (cf le problème du P=NP) "Ceci fait qu'on conjecture cependant que les problèmes NP-complets ne sont pas solubles en un temps polynomial"

avec un algo déterministe
 
sur ton 2eme lien :

typiquement le cas du pb eternity

Ouais, en gros, le bon algo est celui qui réduit le nombre d'opérations pour arriver à trouver une solution.
Soit dit en passant, le fait qu'il n'y ait pas unicité de la solution complique la tache.

... Puzzles.Ao.Free.fr ...
J'en suis a 91% du plateau complet !!!
Mais est ce qu'il fait les indices ce truc ou pas .???

quelqu'un à déjé trouvé ?

Excusez-moi, mais y aurait pas comme un bin's ?
Les deux gars qui ont résolu le 1er Eternity étaient des étudiants en statistiques qui se sont aidé de 2 ordinateurs.
On peut donc en déduire qu'ils touchent leur bille en programmation.
Or ce sont précisément ces deux même gars qui ont été engagé pour réaliser le deuxième pour lequel il est stipulé qu'il ne peut pas être résolu par informatique !
D'après les différents forum que j'ai pu consulter, vous vous jetez tous comme un seul homme (ou une seul femme) sur vos ordi et vos algorithmes pour chercher la solution !
Ne faudrait t'il pas plutôt chercher la solution par les mathématiques (je n'ai hélas pas un niveau suffisant en math pour cela) ou par la logique ?
Y a-t'il des gens qui cherche de cette façon ?
Bon courage à tous !

Est-ce qu'un Mathématicien à trouvé

Ya encore des gens qui suivent ce topic? ^^
Perso j'ai achete le jeu des qu'il est sorti, j'ai essaye a la main et, apres avoir passe un pauqet d'heures a essayer de placer des pieces, j'ai laisse tomber un moment.
Mais la depuis une semaine je m'y suis remis, et je viens de finir de coder un algo de backtrack en C qui commence a bien marcher, bon je sais bien que meme en optimisant a fond et en le laissant tourner des semaines les chances sont infimes, mais apres tout on sait jamais
Je voulais savoir si certains ont des puzzles plus petit pour tester leurs programmes? (un 8x8 ca serait parfait)

 
Un petit deterrement de topic en regle ! Tu trouveras ton bonheur ici par exemple : http://www.eternity2.fr/benchmarks.
A mon avis coder un algo de backtrack est maintenant totalement inutile (a part evidement l'interet de coder par toi-meme et d'apprendre des trucs) vus le nombre de programmes deja existants, certains opensource donc bien optimisés a force.
De plus il est maintenant clair qu'un algo de ce style ne trouvera jamais la solution, il faut juste compter sur la chance, et si je me rappelle bien tu as des millions de fois plus de chances de gagner au Loto que de trouver une solution a Eternity II  avec un algo bruteforce  
La solution sera mathematique ou ne sera pas !

qui en doutait ? ^^
 
(meme le site qui proposait un prog de calcul partagé ferme, le gars se rend (enfin?) compte qu'ils ne trouveront jamais en bruteforce meme avec tous les ordis de la planète )

ya combien de solutions possibles ? ^^

20 000 ils disent sur le site... la grande question est de savoir comment ils ont calculé ca...
 
mais c'est rien comparé au 10^600 possibilité vues par le bruteforce

merci
Pour l'instant j'ai quand meme 178 pièces placées, en tournant depuis 2 semaine et sachant que j'ai encore pas mal de marge pour optimiser
Je vais aller tester leur benchmark pour voir