SokoDan, a sokoban puzzle solver

• Features
• Screenshots
• Download

Features

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.

The programming language is C and the graphical user interface uses GTK+ 1.2 and GNOME. Glade helped me creating the code of the interface.

Screenshots

Building a puzzle. Click on the tools, at the bottom, and "draw" the puzzle. The screenshot shows an example of such a puzzle. Clicking on "Solve" brings a dialog that shows search progress (you may interrupt the search in case it takes too long).	Once a solution is found, you can easily "browse" it. If given enough time, sokoDan yields one of the "best solutions", meaning one solution requiring the least number of gem pushes.

Download

sokoDan-2.1.tar.gz is available under the terms of the GNU GPL (free software). The README file contains, as always, some useful information.

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).