Heiner's solver
From Sokoban Wiki
(new page) |
(++ basic method) |
||
| Line 27: | Line 27: | ||
* '''packet''': the moved objects (some say "box"), the "<code>$</code>" | * '''packet''': the moved objects (some say "box"), the "<code>$</code>" | ||
* '''harbor''': the packet destinations, the "<code>.</code>" | * '''harbor''': the packet destinations, the "<code>.</code>" | ||
| + | * '''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. | ||
Revision as of 23:33, 30 November 2010
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.
