SokoDan, a sokoban puzzle solverYou will find on this page:
SokoDan aims at solving sokoban problems.
Sokoban is that game in which you have to push some gems (in red in the pictures) on some target cases (in green). You cannot pull a gem, and there must be nothing behind the gem you push: neither a wall nor another gem. See, you know what it is !
Version 2.1 is now available ! There have been several noticeable improvments, although not necessarly where it was most needed:
- An algorithm that is just as silly as before, but which is yet more efficient ;
- A dialog box shows the progression of the search and enables the user to interrupt it ;
- A few other user interface improvments ;
- And the use of automake, autoconf, gettext, glib, glade, gnome, ...
The main objective of sokoDan is clearly to use all these GNU development tools, and efficiency of the solving algorithm is secondary. The algorithm, precisely, is still that stupid: we consider all possible moves and we try them one by one. The only piece of intelligence resides in that we do not study the same position twice and we try to detect doomed situations. So you have been warned: with a "real-life" problem (not like in the screenshots), chances are that sokoDan takes several dozens of minutes to display a solution, or that you lose patience and interrupt the search. But if it finds a solution, it will be one of those requiring the minimal number of gem pushes.
A few indications: this program should compile and run under Linux and many Unices, GTK+ is required, GNOME is a plus but remains optional. This program won't work under Windows (c). One last thing: this program doesn't provide any sokoban level, but can solve the ones you provide (well, the small ones).