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