Sokolution - A powerful Sokoban solver

Sokolution is a powerful solver for Sokoban levels. The first version was released in may 2017 and this project is still active.

Since 18/11/2017, Sokolution has dethroned Takaken and can solve 3039 levels in the standard Large Test Suite. This was the world record !
Since 05/08/2020, Sokolution is beaten by Festival, the new solver by Yaron. Congratulations to Yaron for this fantastic solver !

If you don't know what is Sokoban game, follow these links :

Here, you can see the draft that explains algorithms and concepts inside Sokolution :

Here, you can see the statistics for each level :

Main features :

Sokolution - Last versions

Sokolution v4.02 - Download: Sokolution v4.02 Standalone version (Released 27/07/2020)

This version can optimally (push-optimality) solve 54 / 90 levels for XSokoban set (time limit : 10 minutes)
This version can optimally (push-optimality) solve 59 / 90 levels for XSokoban set (time limit : 60 minutes)

Description of the 3 script files :

Change log :

Sokolution v2.031 (plugin version) - Download: Sokolution v2.031 installer (Released 22/10/2019)

This version can solve 3050 / 3424 levels

The Multiple Pattern DataBase for X boxes called MPDB-X parameter is a pre-computation of deadlocks before the search starts. It computes all deadlocks created by X boxes. We can set the X value between 1 (very fast) and 4 (can be very long).

By default, Sokolution v2.X uses a MPDB-2 because it is really fast even for big levels and it helps a bit the solving process.

Please note that the MPDB generation cannot be canceled if you use YASC or Sokoban++.
Please also note that it uses threads and the CPU will be busy at 100% during this process.

Change log :

Sokolution - Old versions

Sokolution v4.01 - Download: Sokolution v4.01 Standalone version (Released 08/02/2020)

This version can optimally (push-optimality) solve 52 / 90 levels for XSokoban set in less than 10 minutes !
This version can optimally (push-optimality) solve 57 / 90 levels for XSokoban set within 60 minutes

Just a small update that improves the detection of frozen PI-Corral and fix small bugs that should not really impact the solving.

Description of the 3 script files :

Change log :

Sokolution v4.0 - Download: Sokolution v4.0 Standalone version (Released 29/01/2020)

This version can optimally (push-optimality) solve / 90 levels for XSokoban set in less than 10 minutes !
This version can optimally (push-optimality) solve 57 / 90 levels for XSokoban set within 60 minutes

This version comes with lots of enhancements and is a little faster than previous version due to a whole refactoring of the code.
I want to try a real challenge with this version : Being able to solve at least 48 Xsokoban levels within 10 minutes for push-optimal solutions !

Solving details for each package can be found at the end of this page.

Now, there are 3 script files :

Change log :

Sokolution v3.041 - Download: Sokolution v3.041 Standalone version (Released 27/12/2019)

This version can optimally (push-optimality) solve 50 / 90 levels for XSokoban set

This version handles the ability to bench levels inside a single file complying with the XSB standard. For this, use the sokolutionBenchSingleFile.bat file instead of Sokolution.bat file.

By default, Sokolution will read single-file packages inside ressources/packages/ directory. So put your .sok file inside this directory and then add the file name (without the sok extension) in the PACKAGE_LIST variable inside the sokolutionBenchSingleFile.bat file. There is an example with the xsokoban package. When launching by default the sokolutionBenchSingleFile.bat script, xsokoban levels will be benched using default parameters.

Change log :

Sokolution v3.04 - Download: Sokolution v3.04 Standalone version (Released 04/10/2019)

This version can optimally (push-optimality) solve 50 / 90 levels for XSokoban set

Change log :

Sokolution v3.03 - Download: Sokolution v3.03 Standalone version (Released 14/09/2019)

Just a small update of the previous version

Change log :

Sokolution v3.02 - Download: Sokolution v3.02 Standalone version (Released 06/09/2019)

I think it will be the last version of Sokolution because I done everything I can do on this project. This version is just because I have some 'lost' ideas that I would like to test.
Finally, many 'lost' ideas were definitely lost but it was worth it because I improved a bit all solving time and found few new solutions. By instance, I can solve Handmade #13 and Sokobet #23 with this version.

Finally results of this version are better than I expected ! See results below for details. Note that I didn't find Sokoban Perfect and Sokoban Revenge packages...

Change log :

Sokolution v3.01 - Download: Sokolution v3.01 Standalone version (Released 17/03/2019)

This version can solve 3053 / 3424 levels
This version can optimally (push-optimality) solve 37 / 90 levels for XSokoban set

Change log :

Sokolution v3.0 - Download: Sokolution v3.0 Standalone version (Released 26/02/2019 - Updated 28/02/2019)

This version can solve 3044 / 3424 levels
This version can optimally (push-optimality) solve 40 / 90 levels for XSokoban set

Small update that improves the statistic report in benching mode. Now, the number of pushes, moves and the XSB solution are displayed.

Use the config.bat file to launch benchs. This script is configured with default settings. Don't hesitate to modify them in order to fit with your needs.
While this is a x64 application, there is almost no limits for memory alloted to the solver. I tested up to 32 GB and it works fine.

