Bonjour,
j'ai un projet a réaliser en C++ sur le thème de ethernity II (site officiel : http://fr.eternityii.com/)

J'ouvre donc ce petit sujet non pas pour que vous me fassiez le code, mais pour proposé une réflexion commune des méthodes(incomplètes) permettant de résoudre ce type de puzzle.

Les premières méthodes dont j'aimerai discuter sont les suivantes :

• Un gradient bruité par une promenade aléatoire
• Un recuit simulé
• Un algorithme génétique
• Une colonie de fourmie

Au sujet du gradient bruité par une promenade aléatoire voici l'algorithme que j'ai trouvé :




NB: ci-dessous l'énoncé de mon projet pour information :

Héhé, j'avais déja pensé faire un algo pour résoudre Eternity, mais j'y ai pensé un bon moment, avec une méthode brute-force, je tombais sur un algo exponentiel.
Donc c'est rapé pour résoudre le grand puzzle. par contre, un tel algo peut marcher sur des petits puzzles.

Je vois que tu as recopié l'énoncé sur le topic, mais concrètement, qu'attends tu de nous ?
La méthode proposée n'est pas mal, en effet ! Surement plus efficace qu'une brute force (car il y a une sorte d'heuristique (les 70% dont tu parles)

Sinon, j'attire ton attention sur le mot "algorithme" qui n'a rien a voir avec la musique

Concrètement je n'attend pas de vous que vous fassiez mon projet, mais me donner des idées concernant les méthodes de solution d'un tel puzzle.
Il est de plus évident qu'aucune méthode n'est parfaites, et qu'elles n'aboutiront pas forcement à un résultat 100% correct.
En effet elles pourront aussi bien trouvée la solution du premier coup, ou mettre un infinité de temps pour la trouvé.
--> Le puzzle ethernity 2 possède à lui seul : 2 puissance 500 possibilités ( soit plus que le nombre d'atomes dans l'univers )

Lorsque j'utilise le mot "algorithme", il s'agit de sa définition au sens large(de mon point de vue):
Un algorithme peut être pour moi bien des choses :

• Un texte explicatif en français( ou un autre langage)
• Un schéma (basé ou non des sur "standards")
• Une forme normalisé d'instruction ( ex : p<- 1 // j'affecte 1 à ma variable P )
• ...

En gros cette une explication sous une forme choisie de l'auteur expliquant la méthode qu'il utiliserait pour résoudre se problème.

Concernant la méthode du gradian je l'ai recopier car je n'était pas sur que mon écriture soit complètement lisible sur le scan.
Je meterai bien sur en disponibilité mon code pour ceux qui voudrons le tester au fur est à mesure de son développement.

Citation : lolpyroman

Lorsque j'utilise le mot "algorithme", il s'agit de sa définition au sens large(de mon point de vue)

il pointe juste du doigt le fait que tu as écrit "algorythme"

oui bien vu, je vais le corriger.

heu je vais passer pour un bleu mais j'ai pas un moyen de corriger la faute dans mon titre?

Bon, je suis en ce moment même sur le cours d'optimisation, donc je ne suis pas certain que ce que je dirai sera éclairé ou juste.

Tout d'abord au niveau de l'évaluation d'une solution, il faut voir qu'il risque d'y avoir pas mal d'optimums locaux, c'est-à-dire de solution qui donne une évalutation bonne, mais pas la meilleur, et qui auraient tendance à "enfoncer" le programme vers cette solution, lui faisant croire que c'est la meilleur. Par exemple, toutes les solutions qui serait constituées, pour une partie, de la solution optimale pourrait être un optimum local. J'entend par là que si tu as, par exemple, un carré de 4 pièces qui appartient à la solution optimale, toute solution présentant ce carré de 4 pieces lui donnera une bonne évaluation, mais ne sera pas forcément proche de la solution optimale.

A ce titre, la colonie de fourmi ne me semble pas être la meilleur solution, il me semble que c'est une méthode qui a tendance à s'enfoncer dans les optimums locaux (il me semble que c'est ce que mon prof avait dit, mais je n'en suis plus sûr à 100%).

L'algo génétique me semble intéressant dans la mesure où il sous-entend une grand variété dans les solutions de base, ce qui permet de ne pas rester bloqué dans des optimums locaux.

Le recuit simulé, je connait pas encore, donc je pourrait pas t'en parler.

Au niveau de l'algo génétique, il faut voir quelles pourraient etre les croisements et les mutations que tu pourrais mettre. Par exemple, il serait intéressant, lorsque tu as une solution qui présente une zone avec pas mal de pièce correctement positionnées (c'est-à-dire que leurs bords correspondent), de créer de nouvelles solutions basées sur cette zone qui tu aurait déplacé, et autour de laquelle tu auras distribué de nouvelles pièces aléatoirement. Ca permet de garder la partie qui donne sa valeur à la solution et de recréer la partie qui en enleve.

Voilà, sinon, c'est intéressant comme projet dans le domaine, perso, je vais avoir à faire une distribution de bande de fréquence pour des points d'accès wifi pour optimiser la réception!

J'aimerai bien développer l'algorithme génétique.
J'ai encore besoin du peu de lecture avant d'être au point.

Néanmoins j'ai repéré quelque points particuliers :

• Les pièces n'auront que 4 cotés
• il peut y avoir X nombre de couleurs différente que peut prendre les faces d'une pièce.
• le plateau est un carre de n*n cases pour généré plus facilement un puzzle avant de le mélanger et tanter de le résoudre (tableau 4x4 = puzzle de 2*2)
• Certaine pièces seront peut être identique (2 couleurs -> 3 possibilités de pièces)

Pour l'instant je pense qu'il faudrait commencer par les bordures, et une fois une solution valide pour le placement de toutes les bordures trouvée, passer à la ranger suivante et ainsi de suite.
Donc revenir plus haut dès que l'on a vu que l'on ne peut résoudre le puzzle avec un tel début, ... .
On pourra déjà ainsi éliminer une partie des possibilités de placement.

Là ca sort du cadre de l'algo génétique. Avec ca, tu pourrais trouver une solution optimale. je me souviens plus comment s'appelle ce type de résolution, mais le fait de remonter d'une niveau de résolution quand tu as déterminé que tu ne pouvais pas avoir de solution finale dans la solution partielle s'appelle le backtracking.
Mais ca n'a pas grand chose à voir avec l'algo génétique dans la mesure où tu ne pourrais pas facilement utiliser les résultats de l'un pour l'autre, du moins je n'en ai pas l'impression. Ce que tu dis, d'utiliser cette méthode (le backtracking) pour éliminer des solutions impossible, je ne vois pas comment tu pourrais le réutiliser efficacement dans un algo génétique dans la mesure ou des mutations risque grandement de créer une solution que tu avais déterminée comme impossible, de meme qu'un croisement. Alors on peut se dire qu'il suffirait de vérifier qu'on ne tombe pas dans une solution impossible, mais ca obligerait à faire une liste de ces solutions impossibles et à parcourir toute cette liste pour vérifier que la solution que l'on tient n'en fait pas partie. Du coup, on perd énormément en temps d'exécution, qui est aussi un critère (important) de l'efficacité d'un algorithme.

A mon avis, l'algo génétique est une bonne solution, le probleme réside ensuite dans le fait de trouver les bonnes méthodes de croisement et de mutation.