SokoSolve | Solver


This is an automated solver for sokoban puzzles. In essence, the solver tries all possible moves until it stumbles apon the correct sequence for a puzzle solution.

It is the general nature of automated solvers that small (few crates, constrained space) can be solved very quickly (sub second), while larger maps will take a very long time indeed.

The solver was removed from the 1.2.* release series for a complete rewrite, it has been re-introduced in 1.3.*.

HOWTO: Solver usage

The basic steps for using the solver are as follows:

  1. In the Library block, open a puzzle library
  2. Select a puzzle, then select Puzzle > Solve
  3. This open the solver control dialog.
  4. From the first tab select thepuzzle you want to run in a batch
  5. From the settings tab, choose the solver configuration. For most users the default settings are ok. [More detail needed on config here]
  6. Click the 'Play' button to start the solver
  7. Double-click on the current solver puzzle to get a calculation report
  8. OR, select the current solver puzzle and click on the visualization button to bring up the visualizationsdialog. [More detail on the visualisation needed]
  9. Lastly, once the solver has completed the batch run, selection the 'HTML Report' option to save a solver report. These reports can be submitted to the SokoSolve project site.

Technical Architecture

Each node in the move tree is unique CrateMap (crate positions) and MoveMap (all possible player moves, without a push)

As of 1.3.33 I have not used any external sokoban knowledge, I have tried to stay away from any accepted wisdom (in part for the fun or it in part to see if I come up with anything fresh), no double much to my cost. This was easy as I had to implement all the basics anyway. I am quickly finding that additional improvements are requiring much more effort.

An unstructured list of C# optimisation findings

C# Implementation

The following image is a cut-down class diagram of the basic solver design:

Solver C# Class Diagram

The key class here is SolverController

Resources & References

Author & Appologies

Appologies... I am in the guts of the solver implementation, I will come back to this page and proof read. I promise. :-;

Guy Langston (Bitwacker), last updated Jan 2008. Logo

SokoSolve is GPL, all documentation (site included) is GFDL. Contact web admin.