Vous connaissez Sokoban, le jeu où il faut pousser les caisses sur les cibles?
Pour jouer: apt-get install ksokoban
J'ai écrit un solveur de sokoban: il tente de résoudre les niveaux tout seul.
Mon solver se nomme Pousse Caisse.
La page de Pousse Caisse:
http://linux.ensimag.fr/~acrequy/wiki/index.php/PousseCaisse(...)
La page est un wiki, tout le monde peut écrire.
Si vous êtes intéressés par les algorithmiques utilisés pour résoudre sokoban, écrivez moi:
alban.crequy AT apinc.org
Pousse Caisse est sous licence GNU GPL.
Journal Sokoban solver
12
fév.
2004
# Re: Sokoban solver
Posté par jigso . Évalué à 3.
Le script est là : http://sed.sourceforge.net/local/games/sokoban.sed(...)
Comme je le disais dans un des commentaire, on peut taper directement les déplacements khhhkkkkhkhhjhhjjjlllllllllllll et ensuite valider avec [Entrée]. Si les niveaux sont les mêmes il doit être possible de faire générer à ton programme la séquence et la faire exécuter directement.
[^] # Re: Sokoban solver
Posté par neil . Évalué à 1.
# Re: Sokoban solver
Posté par Julien Laumonier (site web personnel) . Évalué à 1.
je sais pas si ça peut t'interesser mais voici l'adresse d'un projet de recherche en plannification qui semble ressembler à la résolution du sokoban.
http://lpis.csd.auth.gr/projects/pacoplan/index.html(...)
Les sources sont fournies en C++ mais malheureusement, elles ne compilent pas sous linux car développées pour SUN :( Je pourrais contacter le gars qui l'a fait si ça t'interesse.
Julien
# Re: Sokoban solver
Posté par Erwan . Évalué à 1.
Ca peut peut-etre servir de chercher la classe de complexite, genre voir s'il est NP-complet ou pas.
Ensuite, il y a peut-etre encore une optimisation possible: noter chaque position pour voir lesquelles sont "meilleures" que les autres (en fonction de la distance des caisses au but et de leur mobilite, par exemple) afin de commencer par explorer les branches qui ont le plus de chance de mener a la solution.
[^] # Re: Sokoban solver
Posté par Alban Crequy (site web personnel) . Évalué à 1.
Sokoban has been shown to be PSPACEcomplete by Culberson.
http://www.cs.ualberta.ca/~joe/TR/TR97-02.ps(...)
# Re: Sokoban solver
Posté par Antoine Reilles (site web personnel) . Évalué à 1.
http://pauillac.inria.fr/pipermail/coq-club/2003/001021.html(...)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.