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
HOWTO: Solver usage
The basic steps for using the solver are as follows:
- In the Library block, open a puzzle library
- Select a puzzle, then select Puzzle > Solve
- This open the solver control dialog.
- From the first tab select thepuzzle you want to run in a batch
- From the settings tab, choose the solver configuration. For most users the default settings are ok. [More detail needed on config here]
- Click the 'Play' button to start the solver
- Double-click on the current solver puzzle to get a calculation report
- OR, select the current solver puzzle and click on the visualization button to bring up the visualizationsdialog. [More detail on the visualisation needed]
- 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.
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:
- Baseline I (v1.2.24)
- Baseline II (v1.3.33)
- Baseline II rev 1 (v1.3.33)
- Baseline II rev 2 (v1.3.39-beta )
- 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.
The following image is a cut-down class diagram of the basic solver design:
The key class here is
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.
SokoSolve is GPL,
all documentation (site included) is GFDL.
Contact web admin.