Sokodan, solveur de problèmes de sokoban

• Principe et description
• Captures d'écran
• Téléchargement

Principe et description

SokoDan tente de résoudre les problèmes de sokoban.

Sokoban est le jeu qui consiste à pousser des « pierres » (en rouge sur les images) sur des cases « cible » (en vert). Votre gus ne peut que pousser, et seulement une pierre qui n'a rien derrière : ni mur, ni même une autre pièce. Vous voyez bien que vous connaissiez!

La version 2.1 est maintenant disponible! Il y a plusieurs améliorations notables, mais pas forcément là où c'était le plus nécessaire :

• Un algorithme tout aussi bête mais plus efficace tout de même que le précédent ;
• Une boîte de dialogue montrant la progression de la recherche, et offrant la possibilité de l'interrompre ;
• Quelques autres améliorations de l'interface ;
• Et toujours utilisation d'automake, autoconf, gettext, glib, glade, gnome...

L'objectif premier de sokoDan est clairement d'utiliser tous ces outils GNU, et pas forcément de résoudre les problèmes de sokoban de façon efficace. L'algorithme est toujours aussi stupide : on considère tous les coups possibles et on les essaie consciencieusement. Le seul raffinement consiste à ne pas étudier 2 fois la même position et à détecter certaines positions condamnées. Donc vous êtes prévenus : avec un problème réel (pas comme sur les captures d'écran) il y a des chances pour que sokoDan mette plusieurs dizaines de minutes pour sortir une solution, voire que vous n'ayiez pas la patience d'attendre la fin de l'algorithme. Mais s'il trouve, il donne une solution parmi les meilleures (nombre de déplacements de pierre minimal).

Le langage est le C et l'interface graphique réalisée avec GTK+ 1.2 et GNOME. Glade m'a aidé à écrire le code cette interface.

Captures d'écran

Création du problème. Cliquez sur les outils, en bas, et « dessinez » le problème. La capture d'écran montre un exemple de problème à résoudre. Cliquer sur « Résoudre » amène une boite de dialogue qui vous informera sur l'avancement de la recherche (que vous pourrez éventuellement interrompre).	Parcours de la solution trouvée. Lorsqu'on lui laisse le temps de trouver une solution, sokoDan trouve une « meilleure solution », c'est à dire parmi les solutions au plus petit nombre de déplacements de pièces.

Téléchargement

sokoDan-2.1.tar.gz est disponible sous les termes de la license GNU (logiciel libre). Le fichier README contient (comme toujours ;-) plein d'info utiles.

Quelques précisions : ce programme devrait fonctionner sous Linux, ainsi que sous pas mal d'Unix, avec GTK+ installé (GNOME est un plus mais n'est pas indispensable). En tout cas, il ne fonctionnera pas sous Windows (c). D'autre part, ce programme ne propose pas de niveaux mais permet de les résoudre (enfin, pour les petits problèmes).