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