Heiner's solver

From Sokoban Wiki

I'm Heiner, and have written a "brute force" sokoban solver. Here I want to tell about it.

How it started

The "initial ignition" was an idea about "deadlocks", i.e. their detection. Somewhere I had seen a hand written list of small patterns, used for deadlock detection. That appeared to me to be the wrong way. And I had an idea how to compute a certain class of deadlocks from basic principles. So I started to write a simple sokoban solver in Tcl. That was in 2007.

Later (still in 2007) I changed to ANSI-C, since Tcl wasn't fast enough, any more, and also used too much memory... my method needs large amounts of memory.

But the Tcl prototype was a good exercise to prepare the C program.

Legend

The terms I currently use, may be a bit non-standard. I found this Wiki in late 2010, and start to recognize that others use different words. While I have not switched, this is what I used up to now:

• actor: the moving "man", the warehouse keeper, the "@"
• packet: the moved objects (some say "box"), the "$"
• harbor: the packet destinations, the "."
• configuration: a complete description of a situation: location of actor and of all the packets

The basic solver method

I use the most simple method, not specific to sokoban. We have a starting configuration, a terminal configuration, and a definition of legal moves, which allows writing a function which maps any configuration to the set of legal successors.

This setup is enough for writing a simple puzzle solver, that searches for the shortest solution path.

We have a collection of pairs (configuration, distance), e.g. implemented as a hash table. We enter the pair (start-config, 0). Then, for increasing distance d, from all entries with distance d we generate all immediate successors, and those, which are not yet known, are entered with distance d+1. Each new entry is checked, whether it is the seeked for terminal configuration.

Once the terminal configuration is entered, we can stop the above, and extract a shortest solution path, starting with the terminal configuration, and searching for an immediate predecessor with a distance 1 smaller, and so on.