SokoSolve | Solver

Introduction

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)

• Weighted Brute Force
• Forward & Reverse Searching
• Multi-Threaded - Optimised for dual-core processors
• Static Analysis for dead maps (unsolvable puzzle states)
  • Corner Analysis
  • 4x4 Box searching
  • Recess Analysis
• Visualisations - I have put more effort into the graphical display of the solver, than into the solver itself
  • Depth-first banded node display with colour coded state and weightings
  • Path to root, with immediate children
  • Bitmaps, with overlays
  • Weighting map
  • Outstanding evaluation list, at time of capture (entire node list is cloned)

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

• Converted atomic classes VectorInt, SizeInt from class to struct for huge memory and to a lesser degree speed savings.
• Baselined (history snapshot) each major improvement:
  1. Baseline I (v1.2.24)
  2. Baseline II (v1.3.33)
  3. Baseline II rev 1 (v1.3.33)
  4. Baseline II rev 2 (v1.3.39-beta )
  5. Baseline II rev 3 (v1.3.39-beta )
• Ubiquitous use of the strategy and factory pattern have made innovation very easy
• Abstraction of the SolverController allowed an easy transition to multi-threading
• Regular Microsoft Performance analysis (Tools > Performance Tools > Performance Wizard) has yielded unexpected and easy performance optimisations
• Multi-threading has been a great boon, but has required agressive locking on SolverNode. This greatly offsets the advantage of leveraging the second Core.

C# Implementation

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

The key class here is SolverController

Resources & References

• Erim Sever:  Sokoban Solver Information
• Sokoban at University of Alberta
• "Sokoban Automatic Solver" for windows  -- (Thanks Matthias)

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.

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