Solver limits : Maximum level size: 256 floor squares. Maximum boxes: 255. No limits for level width and height.

Change log :

Sokolution v2.02 - Download: Sokolution v2.02 installer (Released 24/01/2019)

This version can solve 3041 / 3424 levels

Sokolution v2.01 - Download: Sokolution v2.01 installer (Released 18/11/2017)

This version can solve 3039 / 3424 levels

Sokolution v2.0 - Initial release: Sokolution beta v2.0 (Released 14/11/2017)

New world record ! Sokolution solved about 3026 levels, twenty-seven levels more than Takaken !

Sokolution 1.X - Old plugin versions

Download Sokolution v1.54t installer package compatible with YASC Host (Released 27/05/2017)

Download Sokolution v1.54t plugin compatible with YASC Host (Released 05/05/2017)

Note: There is a minor problem with Sokolution v1.54t when it runs under control of the YASC host. Indeed, some levels in SVEN collection are not solved when you run a full bench.
But if you try to solve individually these levels, they are solved...


Download Sokolution v1.53t compatible with YASC Host

Statistics for each set of levels

All statistics can be found on the Sokoban Wiki.

Time limit for all solvers : 600 sec (10 minutes) and memory limit : 1024 MB except for Sokolution v3.X due to x64 architecture that takes more memory so I ajust to 1500 MB.

Collection Author Levels Sokolution 1.53t Sokolution 1.54t Sokolution 2.0 Sokolution 2.01 Sokolution 2.02 Sokolution 2.03 Sokolution 3.0 Sokolution 3.01
AymericAymeric du Peloux282282282282282282282282282
BoxWorldVarious Authors1009494969696969797
Grigr2001Evgeny Grigoriev1009595969696969695
Grigr2002Evgeny Grigoriev403637393939393939
GrigrSpecialEvgeny Grigoriev404040404040404040
HollandDavid Holland816162636464646464
Kenyam Set AKenya Maruyama525051525252525252
MicrobanDavid W. Skinner155155155155155155155155155
Microban IIDavid W. Skinner135131134131132132132132132
SasquatchDavid W. Skinner503334353634363636
Sasquatch 2David W. Skinner502424292929313030
Sasquatch 3David W. Skinner502120232424242124
Sasquatch 4David W. Skinner503232343434343434
Sasquatch 5David W. Skinner503333363737373537
Sasquatch 6David W. Skinner503535363636363737
Sasquatch 7David W. Skinner503636393939393939
SokEvoLee J Haywood107107107107107107107107107
SokHardLee J Haywood163163163163163163163163163
SvenSven Egevad162313331359138913971401140614031408
XSokobanThinking Rabbit907272767676767777
Y.M. AutoYoshio Murase525252525252525252
Y.M. HandmadeYoshio Murase545353535353535353
TOTAL 3424 2938 2970 3026 3039 3041 3050 3044 3053

The parameters are changed for benchs below : Time limit : 600 sec | Memory limit : 12 GB

Collection Author Levels Sokolution 3.02 Sokolution 3.03 Sokolution 3.04 Sokolution 4.0 Sokolution 4.01
Aymeric Aymeric du Peloux 282 282 282 282 282 282
BoxWorld Various Authors 100 97 98 98 98 98
Grigr2001 Evgeny Grigoriev 100 96 96 96 96 96
Grigr2002 Evgeny Grigoriev 40 40 40 40 40 40
GrigrSpecial Evgeny Grigoriev 40 40 40 40 40 40
Holland David Holland 81 65 66 66 66 66
Mircoban David W. Skinner 155 155 155 155 155 155
Mircoban2 David W. Skinner 135 132 132 132 135 135
Sasquatch David W. Skinner 50 36 36 36 37 37
Sasquatch2 David W. Skinner 50 34 32 32 33 33
Sasquatch3 David W. Skinner 50 26 26 26 25 25
Sasquatch4 David W. Skinner 50 36 36 36 36 37
Sasquatch5 David W. Skinner 50 38 38 38 37 37
Sasquatch6 David W. Skinner 50 37 37 37 37 37
Sasquatch7 David W. Skinner 50 40 40 40 40 40
SokEvo Lee J Haywood 107 107 107 107 107 107
SokHard Lee J Haywood 163 163 163 163 163 163
Sven Sven Egevad 1911 1722 1721 1722 1724 1726
XSokoban Thinking Rabbit 90 80 80 82 81 81
Sokoban Perfect Thinking Rabbit 306 233 236 236 242 242
Sokoban Revenge Thinking Rabbit 306 214 216 216 231 229
Y.M. Auto Yoshio Murase 52 52 52 52 52 52
Y.M. Handmade Yoshio Murase 54 54 54 54 54 54
Sokobet Dr Foghs 29 22 24 24 24* 24*
IAG Dr Foghs 35 23 22 20 20 20
TOTAL 4336 3824 3829 3830 3855 3856

* Sokobet #14 can be solved within 600 seconds depending of the power of the computer


*** Copyright Florent DIEDLER 2017 - 2020 ***