Home

SokoSolve: Sokoban Game and Solver

I have been intermittently working on Sokoban for years. It is fun to return every couple of years and breath some life back into it.

Sokoban solving is a interesting domain with very simple rules but with a search complexity comparible to Chess.

Sokoban-tinkering has been a good friend for at least 15 years. It has been a playground for breaking-in the latest C# language features. It provided me with welcome distraction while I nursed my mother during her cancer. It allowed me to learn about hi-performance techniques and deepend my comp-sci knowledge.

  • SouceForge (Dec-2007) The original project. Now legacy reference.
  • GitHub (Sep-2015) updated and moved to GitHub

The SourceForge Years (2007..2015)

This was my first dip into the open-source world. I wanted to explorer the solver, but also to build a user-base -- for which I need a game client and library. I moved onto other things before it got any real usage.

Game Client

Solver Graphs

Another beginning on GitHub (2015..present)

I dropped the game client and library - the whole user interface; and focussed instead on a modernised commandline-only solver. This involved real research in high-performance techniques, including:

  • Multi-threading saturation
  • Memory usage optimiations
  • Lock-less techniques

A confession: at the moment, I am not really interested in direclty solving more puzzles with more advanced algorythims (like ML, etc). Rather, I really want to understand the performance characteristics of the current brute-force implementation. My focus is to build a deep understanding of the low-level performance optimisation techniques.