Sokoban Wiki - User contributions [en]

Solver Statistics

2026-08-09T19:44:41Z

Matthias Meger: /* General benchmarking information */ new JSoko version

A Sokoban solver program is a program that ''tries to'' solve Sokoban levels. There are several solver programs available. (See [[Links#Sokoban Solvers |Sokoban solvers]].)

Solver programs may have different objectives:
# Find any solution
# Find push optimal solutions
# Find push optimal solutions with best moves
# Find move optimal solutions
# Find move optimal solutions with best pushes

Given the computational complexity of these tasks, a solver program is usually designed for just finding any solution. If a solution is to be optimized, an optimizer program can be used. (See [[Links#Sokoban Solvers |Optimizers]].)

The statistics presented here provide a picture of what the best freely available Sokoban solvers can do. 
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

== General benchmarking information ==

For practical reasons, almost all tests have been performed with a 10 minutes time limit. The tests are, however, not a 10 minutes contest but a showcase for what the solvers can do, so other time limits are entirely feasible.

The hardware used for the tests is a standard PC with a modern operating system (64bit).

Tests are performed with default solver settings.

{| class="soko-table feature-list"
!Solver || Version || Author || Architecture || CPU usage || Source code available || More info

|-
|[https://festival-solver.site/ Festival] || 3.1 || Yaron Shoham || 64bit || 8 threads || [https://festival-solver.site/ Festival 3.1] || [https://festival-solver.site/ Website with papers about the solver]

|-
|[http://sokolution.infinityfreeapp.com/ Sokolution] || 7.32 || Florent Diedler || 64bit || all threads || no || [[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver | Sokoban solver "scribbles" by Florent Diedler]]

|-
|[https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken] || 7.4 || Ken'ichiro Takahashi (takaken) || 64bit || 2 threads || no || [https://computerpuzzle.net/puzzle/sokoban/ver731/index.html Description of the used algorithms]

|-
|[https://festival-solver.site/curry/ Curry] || 0.3 || Yaron Shoham || 64bit || 1 thread || [https://festival-solver.site/curry/ Curry 0.3] || [https://festival-solver.site/curry/ Website with paper about the solver]

|-
|[https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || 7.0 beta 1 || 葛永 (Ge Yong) || 64bit || 1 thread || no || [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch Website of BoxSearch]

|-
|[https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || 2.153 || Brian Damgaard || 32bit + 64bit || 1 thread || [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS 2.153] || [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver | Sokoban solver "scribbles" by Brian Damgaard]]

|-
|[https://jsokoapplet.sourceforge.io/ JSoko] || 2.29 || Matthias Meger || 64bit || 1 thread || [https://sourceforge.net/projects/jsokoapplet/files/JSoko/Version%202.29/ JSoko 2.29] || [[Solver | Solver information]]
|-
|[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || 1.0 || Andreas Junghanns || 32bit || 1 thread || [https://webdocs.cs.ualberta.ca/~games/Sokoban/Src/ RS] || [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= Rolling Stone papers]

|}

Contact: SokobanoWiki@gmail.com

== XSokoban Test Suite ==

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

{| class="soko-table"
|-
! colspan="11" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width= "90" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width= "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [[JSoko Solver | JSoko]]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]
| width=" 80" | [https://festival-solver.site/curry/ Curry ]
| width=" 80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]




|- align="right"
| align="left" bgcolor="#f1efe5" | [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/ XSokoban]
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 59*]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Takaken%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/YASS%20-%20XSokoban.html 89]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban | 67 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Sokolution%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Curry%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Festival%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/BoxSearch%20-%20XSokoban.html '''89''']

|}

*) 59 solved puzzles according to paper [https://sokoban.dk/wp-content/uploads/2016/02/Single-Agent.pdf Sokoban Enhancing general single-agent search methods using domain knowledge]

{| class="soko-table"
|-


! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width=" 80" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width=" 80" | [http://www.ijcai.org/Abstract/16/100 Pereira et al.]
| width=" 80" | [http://sourceforge.net/projects/jsokoapplet/ JSoko]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]


|- align="right"
| align="left" bgcolor="#f1efe5" | XSokoban
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]
| [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/JSoko%20-%20XSokoban.html 25]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/Sokolution%20-%20XSokoban.html '''73''']

|}

The statistic shows that Sokolution is by far the best solver when searching for push optimal solutions.

== Large Test Suite ==

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is intended to be a "Large Standard Test Suite" for Sokoban solver programs.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 3272 
| '''3208''' 
| 3207 
| 2953 
| 2899 
| 2749 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/LargeTestSuite/ Click here to see the detailed results for the Large Test Suite].'''

Download the entire test suite [https://sourceforge.net/projects/sokoban-solver-statistics/files/Large%20Test%20Suite.zip/download here] or the individual level sets from [http://sokobano.de/de/levels.php www.sokobano.de].

== Open Test Suite ==

The statistics shows the results for the leading Sokoban solvers for various level collections. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

This test suite may be changed by adding new level collections from time to time.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Open Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 10043 
| '''9596''' 
| 9516 
| 8721 
| 8339 
| 8111 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/ Click here to see the detailed results for the Open Test Suite].'''

[https://sokoban-solver-statistics.sourceforge.io/statistics/Sokolution/ Comparison for the Open Test Suite for all Sokolution versions].

== Push-optimal Test Suite ==

The "Push-optimal Test Suite" comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

For this test suite the solvers must solve the puzzles push optimal.

{| class="soko-table"
|-
! colspan="6" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 1588 
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ '''1529'''] 
|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ Click here to see the detailed results for the Push-Optimal Test Suite].'''

== GroupEffort Test Suite ==

The only reason for benchmarking the GroupEffort test suite is to demonstrate the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

{| class="soko-table"
|-
! colspan="8" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels




|- bgcolor="#f1efe5" align="center" 
| width = "115" align="left" | Collection
| width = "80" | Levels
| width = "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
| width = "80" | [https://festival-solver.site/ Festival]
| width = "80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width = "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width = "80" | [https://sourceforge.net/projects/jsokoapplet/ JSoko]
| width = "80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]




|- align="right"
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
| 200
| 196 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Small-Set | '''200''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Small-Set | 192 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Small-Set | 180 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Small-Set | 191 (b) ]]




|- align="right"
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
| 2851
| 1566 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Large-Set | '''2766''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | 2471 (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Large-Set | 2462 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Large-Set | 2165 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Large-Set | 2260 (b) ]]




|- align="right" bgcolor="#f1efe5" align="right"
| align="left"| Total
| 3051 
| 1762 
| '''2966''' 
| 2671 
| 2654 
| 2345 
| 2471 
|}

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

== Disclaimer ==

Sokoban
=======
 
Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan
 
License
=======
 
Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met:
 
* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
and/or other materials provided with the distribution.
 
Credits (in no particular order)
================================
 
CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown
 
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown
 
Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown
 
Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/
 
SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: https://ljhaywood.uk/games/sokoban/
 
Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown
 
Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/
 
Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html
 
JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@mail.de
Web site: https://jsokoapplet.sourceforge.io/
 
Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: https://computerpuzzle.net/english/sokoban/ver740/index.html
 
YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
Web site: https://sourceforge.net/projects/sokobanyasc/
 
Sokoban YASC
Copyright (C) 2001-2020 by Brian Damgaard
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site: http://ygp.orgfree.com/sokoban.html
 
XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown
 
Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://sokolution.infinityfreeapp.com/
 
Festival
Copyright (C) 2020 by Yaron Shoham
Web site: https://festival-solver.site/
 
Trademarks
==========
 
Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.
 
Contact
=======
 
E-mail: sokobanowiki@gmail.com

Solver Statistics

2026-08-09T19:44:17Z

Matthias Meger: /* General benchmarking information */ new JSoko version

A Sokoban solver program is a program that ''tries to'' solve Sokoban levels. There are several solver programs available. (See [[Links#Sokoban Solvers |Sokoban solvers]].)

Solver programs may have different objectives:
# Find any solution
# Find push optimal solutions
# Find push optimal solutions with best moves
# Find move optimal solutions
# Find move optimal solutions with best pushes

Given the computational complexity of these tasks, a solver program is usually designed for just finding any solution. If a solution is to be optimized, an optimizer program can be used. (See [[Links#Sokoban Solvers |Optimizers]].)

The statistics presented here provide a picture of what the best freely available Sokoban solvers can do. 
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

== General benchmarking information ==

For practical reasons, almost all tests have been performed with a 10 minutes time limit. The tests are, however, not a 10 minutes contest but a showcase for what the solvers can do, so other time limits are entirely feasible.

The hardware used for the tests is a standard PC with a modern operating system (64bit).

Tests are performed with default solver settings.

{| class="soko-table feature-list"
!Solver || Version || Author || Architecture || CPU usage || Source code available || More info

|-
|[https://festival-solver.site/ Festival] || 3.1 || Yaron Shoham || 64bit || 8 threads || [https://festival-solver.site/ Festival 3.1] || [https://festival-solver.site/ Website with papers about the solver]

|-
|[http://sokolution.infinityfreeapp.com/ Sokolution] || 7.32 || Florent Diedler || 64bit || all threads || no || [[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver | Sokoban solver "scribbles" by Florent Diedler]]

|-
|[https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken] || 7.4 || Ken'ichiro Takahashi (takaken) || 64bit || 2 threads || no || [https://computerpuzzle.net/puzzle/sokoban/ver731/index.html Description of the used algorithms]

|-
|[https://festival-solver.site/curry/ Curry] || 0.3 || Yaron Shoham || 64bit || 1 thread || [https://festival-solver.site/curry/ Curry 0.3] || [https://festival-solver.site/curry/ Website with paper about the solver]

|-
|[https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || 7.0 beta 1 || 葛永 (Ge Yong) || 64bit || 1 thread || no || [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch Website of BoxSearch]

|-
|[https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || 2.153 || Brian Damgaard || 32bit + 64bit || 1 thread || [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS 2.153] || [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver | Sokoban solver "scribbles" by Brian Damgaard]]

|-
|[https://jsokoapplet.sourceforge.io/ JSoko] || 2.29 || Matthias Meger || 64bit || 1 thread || [https://sourceforge.net/projects/jsokoapplet/files/JSoko/Version%202.27/ JSoko 2.29] || [[Solver | Solver information]]
|-
|[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || 1.0 || Andreas Junghanns || 32bit || 1 thread || [https://webdocs.cs.ualberta.ca/~games/Sokoban/Src/ RS] || [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= Rolling Stone papers]

|}

Contact: SokobanoWiki@gmail.com

== XSokoban Test Suite ==

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

{| class="soko-table"
|-
! colspan="11" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width= "90" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width= "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [[JSoko Solver | JSoko]]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]
| width=" 80" | [https://festival-solver.site/curry/ Curry ]
| width=" 80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]




|- align="right"
| align="left" bgcolor="#f1efe5" | [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/ XSokoban]
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 59*]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Takaken%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/YASS%20-%20XSokoban.html 89]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban | 67 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Sokolution%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Curry%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Festival%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/BoxSearch%20-%20XSokoban.html '''89''']

|}

*) 59 solved puzzles according to paper [https://sokoban.dk/wp-content/uploads/2016/02/Single-Agent.pdf Sokoban Enhancing general single-agent search methods using domain knowledge]

{| class="soko-table"
|-


! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width=" 80" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width=" 80" | [http://www.ijcai.org/Abstract/16/100 Pereira et al.]
| width=" 80" | [http://sourceforge.net/projects/jsokoapplet/ JSoko]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]


|- align="right"
| align="left" bgcolor="#f1efe5" | XSokoban
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]
| [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/JSoko%20-%20XSokoban.html 25]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/Sokolution%20-%20XSokoban.html '''73''']

|}

The statistic shows that Sokolution is by far the best solver when searching for push optimal solutions.

== Large Test Suite ==

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is intended to be a "Large Standard Test Suite" for Sokoban solver programs.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 3272 
| '''3208''' 
| 3207 
| 2953 
| 2899 
| 2749 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/LargeTestSuite/ Click here to see the detailed results for the Large Test Suite].'''

Download the entire test suite [https://sourceforge.net/projects/sokoban-solver-statistics/files/Large%20Test%20Suite.zip/download here] or the individual level sets from [http://sokobano.de/de/levels.php www.sokobano.de].

== Open Test Suite ==

The statistics shows the results for the leading Sokoban solvers for various level collections. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

This test suite may be changed by adding new level collections from time to time.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Open Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 10043 
| '''9596''' 
| 9516 
| 8721 
| 8339 
| 8111 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/ Click here to see the detailed results for the Open Test Suite].'''

[https://sokoban-solver-statistics.sourceforge.io/statistics/Sokolution/ Comparison for the Open Test Suite for all Sokolution versions].

== Push-optimal Test Suite ==

The "Push-optimal Test Suite" comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

For this test suite the solvers must solve the puzzles push optimal.

{| class="soko-table"
|-
! colspan="6" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 1588 
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ '''1529'''] 
|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ Click here to see the detailed results for the Push-Optimal Test Suite].'''

== GroupEffort Test Suite ==

The only reason for benchmarking the GroupEffort test suite is to demonstrate the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

{| class="soko-table"
|-
! colspan="8" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels




|- bgcolor="#f1efe5" align="center" 
| width = "115" align="left" | Collection
| width = "80" | Levels
| width = "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
| width = "80" | [https://festival-solver.site/ Festival]
| width = "80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width = "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width = "80" | [https://sourceforge.net/projects/jsokoapplet/ JSoko]
| width = "80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]




|- align="right"
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
| 200
| 196 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Small-Set | '''200''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Small-Set | 192 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Small-Set | 180 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Small-Set | 191 (b) ]]




|- align="right"
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
| 2851
| 1566 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Large-Set | '''2766''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | 2471 (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Large-Set | 2462 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Large-Set | 2165 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Large-Set | 2260 (b) ]]




|- align="right" bgcolor="#f1efe5" align="right"
| align="left"| Total
| 3051 
| 1762 
| '''2966''' 
| 2671 
| 2654 
| 2345 
| 2471 
|}

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

== Disclaimer ==

Sokoban
=======
 
Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan
 
License
=======
 
Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met:
 
* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
and/or other materials provided with the distribution.
 
Credits (in no particular order)
================================
 
CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown
 
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown
 
Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown
 
Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/
 
SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: https://ljhaywood.uk/games/sokoban/
 
Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown
 
Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/
 
Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html
 
JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@mail.de
Web site: https://jsokoapplet.sourceforge.io/
 
Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: https://computerpuzzle.net/english/sokoban/ver740/index.html
 
YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
Web site: https://sourceforge.net/projects/sokobanyasc/
 
Sokoban YASC
Copyright (C) 2001-2020 by Brian Damgaard
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site: http://ygp.orgfree.com/sokoban.html
 
XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown
 
Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://sokolution.infinityfreeapp.com/
 
Festival
Copyright (C) 2020 by Yaron Shoham
Web site: https://festival-solver.site/
 
Trademarks
==========
 
Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.
 
Contact
=======
 
E-mail: sokobanowiki@gmail.com

Solver Statistics

2026-05-04T19:33:13Z

Matthias Meger: /* General benchmarking information */ New JSoko version

A Sokoban solver program is a program that ''tries to'' solve Sokoban levels. There are several solver programs available. (See [[Links#Sokoban Solvers |Sokoban solvers]].)

Solver programs may have different objectives:
# Find any solution
# Find push optimal solutions
# Find push optimal solutions with best moves
# Find move optimal solutions
# Find move optimal solutions with best pushes

Given the computational complexity of these tasks, a solver program is usually designed for just finding any solution. If a solution is to be optimized, an optimizer program can be used. (See [[Links#Sokoban Solvers |Optimizers]].)

The statistics presented here provide a picture of what the best freely available Sokoban solvers can do. 
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

== General benchmarking information ==

For practical reasons, almost all tests have been performed with a 10 minutes time limit. The tests are, however, not a 10 minutes contest but a showcase for what the solvers can do, so other time limits are entirely feasible.

The hardware used for the tests is a standard PC with a modern operating system (64bit).

Tests are performed with default solver settings.

{| class="soko-table feature-list"
!Solver || Version || Author || Architecture || CPU usage || Source code available || More info

|-
|[https://festival-solver.site/ Festival] || 3.1 || Yaron Shoham || 64bit || 8 threads || [https://festival-solver.site/ Festival 3.1] || [https://festival-solver.site/ Website with papers about the solver]

|-
|[http://sokolution.infinityfreeapp.com/ Sokolution] || 7.32 || Florent Diedler || 64bit || all threads || no || [[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver | Sokoban solver "scribbles" by Florent Diedler]]

|-
|[https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken] || 7.4 || Ken'ichiro Takahashi (takaken) || 64bit || 2 threads || no || [https://computerpuzzle.net/puzzle/sokoban/ver731/index.html Description of the used algorithms]

|-
|[https://festival-solver.site/curry/ Curry] || 0.3 || Yaron Shoham || 64bit || 1 thread || [https://festival-solver.site/curry/ Curry 0.3] || [https://festival-solver.site/curry/ Website with paper about the solver]

|-
|[https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || 7.0 beta 1 || 葛永 (Ge Yong) || 64bit || 1 thread || no || [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch Website of BoxSearch]

|-
|[https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || 2.153 || Brian Damgaard || 32bit + 64bit || 1 thread || [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS 2.153] || [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver | Sokoban solver "scribbles" by Brian Damgaard]]

|-
|[https://jsokoapplet.sourceforge.io/ JSoko] || 2.28 || Matthias Meger || 64bit || 1 thread || [https://sourceforge.net/projects/jsokoapplet/files/JSoko/Version%202.27/ JSoko 2.28] || [[Solver | Solver information]]
|-
|[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || 1.0 || Andreas Junghanns || 32bit || 1 thread || [https://webdocs.cs.ualberta.ca/~games/Sokoban/Src/ RS] || [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= Rolling Stone papers]

|}

Contact: SokobanoWiki@gmail.com

== XSokoban Test Suite ==

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

{| class="soko-table"
|-
! colspan="11" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width= "90" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width= "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [[JSoko Solver | JSoko]]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]
| width=" 80" | [https://festival-solver.site/curry/ Curry ]
| width=" 80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]




|- align="right"
| align="left" bgcolor="#f1efe5" | [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/ XSokoban]
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 59*]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Takaken%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/YASS%20-%20XSokoban.html 89]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban | 67 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Sokolution%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Curry%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Festival%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/BoxSearch%20-%20XSokoban.html '''89''']

|}

*) 59 solved puzzles according to paper [https://sokoban.dk/wp-content/uploads/2016/02/Single-Agent.pdf Sokoban Enhancing general single-agent search methods using domain knowledge]

{| class="soko-table"
|-


! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width=" 80" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width=" 80" | [http://www.ijcai.org/Abstract/16/100 Pereira et al.]
| width=" 80" | [http://sourceforge.net/projects/jsokoapplet/ JSoko]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]


|- align="right"
| align="left" bgcolor="#f1efe5" | XSokoban
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]
| [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/JSoko%20-%20XSokoban.html 25]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/Sokolution%20-%20XSokoban.html '''73''']

|}

The statistic shows that Sokolution is by far the best solver when searching for push optimal solutions.

== Large Test Suite ==

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is intended to be a "Large Standard Test Suite" for Sokoban solver programs.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 3272 
| '''3208''' 
| 3207 
| 2953 
| 2899 
| 2749 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/LargeTestSuite/ Click here to see the detailed results for the Large Test Suite].'''

Download the entire test suite [https://sourceforge.net/projects/sokoban-solver-statistics/files/Large%20Test%20Suite.zip/download here] or the individual level sets from [http://sokobano.de/de/levels.php www.sokobano.de].

== Open Test Suite ==

The statistics shows the results for the leading Sokoban solvers for various level collections. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

This test suite may be changed by adding new level collections from time to time.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Open Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 10043 
| '''9596''' 
| 9516 
| 8721 
| 8339 
| 8111 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/ Click here to see the detailed results for the Open Test Suite].'''

[https://sokoban-solver-statistics.sourceforge.io/statistics/Sokolution/ Comparison for the Open Test Suite for all Sokolution versions].

== Push-optimal Test Suite ==

The "Push-optimal Test Suite" comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

For this test suite the solvers must solve the puzzles push optimal.

{| class="soko-table"
|-
! colspan="6" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 1588 
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ '''1529'''] 
|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ Click here to see the detailed results for the Push-Optimal Test Suite].'''

== GroupEffort Test Suite ==

The only reason for benchmarking the GroupEffort test suite is to demonstrate the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

{| class="soko-table"
|-
! colspan="8" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels




|- bgcolor="#f1efe5" align="center" 
| width = "115" align="left" | Collection
| width = "80" | Levels
| width = "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
| width = "80" | [https://festival-solver.site/ Festival]
| width = "80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width = "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width = "80" | [https://sourceforge.net/projects/jsokoapplet/ JSoko]
| width = "80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]




|- align="right"
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
| 200
| 196 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Small-Set | '''200''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Small-Set | 192 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Small-Set | 180 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Small-Set | 191 (b) ]]




|- align="right"
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
| 2851
| 1566 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Large-Set | '''2766''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | 2471 (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Large-Set | 2462 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Large-Set | 2165 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Large-Set | 2260 (b) ]]




|- align="right" bgcolor="#f1efe5" align="right"
| align="left"| Total
| 3051 
| 1762 
| '''2966''' 
| 2671 
| 2654 
| 2345 
| 2471 
|}

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

== Disclaimer ==

Sokoban
=======
 
Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan
 
License
=======
 
Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met:
 
* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
and/or other materials provided with the distribution.
 
Credits (in no particular order)
================================
 
CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown
 
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown
 
Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown
 
Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/
 
SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: https://ljhaywood.uk/games/sokoban/
 
Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown
 
Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/
 
Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html
 
JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@mail.de
Web site: https://jsokoapplet.sourceforge.io/
 
Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: https://computerpuzzle.net/english/sokoban/ver740/index.html
 
YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
Web site: https://sourceforge.net/projects/sokobanyasc/
 
Sokoban YASC
Copyright (C) 2001-2020 by Brian Damgaard
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site: http://ygp.orgfree.com/sokoban.html
 
XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown
 
Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://sokolution.infinityfreeapp.com/
 
Festival
Copyright (C) 2020 by Yaron Shoham
Web site: https://festival-solver.site/
 
Trademarks
==========
 
Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.
 
Contact
=======
 
E-mail: sokobanowiki@gmail.com

Solver Statistics

2026-04-24T18:36:56Z

Matthias Meger: New JSoko version

A Sokoban solver program is a program that ''tries to'' solve Sokoban levels. There are several solver programs available. (See [[Links#Sokoban Solvers |Sokoban solvers]].)

Solver programs may have different objectives:
# Find any solution
# Find push optimal solutions
# Find push optimal solutions with best moves
# Find move optimal solutions
# Find move optimal solutions with best pushes

Given the computational complexity of these tasks, a solver program is usually designed for just finding any solution. If a solution is to be optimized, an optimizer program can be used. (See [[Links#Sokoban Solvers |Optimizers]].)

The statistics presented here provide a picture of what the best freely available Sokoban solvers can do. 
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

== General benchmarking information ==

For practical reasons, almost all tests have been performed with a 10 minutes time limit. The tests are, however, not a 10 minutes contest but a showcase for what the solvers can do, so other time limits are entirely feasible.

The hardware used for the tests is a standard PC with a modern operating system (64bit).

Tests are performed with default solver settings.

{| class="soko-table feature-list"
!Solver || Version || Author || Architecture || CPU usage || Source code available || More info

|-
|[https://festival-solver.site/ Festival] || 3.1 || Yaron Shoham || 64bit || 8 threads || [https://festival-solver.site/ Festival 3.1] || [https://festival-solver.site/ Website with papers about the solver]

|-
|[http://sokolution.infinityfreeapp.com/ Sokolution] || 7.32 || Florent Diedler || 64bit || all threads || no || [[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver | Sokoban solver "scribbles" by Florent Diedler]]

|-
|[https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken] || 7.4 || Ken'ichiro Takahashi (takaken) || 64bit || 2 threads || no || [https://computerpuzzle.net/puzzle/sokoban/ver731/index.html Description of the used algorithms]

|-
|[https://festival-solver.site/curry/ Curry] || 0.3 || Yaron Shoham || 64bit || 1 thread || [https://festival-solver.site/curry/ Curry 0.3] || [https://festival-solver.site/curry/ Website with paper about the solver]

|-
|[https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || 7.0 beta 1 || 葛永 (Ge Yong) || 64bit || 1 thread || no || [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch Website of BoxSearch]

|-
|[https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || 2.153 || Brian Damgaard || 32bit + 64bit || 1 thread || [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS 2.153] || [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver | Sokoban solver "scribbles" by Brian Damgaard]]

|-
|[https://jsokoapplet.sourceforge.io/ JSoko] || 2.27 || Matthias Meger || 64bit || 1 thread || [https://sourceforge.net/projects/jsokoapplet/files/JSoko/Version%202.27/ JSoko 2.27] || [[Solver | Solver information]]
|-
|[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || 1.0 || Andreas Junghanns || 32bit || 1 thread || [https://webdocs.cs.ualberta.ca/~games/Sokoban/Src/ RS] || [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= Rolling Stone papers]

|}

Contact: SokobanoWiki@gmail.com

== XSokoban Test Suite ==

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

{| class="soko-table"
|-
! colspan="11" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width= "90" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width= "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [[JSoko Solver | JSoko]]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]
| width=" 80" | [https://festival-solver.site/curry/ Curry ]
| width=" 80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]




|- align="right"
| align="left" bgcolor="#f1efe5" | [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/ XSokoban]
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 59*]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Takaken%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/YASS%20-%20XSokoban.html 89]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban | 67 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Sokolution%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Curry%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Festival%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/BoxSearch%20-%20XSokoban.html '''89''']

|}

*) 59 solved puzzles according to paper [https://sokoban.dk/wp-content/uploads/2016/02/Single-Agent.pdf Sokoban Enhancing general single-agent search methods using domain knowledge]

{| class="soko-table"
|-


! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width=" 80" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width=" 80" | [http://www.ijcai.org/Abstract/16/100 Pereira et al.]
| width=" 80" | [http://sourceforge.net/projects/jsokoapplet/ JSoko]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]


|- align="right"
| align="left" bgcolor="#f1efe5" | XSokoban
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]
| [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/JSoko%20-%20XSokoban.html 25]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/Sokolution%20-%20XSokoban.html '''73''']

|}

The statistic shows that Sokolution is by far the best solver when searching for push optimal solutions.

== Large Test Suite ==

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is intended to be a "Large Standard Test Suite" for Sokoban solver programs.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 3272 
| '''3208''' 
| 3207 
| 2953 
| 2899 
| 2749 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/LargeTestSuite/ Click here to see the detailed results for the Large Test Suite].'''

Download the entire test suite [https://sourceforge.net/projects/sokoban-solver-statistics/files/Large%20Test%20Suite.zip/download here] or the individual level sets from [http://sokobano.de/de/levels.php www.sokobano.de].

== Open Test Suite ==

The statistics shows the results for the leading Sokoban solvers for various level collections. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

This test suite may be changed by adding new level collections from time to time.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Open Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 10043 
| '''9596''' 
| 9516 
| 8721 
| 8339 
| 8111 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/ Click here to see the detailed results for the Open Test Suite].'''

[https://sokoban-solver-statistics.sourceforge.io/statistics/Sokolution/ Comparison for the Open Test Suite for all Sokolution versions].

== Push-optimal Test Suite ==

The "Push-optimal Test Suite" comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

For this test suite the solvers must solve the puzzles push optimal.

{| class="soko-table"
|-
! colspan="6" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 1588 
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ '''1529'''] 
|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ Click here to see the detailed results for the Push-Optimal Test Suite].'''

== GroupEffort Test Suite ==

The only reason for benchmarking the GroupEffort test suite is to demonstrate the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

{| class="soko-table"
|-
! colspan="8" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels




|- bgcolor="#f1efe5" align="center" 
| width = "115" align="left" | Collection
| width = "80" | Levels
| width = "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
| width = "80" | [https://festival-solver.site/ Festival]
| width = "80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width = "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width = "80" | [https://sourceforge.net/projects/jsokoapplet/ JSoko]
| width = "80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]




|- align="right"
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
| 200
| 196 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Small-Set | '''200''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Small-Set | 192 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Small-Set | 180 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Small-Set | 191 (b) ]]




|- align="right"
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
| 2851
| 1566 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Large-Set | '''2766''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | 2471 (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Large-Set | 2462 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Large-Set | 2165 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Large-Set | 2260 (b) ]]




|- align="right" bgcolor="#f1efe5" align="right"
| align="left"| Total
| 3051 
| 1762 
| '''2966''' 
| 2671 
| 2654 
| 2345 
| 2471 
|}

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

== Disclaimer ==

Sokoban
=======
 
Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan
 
License
=======
 
Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met:
 
* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
and/or other materials provided with the distribution.
 
Credits (in no particular order)
================================
 
CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown
 
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown
 
Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown
 
Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/
 
SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: https://ljhaywood.uk/games/sokoban/
 
Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown
 
Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/
 
Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html
 
JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@mail.de
Web site: https://jsokoapplet.sourceforge.io/
 
Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: https://computerpuzzle.net/english/sokoban/ver740/index.html
 
YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
Web site: https://sourceforge.net/projects/sokobanyasc/
 
Sokoban YASC
Copyright (C) 2001-2020 by Brian Damgaard
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site: http://ygp.orgfree.com/sokoban.html
 
XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown
 
Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://sokolution.infinityfreeapp.com/
 
Festival
Copyright (C) 2020 by Yaron Shoham
Web site: https://festival-solver.site/
 
Trademarks
==========
 
Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.
 
Contact
=======
 
E-mail: sokobanowiki@gmail.com

Solver Statistics

2026-03-11T20:48:12Z

Matthias Meger: /* General benchmarking information */ new JSoko version

A Sokoban solver program is a program that ''tries to'' solve Sokoban levels. There are several solver programs available. (See [[Links#Sokoban Solvers |Sokoban solvers]].)

Solver programs may have different objectives:
# Find any solution
# Find push optimal solutions
# Find push optimal solutions with best moves
# Find move optimal solutions
# Find move optimal solutions with best pushes

Given the computational complexity of these tasks, a solver program is usually designed for just finding any solution. If a solution is to be optimized, an optimizer program can be used. (See [[Links#Sokoban Solvers |Optimizers]].)

The statistics presented here provide a picture of what the best freely available Sokoban solvers can do. 
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

== General benchmarking information ==

For practical reasons, almost all tests have been performed with a 10 minutes time limit. The tests are, however, not a 10 minutes contest but a showcase for what the solvers can do, so other time limits are entirely feasible.

The hardware used for the tests is a standard PC with a modern operating system (64bit).

Tests are performed with default solver settings.

{| class="soko-table feature-list"
!Solver || Version || Author || Architecture || CPU usage || Source code available || More info

|-
|[https://festival-solver.site/ Festival] || 3.1 || Yaron Shoham || 64bit || 8 threads || [https://festival-solver.site/ Festival 3.1] || [https://festival-solver.site/ Website with papers about the solver]

|-
|[http://sokolution.infinityfreeapp.com/ Sokolution] || 7.32 || Florent Diedler || 64bit || all threads || no || [[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver | Sokoban solver "scribbles" by Florent Diedler]]

|-
|[https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken] || 7.4 || Ken'ichiro Takahashi (takaken) || 64bit || 2 threads || no || [https://computerpuzzle.net/puzzle/sokoban/ver731/index.html Description of the used algorithms]

|-
|[https://festival-solver.site/curry/ Curry] || 0.3 || Yaron Shoham || 64bit || 1 thread || [https://festival-solver.site/curry/ Curry 0.3] || [https://festival-solver.site/curry/ Website with paper about the solver]

|-
|[https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || 7.0 beta 1 || 葛永 (Ge Yong) || 64bit || 1 thread || no || [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch Website of BoxSearch]

|-
|[https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || 2.153 || Brian Damgaard || 32bit + 64bit || 1 thread || [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS 2.153] || [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver | Sokoban solver "scribbles" by Brian Damgaard]]

|-
|[https://jsokoapplet.sourceforge.io/ JSoko] || 2.26 || Matthias Meger || 64bit || 1 thread || [https://sourceforge.net/projects/jsokoapplet/files/JSoko/Version%202.24/ JSoko 2.26] || [[Solver | Solver information]]
|-
|[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || 1.0 || Andreas Junghanns || 32bit || 1 thread || [https://webdocs.cs.ualberta.ca/~games/Sokoban/Src/ RS] || [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= Rolling Stone papers]

|}

Contact: SokobanoWiki@gmail.com

== XSokoban Test Suite ==

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

{| class="soko-table"
|-
! colspan="11" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width= "90" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width= "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [[JSoko Solver | JSoko]]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]
| width=" 80" | [https://festival-solver.site/curry/ Curry ]
| width=" 80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]




|- align="right"
| align="left" bgcolor="#f1efe5" | [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/ XSokoban]
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 59*]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Takaken%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/YASS%20-%20XSokoban.html 89]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban | 67 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Sokolution%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Curry%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Festival%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/BoxSearch%20-%20XSokoban.html '''89''']

|}

*) 59 solved puzzles according to paper [https://sokoban.dk/wp-content/uploads/2016/02/Single-Agent.pdf Sokoban Enhancing general single-agent search methods using domain knowledge]

{| class="soko-table"
|-


! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width=" 80" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width=" 80" | [http://www.ijcai.org/Abstract/16/100 Pereira et al.]
| width=" 80" | [http://sourceforge.net/projects/jsokoapplet/ JSoko]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]


|- align="right"
| align="left" bgcolor="#f1efe5" | XSokoban
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]
| [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/JSoko%20-%20XSokoban.html 25]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/Sokolution%20-%20XSokoban.html '''73''']

|}

The statistic shows that Sokolution is by far the best solver when searching for push optimal solutions.

== Large Test Suite ==

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is intended to be a "Large Standard Test Suite" for Sokoban solver programs.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 3272 
| '''3208''' 
| 3207 
| 2953 
| 2899 
| 2749 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/LargeTestSuite/ Click here to see the detailed results for the Large Test Suite].'''

Download the entire test suite [https://sourceforge.net/projects/sokoban-solver-statistics/files/Large%20Test%20Suite.zip/download here] or the individual level sets from [http://sokobano.de/de/levels.php www.sokobano.de].

== Open Test Suite ==

The statistics shows the results for the leading Sokoban solvers for various level collections. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

This test suite may be changed by adding new level collections from time to time.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Open Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 10043 
| '''9596''' 
| 9516 
| 8721 
| 8339 
| 8111 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/ Click here to see the detailed results for the Open Test Suite].'''

[https://sokoban-solver-statistics.sourceforge.io/statistics/Sokolution/ Comparison for the Open Test Suite for all Sokolution versions].

== Push-optimal Test Suite ==

The "Push-optimal Test Suite" comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

For this test suite the solvers must solve the puzzles push optimal.

{| class="soko-table"
|-
! colspan="6" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 1588 
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ '''1529'''] 
|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ Click here to see the detailed results for the Push-Optimal Test Suite].'''

== GroupEffort Test Suite ==

The only reason for benchmarking the GroupEffort test suite is to demonstrate the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

{| class="soko-table"
|-
! colspan="8" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels




|- bgcolor="#f1efe5" align="center" 
| width = "115" align="left" | Collection
| width = "80" | Levels
| width = "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
| width = "80" | [https://festival-solver.site/ Festival]
| width = "80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width = "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width = "80" | [https://sourceforge.net/projects/jsokoapplet/ JSoko]
| width = "80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]




|- align="right"
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
| 200
| 196 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Small-Set | '''200''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Small-Set | 192 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Small-Set | 180 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Small-Set | 191 (b) ]]




|- align="right"
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
| 2851
| 1566 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Large-Set | '''2766''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | 2471 (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Large-Set | 2462 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Large-Set | 2165 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Large-Set | 2260 (b) ]]




|- align="right" bgcolor="#f1efe5" align="right"
| align="left"| Total
| 3051 
| 1762 
| '''2966''' 
| 2671 
| 2654 
| 2345 
| 2471 
|}

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

== Disclaimer ==

Sokoban
=======
 
Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan
 
License
=======
 
Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met:
 
* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
and/or other materials provided with the distribution.
 
Credits (in no particular order)
================================
 
CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown
 
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown
 
Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown
 
Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/
 
SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: https://ljhaywood.uk/games/sokoban/
 
Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown
 
Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/
 
Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html
 
JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@mail.de
Web site: https://jsokoapplet.sourceforge.io/
 
Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: https://computerpuzzle.net/english/sokoban/ver740/index.html
 
YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
Web site: https://sourceforge.net/projects/sokobanyasc/
 
Sokoban YASC
Copyright (C) 2001-2020 by Brian Damgaard
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site: http://ygp.orgfree.com/sokoban.html
 
XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown
 
Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://sokolution.infinityfreeapp.com/
 
Festival
Copyright (C) 2020 by Yaron Shoham
Web site: https://festival-solver.site/
 
Trademarks
==========
 
Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.
 
Contact
=======
 
E-mail: sokobanowiki@gmail.com

Solver Statistics

2026-03-11T20:47:44Z

Matthias Meger: /* General benchmarking information */ New JSoko version

A Sokoban solver program is a program that ''tries to'' solve Sokoban levels. There are several solver programs available. (See [[Links#Sokoban Solvers |Sokoban solvers]].)

Solver programs may have different objectives:
# Find any solution
# Find push optimal solutions
# Find push optimal solutions with best moves
# Find move optimal solutions
# Find move optimal solutions with best pushes

Given the computational complexity of these tasks, a solver program is usually designed for just finding any solution. If a solution is to be optimized, an optimizer program can be used. (See [[Links#Sokoban Solvers |Optimizers]].)

The statistics presented here provide a picture of what the best freely available Sokoban solvers can do. 
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

== General benchmarking information ==

For practical reasons, almost all tests have been performed with a 10 minutes time limit. The tests are, however, not a 10 minutes contest but a showcase for what the solvers can do, so other time limits are entirely feasible.

The hardware used for the tests is a standard PC with a modern operating system (64bit).

Tests are performed with default solver settings.

{| class="soko-table feature-list"
!Solver || Version || Author || Architecture || CPU usage || Source code available || More info

|-
|[https://festival-solver.site/ Festival] || 3.1 || Yaron Shoham || 64bit || 8 threads || [https://festival-solver.site/ Festival 3.1] || [https://festival-solver.site/ Website with papers about the solver]

|-
|[http://sokolution.infinityfreeapp.com/ Sokolution] || 7.32 || Florent Diedler || 64bit || all threads || no || [[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver | Sokoban solver "scribbles" by Florent Diedler]]

|-
|[https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken] || 7.4 || Ken'ichiro Takahashi (takaken) || 64bit || 2 threads || no || [https://computerpuzzle.net/puzzle/sokoban/ver731/index.html Description of the used algorithms]

|-
|[https://festival-solver.site/curry/ Curry] || 0.3 || Yaron Shoham || 64bit || 1 thread || [https://festival-solver.site/curry/ Curry 0.3] || [https://festival-solver.site/curry/ Website with paper about the solver]

|-
|[https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || 7.0 beta 1 || 葛永 (Ge Yong) || 64bit || 1 thread || no || [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch Website of BoxSearch]

|-
|[https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || 2.153 || Brian Damgaard || 32bit + 64bit || 1 thread || [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS 2.153] || [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver | Sokoban solver "scribbles" by Brian Damgaard]]

|-
|[https://jsokoapplet.sourceforge.io/ JSoko] || 2.26 || Matthias Meger || 64bit || 1 thread || [https://sourceforge.net/projects/jsokoapplet/files/JSoko/Version%202.24/ JSoko 2.25] || [[Solver | Solver information]]
|-
|[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || 1.0 || Andreas Junghanns || 32bit || 1 thread || [https://webdocs.cs.ualberta.ca/~games/Sokoban/Src/ RS] || [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= Rolling Stone papers]

|}

Contact: SokobanoWiki@gmail.com

== XSokoban Test Suite ==

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

{| class="soko-table"
|-
! colspan="11" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width= "90" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width= "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [[JSoko Solver | JSoko]]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]
| width=" 80" | [https://festival-solver.site/curry/ Curry ]
| width=" 80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]




|- align="right"
| align="left" bgcolor="#f1efe5" | [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/ XSokoban]
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 59*]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Takaken%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/YASS%20-%20XSokoban.html 89]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban | 67 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Sokolution%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Curry%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Festival%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/BoxSearch%20-%20XSokoban.html '''89''']

|}

*) 59 solved puzzles according to paper [https://sokoban.dk/wp-content/uploads/2016/02/Single-Agent.pdf Sokoban Enhancing general single-agent search methods using domain knowledge]

{| class="soko-table"
|-


! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width=" 80" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width=" 80" | [http://www.ijcai.org/Abstract/16/100 Pereira et al.]
| width=" 80" | [http://sourceforge.net/projects/jsokoapplet/ JSoko]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]


|- align="right"
| align="left" bgcolor="#f1efe5" | XSokoban
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]
| [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/JSoko%20-%20XSokoban.html 25]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/Sokolution%20-%20XSokoban.html '''73''']

|}

The statistic shows that Sokolution is by far the best solver when searching for push optimal solutions.

== Large Test Suite ==

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is intended to be a "Large Standard Test Suite" for Sokoban solver programs.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 3272 
| '''3208''' 
| 3207 
| 2953 
| 2899 
| 2749 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/LargeTestSuite/ Click here to see the detailed results for the Large Test Suite].'''

Download the entire test suite [https://sourceforge.net/projects/sokoban-solver-statistics/files/Large%20Test%20Suite.zip/download here] or the individual level sets from [http://sokobano.de/de/levels.php www.sokobano.de].

== Open Test Suite ==

The statistics shows the results for the leading Sokoban solvers for various level collections. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

This test suite may be changed by adding new level collections from time to time.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Open Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 10043 
| '''9596''' 
| 9516 
| 8721 
| 8339 
| 8111 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/ Click here to see the detailed results for the Open Test Suite].'''

[https://sokoban-solver-statistics.sourceforge.io/statistics/Sokolution/ Comparison for the Open Test Suite for all Sokolution versions].

== Push-optimal Test Suite ==

The "Push-optimal Test Suite" comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

For this test suite the solvers must solve the puzzles push optimal.

{| class="soko-table"
|-
! colspan="6" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 1588 
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ '''1529'''] 
|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ Click here to see the detailed results for the Push-Optimal Test Suite].'''

== GroupEffort Test Suite ==

The only reason for benchmarking the GroupEffort test suite is to demonstrate the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

{| class="soko-table"
|-
! colspan="8" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels




|- bgcolor="#f1efe5" align="center" 
| width = "115" align="left" | Collection
| width = "80" | Levels
| width = "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
| width = "80" | [https://festival-solver.site/ Festival]
| width = "80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width = "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width = "80" | [https://sourceforge.net/projects/jsokoapplet/ JSoko]
| width = "80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]




|- align="right"
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
| 200
| 196 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Small-Set | '''200''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Small-Set | 192 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Small-Set | 180 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Small-Set | 191 (b) ]]




|- align="right"
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
| 2851
| 1566 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Large-Set | '''2766''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | 2471 (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Large-Set | 2462 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Large-Set | 2165 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Large-Set | 2260 (b) ]]




|- align="right" bgcolor="#f1efe5" align="right"
| align="left"| Total
| 3051 
| 1762 
| '''2966''' 
| 2671 
| 2654 
| 2345 
| 2471 
|}

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

== Disclaimer ==

Sokoban
=======
 
Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan
 
License
=======
 
Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met:
 
* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
and/or other materials provided with the distribution.
 
Credits (in no particular order)
================================
 
CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown
 
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown
 
Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown
 
Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/
 
SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: https://ljhaywood.uk/games/sokoban/
 
Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown
 
Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/
 
Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html
 
JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@mail.de
Web site: https://jsokoapplet.sourceforge.io/
 
Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: https://computerpuzzle.net/english/sokoban/ver740/index.html
 
YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
Web site: https://sourceforge.net/projects/sokobanyasc/
 
Sokoban YASC
Copyright (C) 2001-2020 by Brian Damgaard
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site: http://ygp.orgfree.com/sokoban.html
 
XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown
 
Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://sokolution.infinityfreeapp.com/
 
Festival
Copyright (C) 2020 by Yaron Shoham
Web site: https://festival-solver.site/
 
Trademarks
==========
 
Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.
 
Contact
=======
 
E-mail: sokobanowiki@gmail.com

Feature list : Map Viewing

2026-02-09T08:23:04Z

Matthias Meger: /* Map Viewing */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Map Viewing ==




{| class="soko-table"
! colspan="6" | Map Viewing !! colspan="50" | <div align="right">Map Viewing</div>
|- {{programs}}
| {{tc}} | level browser with preview || {{yes}} one level at a time || {{yes}} block graphic miniatures of all loaded levels || {{yes}} block graphic miniatures of all loaded levels || {{yes}} block graphic miniatures of all levels in a collection (customizable miniature size) || {{no}} || {{no}}
|-
| {{tc}} | resize skin to fit window || {{yes}} always || {{yes}}skin dependent || {{yes}} always || {{yes}} {{tip|flaw: Windows has 2 font settings, small (default) and large, and this only works for small fonts|text=flaw}} || {{yes}} || {{no}}
|-
| {{tc}} | resize window to fit map || {{un}} {{tip|map always fits in window}} || {{no}} || {{un}} {{tip|map always fits in window}} || {{yes}} {{tip|flaw: Windows has 2 font settings, small (default) and large, and this only works for small fonts|text=flaw}} || {{yes}} optional || {{yes}} always
|-
| {{tc}} | [[Feature_list_:_Map_Viewing#Level_scrolling|levels larger than window: scrolling]] || {{un}} || {{no}} || {{un}} || {{yes}} via scrollbars. {{tip| Windows has 2 font settings, small (default) and large, and this only works for small fonts|text=flaw}} || {{yes}} {{tip|via scrollbars with an option to autofollow (move scrollbars automatically)}} || {{un}}
|-
| {{tc}} | one-click browse levels || {{yes}} previous, next {{tip|in all level files in current level directory, with wrap-around}} || {{yes}} previous, next {{tip|in currently loaded levels, without wrap-around}} || {{yes}} previous, next {{tip|in current collection, with wrap-around}} || {{yes}} previous, next {{tip|in all loaded level files, with wrap-around}} || {{yes}} {{tip| implementation: keyboard shortcuts for: previous, next, first, last (in current collection, without wrap-around)|text=partial}} || {{yes}} next, without wrap-around
|-
| {{tc}} | one-click browse files || {{no}} || {{no}} || {{no}} || {{yes}} drop-down list with all level collections || {{yes}} drop-down list with visited level collections || {{no}}
|-
| {{tc}} | search for unsolved level || {{yes}} previous, next {{tip|in all level files in current level directory, with wrap-around}} || {{yes}} previous, next, random {{tip|in currently loaded levels, without wrap-around}} || {{yes}} previous, next {{tip|in current collection, with wrap-around}} || {{yes}} {{tip|partial implementation: auto-advance after having solved a level finds an unsolved level if settings is "unsolved levels only"|text=partial}} || {{yes}} previous, next {{tip|in current collection, without wrap-around}} || {{no}}
|-
| {{tc}} | rotate and mirror level-map || {{yes}} persistent, with reset option {{tip|savegames and solutions are automatically synchronized with current transformation}} || {{yes}} session (partial implementation: use editor) {{tip|savegames and solutions are specific to each transformation}} || {{yes}} session, with reset option {{tip|savegames and solutions are automatically synchronized with current transformation}} || {{yes}} <big style="color: red;">?</big>{{tip|Will somebody with a full version check if it is session, with reset option or persistent, with reset option additionally check if savegames and solutions are automatically synchronized with current transformation or savegames and solutions are specific to each transformation|width=300px|text=Help}} || {{yes}} session, with reset option {{tip|savegames and solutions are automatically synchronized with current transformation}} || {{no}}
|-
| {{tc}} | multiple windows, one per level || {{no}} || {{no}} || {{no}} || {{yes}}via tabs. multiple levels can be opened in separate tabs. || {{no}} || {{yes}}
|-
| {{tc}} | multiple views of a level || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | full screen || {{no}} || {{no}} || {{no}} || {{no}} || {{yes}} via : keyboard: F11 || {{no}}
|- {{programs}}
|}
[[#top|Top]]

<noinclude>

<h2>Information</h2>
=== Level scrolling ===

levels larger than window: scrolling 
levels larger than window: scrollbars 

Briefly, the first line is there to give a program the chance to tell that it has a scroll feature, and the second line is there to tell if the program does it the right way - with scrollbars.

Since the first graphical user interfaces emerged, scrollbars have been used for depicting the situation where a document doesn't fit in the window, so the user can rightfully expect to find that logic (or something equally user-friendly) in a Sokoban program as well.

Therefore, it's embarrasing for programs that requires scrolling if they don't have scrollbars or something equivalent. The line "levels larger than window: scrollbars" must be listed so readers can see this major design flaw, and so new programmers are reminded that they definitely should do better.

On the other hand, Sokofan deserves credits for at least having a scroll feature, despite the fact that it's not done the right way with scrollbars. The user doesn't get any visible clue that the board is bigger than the window, and the user must read the instructions to find the keyboard and mouse/key combinations that controls the scrolling.

So the line "levels larger than window: scrolling" is there to give Sokofan a chance to tell that it indeed has a scroll feature, even though it's not as user-friendly as the user rightfully can expect from a good Sokoban clone.

-bd

=== Multiple views of a level ===
A user often works on several alternative paths at the same time. It would be a great help if each of them was fully visible. For instance, multiple views are beneficial during the process of optimizing existing solutions.

=== SokRFI - Sokoban Requests for Implementation ===



{| class="soko-table feature-list"
|-
! colspan="50" | Map Viewing : SokRFI - Sokoban Requests for Implementation
|-
| width="120" {{tc}} | Feature || {{tc}} | Description
|-
|{{tc}}| show/hide redundant walls ||It fills jagged wall edges, fills unused "tubes", removes redundant walls, unused boxes, and unused goals. Implemented in [http://sokoban.ws/usokoban/usokoban.htm USokoban] as 'Normalize level'.
|}

[[#top|Top]]
</noinclude>

Feature list : Level Management

2026-02-09T08:22:56Z

Matthias Meger: /* Level Management */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Level Management ==




{| class="soko-table feature-list"
! colspan="6" | Level Management !! colspan="50" | <div align="right">Level Management</div>
|- {{programs}}
| {{tc}} | copy/paste level(s) (normal) || {{yes}} || {{yes}}{{tip|partial implementation of import: one level at a time; works for raw boards without meta data only}} || {{yes}}{{tip|levels can also be pasted by using drag&drop of a level file}} || <big style="color: red;">?</big>{{tip|Will somebody with a full version check if it works here the demo version has it on the menu in the editor and it does not mention any restrictions, but it does not work|text=Help}} || {{yes}} {{tip|flaw: pasted levels are not saved|text=flaw}} || {{no}}
|-
| {{tc}} | copy/paste levels (run-length-encoded) || {{yes}} || {{no}} || {{yes}} || {{no}} || {{yes}} {{tip|flaw: pasted levels are not saved |text=flaw}} || {{no}}
|-
| {{tc}} | copy map (current state) || {{yes}}via [ CTRL + click "tools"] and editor || {{yes}} || {{yes}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | copy level(s) with solution(s) || {{yes}}(multiple) || {{no}} || {{yes}}(single) || {{no}} || {{yes}}(single) || {{no}}
|-
| {{tc}} | paste level(s) with solution(s) || {{yes}}(multiple) || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | edit level information (e.g., title, author) || {{yes}} via "open" window || {{yes}} via menu: level->about; properties: title, author, comment || {{no}} || {{yes}} via menu: file->edit mode + file->attributes; properties:title, description, copyright, email, website || {{no}} || {{no}}
|-
| {{tc}} | edit levelset information (e.g., title, copyright) || {{no}} || {{yes}} via menu: levelset->about; properties: title, author, copyright, comment || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | load multiple files || {{no}} || {{yes}} || {{no}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{yes}}
|-
| {{tc}} | merge level files || {{yes}} (merge is a feature in the "open" window: menu -> file conversion...) || {{yes}}(via: open and select multiple files.) || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | recent levels history || {{yes}} 25 items {{tip|holding a unified recent file history for all loaded file-types, e.g., levels and background images}} || {{no}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{no}}
|-
| {{tc}} | saves levels with format || {{yes}} sok (.sok) || {{yes}} sok (.sok), xsokoban (.txt, .xsb), games 4 brains (.lp0), xml text file (.sls) || {{yes}} sok (.sok) || {{yes}} xml text file (.sls) || {{no}} || {{yes}} savegame text file (.sokosave)
|-
! colspan="6" | Level Management : Import and Export for Internet !! colspan="50" | <div align="right">Level Management : Import and Export for Internet</div>
|- {{programs}}
| {{tc}} | import levels with hyphens "-" or underscores "_" || {{yes}} via clipboard and load level || {{yes}} via clipboard and load level || {{yes}} via clipboard and load level || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | export levels with hyphens "-" or underscores "_" || {{yes}}via clipboard || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | stripping leading ">" characters || {{yes}} (all leading ">" characters are stripped) || {{no}} || {{yes}} (stripping leading ">" characters: boards, not moves) || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | accepts alternative characters for boards || {{yes}}characters: p,P,b,B,o || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|}
[[#top|Top]]

<noinclude>

== Related pages ==
* [[Level_format]]

== SokRFI - Sokoban Requests for Implementation ==


{| class="soko-table feature-list"
|-
! colspan="50" | Level Management : SokRFI - Sokoban Requests for Implementation
|-
| width="120" {{tc}} | Feature || {{tc}} | Description
|-
|{{tc}}| split levelset || SokoSave offers a utility for this feature. (External program [http://www.high-speed-software.com/sokosave/sokosavedesktop/sokosplit/ SokoSplit] can be downloaded)
|-
|{{tc}}| export levels to internet ||
 Export levels to internet 

This feature can be used to publish level(s) in a web-site. 

The export can have different variants: 
<ul>
<li>Generating the strings with code HTML. 
With links to download levels or thumbnails of each level.</li>
<li>Generating the strings with code [http://web.singnet.com.sg/~fclim/sbml/index.html SBML] (SokoBan Markup Language). 
Exporting with this language, levels can be customized by the user for the graphic representation of the maps, as well as provide a meta-information semantics of each level.
</li>
</ul>

<hr>Alternative development 
See [[SokRFI - Export Levels to Internet]].

<hr>Utility Sokoban++ offers a utility for this feature. (External program [http://www.joriswit.nl/sokoban/junk/ Sokoban Website Generator] can be downloaded) 

|}
[[#top|Top]]
</noinclude>

Feature list : Miscellaneous

2026-02-09T08:22:41Z

Matthias Meger: /* Miscellaneous */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Miscellaneous ==




{| class="soko-table feature-list"
! colspan="6" | Miscellaneous !! colspan="50" | <div align="right">Miscellaneous</div>
|- {{programs}}
| {{tc}} | builtin help and program information || {{yes}} rich text document (rtf) || {{yes}} html pages (html) || {{yes}} Java help || {{yes}} html pages (htm) || {{yes}} ascii text document || {{yes}} html page (html)
|-
| {{tc}} | context sensitive help || {{no}} || {{yes}} || {{yes}} {{tip|Pressing the help key (F1) opens the help}} || {{no}} {{tip|however, the web-page says otherwise|text=note}} || {{no}} || {{no}}
|-
| {{tc}} | customizable language || {{no}} || {{yes}} || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | languages || English || English, Afrikaans, Danish (embarrassing), Dutch, German, Greek, Finnish, French, Italian, Polish, Portugese, Russian, Spanish (Spain, Argentina), Turkish, Slovenian, Swedish || English, German, Chinese (Simplified), Spanish, Dutch || English || English, Bulgarian, Chinese (Simplified, Traditional), German, Spanish || English
|-
| {{tc}} | builtin solutions || {{yes}} {{tip|all levels ship with builtin solutions}} || {{yes}} {{tip|not all levels ship with builtin solutions}} || {{yes}} {{tip|not all levels ship with builtin solutions}} || {{yes}} {{tip|not all levels ship with builtin solutions}} || {{no}} || {{no}}
|-
| {{tc}} | file type associations (optional) || {{no}} || {{yes}} .sls, .pak, .rdf, .lp0, .xsb, .sok, .sxl, .slc || {{no}} || {{no}} || {{no}} || {{yes}} .sokomaze, .xsb, .sokohex, .hsb, .sokotri, .tsb, .sokosave Windows, Mac OS X
|-
| {{tc}} | accessibility for portable version || {{no}} || {{no}} || {{no}} || {{no}} || {{yes}}{{tip|compatible installation: yes system modification: no generated data: saves the files created in the removable device. additional: edition for mobile phone, java MIDP 2.0 only.|width=200px}} || {{no}}
|- {{programs}}
|}
[[#top|Top]]

<noinclude>

==Info==
===Portable software===
''From Wikipedia, the free encyclopedia'' 

To be considered '''truly portable''', a software program must: 
<ul>
<li>Not require any form of formal installation to be carried out on any computer before it can be used, with the release package only needing to be decompressed directly to removable media before use (if it has to be installed first, and requires it's files to be manually copied to removable media, it's clearly not designed to be portable!). For example, software which is supplied as an InstallShield package could not be considered portable, though a ZIP archives containing an executable would be.</li>
<li>Settings are stored with, and can be carried around with, the software (i.e. they are written to the USB drive). If the registry is used to store settings; the application's configuration isn't portable, and must be set up on every PC it is used on</li>
<li>Leaves a zero (or near-zero) "footprint" on any PC it's run on after being used. i.e. All temporary files/registry settings should be removed once the program has exited, and files created by the user can be saved directly to the same removable media as the application is stored on.</li>
</ul>
Generally, smaller utility/toolkit software is inherently fairly portable; though larger applications are sometimes changed in order to allow a portable versions to be released (e.g. FirefoxPortable)

</noinclude>

Feature list : Game Play

2026-02-09T08:22:05Z

Matthias Meger: /* Game Play */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Game Play ==




{| class="soko-table"
! colspan="6" | Game Play !! colspan="50" | <div align="right">Game Play</div>
|- {{programs}}
| {{tc}} | autosave best solutions || {{yes}} tiebreaking: moves, pushes, secondary metrics || {{yes}} tiebreaking: moves, pushes || {{no}} || {{yes}} tiebreaking: moves, pushes || {{yes}} tiebreaking: moves, pushes, secondary metrics || {{no}}
|-
| {{tc}} | autosave solutions options || always autosaves better solutions; inferior solutions are discarded || autosave solutions options: never/always/if better/ask; existing solutions are kept || {{no}} || autosave solutions options: none/best 5/best 10/all || always autosaves better solutions; inferior solutions are discarded || optionally saves game when solved; only one solution per saved game
|-
| {{tc}} | push or move optimized pathfinding || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}}
|-
| {{tc}} | move animation modes || smooth, cell by cell, instant || cell by cell, instant || cell by cell || smooth || cell by cell, instant {{tip|(instant with [[Feature_info#Choice points|choice points]] is listed but is too fast to be useful)|menu=yes}} || cell by cell, instant
|-
| {{tc}} | mouse move control: drag and drop || {{yes}} with reachable squares || {{yes}} without reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{no}}
|-
| {{tc}} | [[#Mouse_Move_Control:_Select_and_drop|mouse move control: select and drop]] || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} without reachable squares
|-
| {{tc}} | [[#Mouse_Move_Control:_Drag_and_track|mouse move control: drag and track]] || {{no}} experimental click-less tracking available || {{no}} || {{no}} || {{no}} || {{no}} || {{yes}}
|-
| {{tc}} | reverse mode play starting at end position (pull instead of push) || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | show secondary metrics (box-pushes, box-changes and pushing-sessions) || {{yes}} display: mouse over || {{yes}} display: optional, configurable || {{no}} || {{no}} || {{yes}} || {{yes}}
|-
| {{tc}} | [[#Lowerbound_of_solution_length_regarding_pushes|show a lowerbound of the solution length]] || {{no}} || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | timing || {{yes}} optional; optional idle time threshold || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | move player through boxes ||{{no}}|| {{no}} || {{yes}} || {{no}} || {{yes}} target: reachable squares through boxes. figure: small black square. via: options -> go through boxes. || {{no}}
|-
! colspan="6" | Game Play : Legal moves !! colspan="50" | <div align="right">Game Play : Legal moves</div>
|- {{programs}}
| {{tc}} | show player's reachable squares|| {{yes}} figure: transparent small skin graphics || {{no}} || {{yes}} figure: transparent small skin graphics || {{yes}} || {{yes}} figure: small round blobs || {{no}}
|-
| {{tc}} | show box's reachable squares || {{yes}} figure: transparent small skin graphics || {{yes}} figure: skin graphics, independent of box || {{yes}} figure: transparent small skin graphics || {{yes}} || {{yes}} figure: small round blobs || {{no}}
|-
| {{tc}} | show pushable boxes || {{yes}} dynamically by clicking a wall. figure: configurable border || {{no}} || {{no}} || {{no}} || {{yes}} permanent with CTRL+F9. dynamically by clicking a wall. figure: skin graphics, independent of box || {{no}}
|-
| {{tc}} | show [[Deadlocks#Dead square deadlocks|dead squares]] || {{yes}}figure: configurable shaded square || {{no}} || {{yes}}figure: darker shaded square || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | [[#Simple deadlock detection|simple deadlock detection]] || {{yes}} dead squares, freezing boxes || {{no}} || {{yes}} dead squares, freezing boxes || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | [[#Advanced deadlock detection|advanced deadlock detection]] || {{yes}} {{tip|bipartite: n boxes for m goals; 1 goal for n boxes; corrals: precalculated at level load time + 100 ms search after a push}} || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}}
|-
! colspan="6" | Game Play : History !! colspan="50" | <div align="right">Game Play : History</div>
|- {{programs}}
| {{tc}} | undo/redo || unlimited || unlimited || unlimited || unlimited || unlimited || unlimited
|-
| {{tc}} | undo all || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} press [esc]|| {{yes}}
|-
| {{tc}} | redo all || {{yes}} || {{no}} || {{yes}} || {{no}} ||{{no}} || {{yes}}
|-
| {{tc}} | replay || {{yes}} forwards and backwards || {{yes}} forwards || {{yes}} forwards || {{yes}} forwards and backwards || {{yes}} forwards (solutions only) || {{yes| via trackbar dragged to any position replays to that position}}
|-
| {{tc}} | replay ergonomics || unified start/stop button; click anywhere to stop; keyboard shortcuts available; speed and direction can be changed during replay || separate start/stop buttons; click stop-button to stop; keyboard shortcuts available || unified start/stop button; click anywhere to stop; speed can be changed during replay || || with start/stop: CTRL+F2 to begin. SPACE to replay to next box-change. without start/stop: F2 || trackbar represents replay history; drag trackbar to control replay; click anywhere, click [stop] button, or press [esc] to stop
|-
| {{tc}} | mousewheel undo/redo/replay support || {{yes}} combined moves || {{yes}} single step or optional combined moves || {{yes}} combined moves || {{no}} || {{yes}} combined moves || {{no}}
|-
| {{tc}} | browse move history || {{yes}} trackbar (choice-points, with preview) || {{yes}} trackbar (all moves, with preview) || {{yes}} trackbar (choice-points, with preview) || {{no}} || {{no}} || {{yes}} trackbar (all moves, no preview)
|-
| {{tc}} | quicksave slots || {{yes}} unlimited (interface: graphical, window, thumbnail preview) || {{yes}} unlimited (interface: graphical, pop-up, list) || {{no}} || {{yes}} 3 (interface: graphical) || {{no}} || {{no}}
|-
| {{tc}} | one-click load quicksaves || {{yes}} keyboard: press [Enter] to load currently selected snapshot; mouse: double-click a snapshot on the list || {{no}} || {{no}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | remember last session || {{yes}} file, level, history with redo, position {{tip|position is optional, default "off", additionally, up to 25 recent (file, level)}} || {{yes}} file, level || {{yes}} file, level || {{yes}} file, level, history without redo, position || {{yes}} file, level, history without redo, position || {{no}}
|- {{programs}}
|}

[[#top|Top]]

<noinclude>

== Info ==

=== Choice points ===

A choice point in the game is when the player changes from one box to another, or finishes a series of moves that pushed a box in a single direction.

Several programs have replay features related to choice points. Sokofan, for example, has replay buttons (called "smart do/undo") to move from one choice point to another. Another example is the game history browser in Sokoban YASC which works with choice points instead of individual moves.

=== Mouse Move Control: Select and drop ===
Lift and drop. Left click on a box to lift it, move to the wanted position and left click again to drop. Lift and drop is easier for long moves than the drag and drop.

=== Mouse Move Control: Drag and track ===
Point at the pusher with the mouse and move it in the direction you want. The pusher will track your movements.

=== Simple deadlock detection ===

Simple deadlock detection deals with deadlock types that require rather simple analysis of the board and the game state. Good examples are:

* [[Deadlocks#Dead square deadlocks|Dead squares]]

* [[Deadlocks#Freeze deadlocks|Freeze deadlocks]]

=== Advanced deadlock detection ===

Advanced deadlock detection deals with deadlock types that require quite sophisticated computations. Good examples are:

* [[Deadlocks#Bipartite deadlocks|Bipartite deadlocks]]

* [[Deadlocks#Corral deadlocks|Corral deadlocks]]

=== Lowerbound of solution length regarding pushes ===

For solving a level all boxes have to be pushed to goals. A program can calculate the distance of every box to the nearest goal. While doing this it is presumed only one box is on the board (hence the box does not need to be pushed around other boxes). The sum of all these box distances to their goals results in a lowerbound - no matter how the boxes are pushed to their goals the level can never be solved with fewer than the calculated number of pushes. Some programs can calculate a lowerbound for the solution length (in pushes): 
number of pushes so far + sum of all box distances to their nearest goals (presuming no other boxes are on the board). 
This lowerbound can be useful in levels like the "Kobus Theron"-series.

[[#top|Top]]
</noinclude>

Feature list : Level Editor

2026-02-09T08:21:52Z

Matthias Meger: /* Additional Tools : Level Editor */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools : Level Editor ==




{| class="soko-table feature-list"
! colspan="6" | Additional Tools - Level Editor !!
|- {{programs|5= |6= }}
| {{tc}} | editor || built-in || built-in || built-in || built-in
|-
| {{tc}} | drawing objects || wall, box, goal, player || none, floor, goal, box-on-floor, box-on-goal, player-on-floor, player-on-goal, wall || wall, box, goal, player, floor || floor, goal, box, wall
|-
| {{tc}} | drawing tools || objects, eraser, rubber-band, fill || objects, pencil, drop, fill, line, rectangle, filled rectangle || objects || objects, move player, move box
|-
| {{tc}} | drawing logic || select object + click-and-drag the board to put objects on the board || select object + select drawing tool + click-and-drag the board to put objects on the board || select object + click-and-drag the board to put objects on the board || select object + click-and-drag the board to put objects on the board
|-
| {{tc}} | drawing logic inconveniences || the board jumps around on the screen when automatic scaling and positioning kick in || drawing with tools like lines and rectangles don't show the objects on the screen during the drawing process || the board jumps around on the screen when automatic scaling and positioning kick in || The "move" tool works for boxes and the player only, not for goals
|-
| {{tc}} | savegames and solutions for modified levels are retained after cosmetic changes (e.g., transformations and adding/removing extra floors/walls) || {{yes}} || {{no}} the savegames and solutions are still there in the files, but they are not applicable to the modified level || {{no}} || <big style="color: red;background:beige;">?</big> {{tip|will somebody with a full version check if it is "yes" or "no"|text=help}}
|-
| {{tc}} | undo || {{yes}} unlimited || {{yes}} unlimited || {{no}} || {{yes}} unlimited
|-
| {{tc}} | redo || {{yes}} unlimited || {{yes}} unlimited || {{no}} || {{no}}
|-
| {{tc}} | undo/redo logic || one complete transaction at a time || one complete transaction at a time || || one cell at a time
|-
| {{tc}} | undo/redo history is saved from one session to the next || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | undo/redo multiple transactions: interface || pull-down menu: 1,2,4,8,... transactions || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | undo/redo multiple transactions: preview || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | "rubber-band" area selection || {{yes}}(features: move, copy, paste, delete, transform, fill) || {{no}} || {{no}} || {{no}}
|- {{programs|5= |6= }}
| {{tc}} | board transformations || {{yes}} rotate counter-clockwise and clockwise, flip vertically and horizontally. || {{yes}} rotate clockwise, flip vertically || {{yes}} rotate counter-clockwise and clockwise, flip vertically and horizontally || {{yes}} rotate counter-clockwise and clockwise, flip vertically and horizontally
|-
| {{tc}} | resize board || {{un}} {{tip|the board is automatically positioned so it's possible to draw on all 4 sides}} || {{yes}} (via toolbar button: resize level) || {{un}} {{tip|the board is automatically positioned so it's possible to draw on all 4 sides}} || {{un}} {{tip|"move board" does not clip the level to a predefined size like, e.g., Sokoban++ does}}
|-
| {{tc}} | move board || {{un}} || {{yes}} || {{un}} || {{yes}}
|-
| {{tc}} | one-click switching between play/edit mode || {{yes}} || {{no}} use menu: game->mode || {{no}} || {{yes}} {{tip|partial implementation: no visible button but a keyboard shortcut "Alt+P"|text=partial}}
|-
| {{tc}} | board validation on switching from edit mode to play mode || {{yes}} || {{no}} all boards are playable || {{yes}} || <big style="color:red;background:beige">?</big>{{tip|will somebody with a full version check if it happens automatically|text=help}}
|-
| {{tc}} | customizable skin || {{yes}} format: simple image-based skins without seamless walls || {{yes}} same skin in edit mode and in play mode || {{yes}} same skin in edit mode and in play mode || {{yes}} same skin in edit mode and in play mode
|-
| {{tc}} | customizable button images || {{yes}} || {{no}} || {{yes}} || {{un}} {{tip|the editor uses menus and has no buttons}}
|-
| {{tc}} | button images automatically synchronized with skin images || {{no}} || {{no}} || {{yes}} || {{un}}
|-
| {{tc}} | windows clipboard copy/paste || {{yes}} || {{yes}} {{tip|partial implementation: imports / exports complete levels instead of copying / pasting sections to the existing "document", i.e., the board|text=partial}} || {{no}} || <big style="color: red;background:beige;">?</big> {{tip|(will somebody with a full version check if it works here; the demo version has it on the menu in the editor and it does not mention any restrictions, but it does not work)|width=260px|text=help}}
|-
| {{tc}} | internal clipboard with multiple items || {{yes}} unlimited, persistent, with preview || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | edit board as text || {{no}} || {{no}} || {{no}} || {{no}}
|}
[[#top|Top]]

Feature list : Moves Management

2026-02-09T08:21:44Z

Matthias Meger: /* Moves Management */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Moves Management ==




{| class="soko-table feature-list"
! colspan="6" | Moves Management !! colspan="50" | <div align="right">Moves Management</div>
|- {{programs}}
| {{tc}} | copy/paste moves (normal) || {{yes}} || {{yes}} || {{yes}} || {{yes}} {{tip|partial implementation: solutions only, not savegames flaw: imported solutions are lost when the program exits flaw: imported moves are listed as solutions even if this is not the case|width=200px}} || {{yes}} || {{no}}
|-
| {{tc}} | copy/paste moves (run-length-encoded) || {{yes}} || {{yes}} partial: paste only || {{yes}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | copy moves after the current position || {{yes}}via keyboard: Ctrl+B || {{yes}}via menu: position -> copy || {{yes}} Ctrl+Shift+M || {{no}} || {{yes}}via keyboard: Ctrl+Alt+C || {{no}}
|-
| {{tc}} | paste moves as continuation of current position || {{yes}} || {{yes}} || {{yes}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | rotate and/or flip moves || {{no}}{{tip|board rotations and flips automatically synchronize existing savegames and solutions}} || {{no}} external program [http://www.joriswit.nl/sokoban/junk/solutionrotator.zip Solution Rotator] can be downloaded || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | edit move information (e.g, title, author, comment) || {{yes}}via snapshot window || {{yes}}via menu: position->save; properties: title || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | recreate maps from solutions || {{yes}} multiple solutions, with titles and info || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | load and save moves || sok (ascii text file, levels); clipboard: import/export || xht,txt (ascii text file, solutions), mov (sokofun movie); clipboard: import/export || sok (ascii text file, levels); clipboard: import/export || gam (xml text file, level); clipboard: import/export || txt (ascii text file, levels); clipboard: import/export || sokosave (savegame file)
|- {{programs}}
|}
[[#top|Top]]

<noinclude>

== Related pages ==
* [[Solution_format]] (German language)

== SokRFI - Sokoban Requests for Implementation ==


{| class="soko-table"
|-
! colspan="50" | Moves Management : SokRFI - Sokoban Requests for Implementation
|-
| width="120" {{tc}} | Feature || {{tc}} | Description
|-
|{{tc}}| animation snapshots capture: solutions || Sokoban++ offers a utility for this feature. (External program [http://www.joriswit.nl/sokoban/junk/ Sokoban Animator] can be downloaded)
|-
|{{tc}}| export solution as animation || Free formats: 
Text file:
:Scalable Vector Graphics ([http://www.w3.org/Graphics/SVG/ SVG]).
:Implementation with a [http://www.treebuilder.de/svg/sokoban/sokobano.svg template SVG].
Image file:
:Animated PNG ([http://wiki.mozilla.org/APNG_Specification APNG]) available with Firefox 3.
:[http://easysok.sourceforge.net EasySok] as alternative can save all the snapshots in a movie MNG.
|}
[[#top|Top]]
</noinclude>

Feature list : Customizing

2026-02-09T08:21:34Z

Matthias Meger: /* Customizing */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Customizing ==




{| class="soko-table"
! colspan="6" | Customizing !! colspan="50" | <div align="right">Customizing</div>
|- {{programs}}
| {{tc}} | settings interface || {{yes}} graphical user interface (tree-view) || {{yes}} graphical user interface (tabbed notebook view) || {{yes}} graphical user interface || {{yes}} graphical user interface (tabbed notebook view) || {{yes}} graphical user interface (window) || {{yes}} graphical user interface (window)
|-
| {{tc}} | configurable statusbar (e.g., level title, moves, pushes) || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | configurable game state graphics (e.g., moves/pushes) || {{yes}} fonts, colours, buttons (static layout) || {{yes}} skin graphics (configurable layout) || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | customizable cursors || {{no}} || {{yes}} graphics, skin dependent || {{no}} || {{yes}} small/large built-in cursors || {{no}} || {{no}}
|-
| {{tc}} | customizable mouse actions || {{yes}}(only right-click) || {{no}} || {{no}} || || {{yes}}(buttons: left, middle, right) || {{no}}
|-
| {{tc}} | customizable sound events || {{yes}} independent || {{yes}} skin dependent || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | background music || {{no}}  || {{no}} || {{no}} || {{yes}} source: folder formats: midi, mp3. || {{no}} || {{no}}
|-
! colspan="6" | Customizing : Background Image!! colspan="50" | <div align="right">Customizing : Background Image</div>
|- {{programs}}
| {{tc}} | customizable backgrounds || {{yes}} independent, with preview || {{yes}} skin dependent || {{yes}} independent || {{yes}} skin dependent || {{yes}} independent, with preview || {{no}}
|-
| {{tc}} | background control || {{yes}} source: color, image; (image view: center, scale, stretch, tile) || {{yes}} source: color, image; (image view: center, stretch, tile) || {{no}} || {{yes}} source: image; (image view: tile) || {{yes}} source: image; (image view: center, stretch, tile) || {{no}}
|-
| {{tc}} | quick browse backgrounds || {{no}} "slow" browse via settings || {{no}} || {{yes}} browse with preview via settings || {{no}} || {{yes}} tool button with drop-down list || {{no}}
|}
[[#top|Top]]

<noinclude>

== SokRFI - Sokoban Requests for Implementation ==


{| class="soko-table feature-list"
|-
! colspan="50" | Customizing : SokRFI - Sokoban Requests for Implementation
|-
| width="120" {{tc}} | Feature || {{tc}} | Description
|-
|{{tc}}| background-image changer || This feature is for the users that look for to always have a different background, playing a level. It is applied to the following events in the program: 
• On program start-up • After solving a level. 
For the convenience of users and updates are groups all backgrounds in a single folder. One can also choose the mode in that the background will be changed: 
• Next image. • Previous image. • Random image.Implemented in Sokomind
|}
[[#top|Top]]
</noinclude>

Feature list : Multi-player Mode

2026-02-09T08:21:25Z

Matthias Meger: /* Multi-player Mode */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Multi-player Mode ==




{| class="soko-table feature-list"
! colspan="6" | Multi-player Mode !! colspan="50" | <div align="right">Multi-player Mode</div>
|- {{programs}}
| {{tc}} | [[Feature_list_:_Multi-player_Mode#Multi-player|multi-player]] || {{no}} || {{yes}}(options: create new player, change player) || {{no}} || {{yes}}(options: create new player, change player) || {{yes}}(options: create new player, change player) || {{no}}
|-
| {{tc}} | edit player information (e.g. name, email, country) || {{no}} || {{no}} || {{no}} || || {{no}} || {{yes}} {{tip|only when recording high score}}
|-
| {{tc}} | display personal high-scores || {{yes}} {{tip|cramped implementation and disabled by default. Enable it in "open" window via menu -> show solutions}} || {{yes}} via menu: level -> choose || {{no}} || {{yes}} via menu: view -> scores and solutions || {{yes}} drop-down list || {{yes}} via menu: help -> scores
|-
| {{tc}} | compare high-scores of all the players || {{ni|/a|Not applicable to single-player programs.}} || {{yes}} general and personal scores || {{ni|/a|Not applicable to single-player programs.}} || {{yes}}ranking with all the players || {{no}} || {{ni|/a|Not applicable to single-player programs.}}
|-
| {{tc}} | save and restore the player profiles (e.g. high-scores, settings) || {{ni|/a|Not applicable to single-player programs.}} || {{yes}} player position file (*.sav) || {{ni|/a|Not applicable to single-player programs.}} || ||{{yes}} player info file (*.SokoInfo) || {{ni|/a|Not applicable to single-player programs.}}
|-
| {{tc}} | remember each player's session (e.g. level, skin, quicksaves) {{tip|not to be confused with a single player program's ability to do the same. Feature implemented in Sokonline.|text=note}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|- {{programs}}
|}
[[#top|Top]]

<noinclude>

<h2>Info</h2>
=== Multi-player ===

This modality is useful for the competitions, each user can have his own configurations. As the personalization, with their scores, personal information, as the option of sending their solutions via e-mail.

These are options for the soko-programs that point, to give the option for competitive players that participate in the challenges of internet.

'''Related programs''' 
[http://sokoban.online.fr/mon_player.html Sokonline]

[[#top|Top]]
</noinclude>

Feature list : Additional Tools

2026-02-09T08:21:18Z

Matthias Meger: /* Additional Tools */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools ==




{| class="soko-table"
! colspan="6" | Additional Tools !! colspan="50" | <div align="right">Additional Tools</div>
|- {{programs}}
| {{tc}} | level editor ([[Feature_list_:_Level_Editor|see details below]]) || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||{{no}} || {{no}}
|-
| {{tc}} | solver ([[Feature_list_:_Solver|see details below]]) || {{yes}} common solver plugins (allowing continued game play) || {{yes}} common solver plugins (blocking game play) || {{yes}} built-in (blocking game play) || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | optimizer ([[Feature_list_:_Solver#Additional_Tools_:_Optimizer|see details below]]) || {{yes}} common optimizer plugins (allowing continued game play) || {{no}} || {{yes}} built-in (blocking game play) || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | locate and browse duplicates or look-alikes ([[Feature_list_:_Duplicate_Finder|see details below]]) || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}} external program [http://geocities.com/ygp_bg/sokodup.zip Soko-Dup] can be downloaded || {{no}}
|-
| {{tc}} | skin graphics editor || {{no}} skin script editor available || {{no}} skin script editor available || {{no}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | level generator || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | optimizer for unnecessary moves between pushes || {{yes}} automatically during game-play || {{yes}} manually via menu || {{yes}} automatically during game-play || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | level file converters || {{yes}} {{tip|SokoMind (including solutions), Sokoban for Windows by Björn Källmark (including solutions), Sokofan (including solutions)|width=250px|text=file types}} || {{yes}} {{tip|ASCII (*.txt, *.xsb, *.screen, *.skm, *.scb), Sokoban (*.sls), Visual Sokoban 1 and 2 (*.pak), WinSoko (*.rdf), Games 4 Brains (*.lp0), Mark McIntyres Soko (*.sok), XML Sokoban (*.xml), Sokoban XP (*.sxl), Games 4 Brains Sokoblue (*.dat), Icons (*.ico), Björn Källmark's xml format (*.slc)|width=270px|text=file types}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | image snapshot capture || {{no}} || {{yes}} miniature level bitmap with 1 pixel per square; via menu: level->copy level || {{no}} || {{no}} || {{no}} || {{no}}
|- {{programs}}
|}
[[#top|Top]]

Feature list : Skin Features

2026-02-09T08:21:10Z

Matthias Meger: /* Skin Features */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Skin Features ==




{| class="soko-table"
! colspan="6" | Skin Features !! colspan="50" | <div align="right">Skin Features</div>
|- {{programs}}
| {{tc}} | customizable skin || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}}
|-
| {{tc}} | skin formats || {{yes}} meta-script language {{tip|includes scripts for importing the following skin formats: common sokoban skin images (YSokoban), Sokoban++ skin scripts, Sokofan skin scripts, Visual Sokoban skin scripts, Sokoban for Windows skin scripts (Björn Källmark), Sokoban BDE images, SuperSoko skin images, SokoStation4 skin scripts JSoko skin scripts|width=210px}} || {{yes}} Sokoban++ skin scripts (ini) || {{yes}} two built-in skins || {{yes}} Sokoban for Windows skin scripts (skn) || {{yes}} common sokoban skin images (YSokoban) || {{no}}
|-
| {{tc}} | resizeable skins || {{yes}} || {{no}} || {{yes}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | pseudo-3D skins (sokoban++ style) || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | legal moves box animation (ysokoban style) || {{yes}} || {{no}} || {{no}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | legal moves player animation (ysokoban style) || {{yes}} || {{no}} || {{no}} || {{no}} ||{{yes}} || {{no}}
|-
| {{tc}} | solution animation (ysokoban style) || {{yes}} || {{no}} || {{no}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | animation frame extrapolation (morphing) || {{yes}} 30 frames || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | directional player || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | directional player can return to an "at ease" position || {{no}} || {{no}} || {{no}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | directional box|| {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | directional box can return to an "at ease" position || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | support for seamless walls (as opposed to discrete walls) || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}}
|-
| {{tc}} | walls can be transparent || {{no}} || {{no}} skin dependent || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | floors can be transparent || {{yes}} || {{no}} skin dependent || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | skin browser with preview || {{yes}} image-based skins; not scripted skins || {{no}} || {{yes}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | recent skins history || {{yes}} || {{yes}} || {{no}} || {{un}} {{tip|with all skins in a list it is just as easy to browse the whole list}} || {{no}} || {{no}}
|-
| {{tc}} | quick browse skins || {{yes}} menu: default, recent skins; keyboard shortcuts: next, default || {{yes}} menu: default, recent skins || {{yes}} menu: skin list || {{yes}} menu: skin list || {{yes}} use F4-F8 to select one of the loaded skins || {{no}}
|- {{programs}}
|}
[[#top|Top]]

Feature list : Duplicate Finder

2026-02-09T08:21:02Z

Matthias Meger: /* Additional Tools : Duplicate Finder */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools : Duplicate Finder ==




{| class="soko-table"
! colspan="6" | Additional Tools : Duplicate Finder !!
|- {{programs|3= |4= |6= }}
| {{tc}} | duplicate finder || built-in ||{{ni}} {{tip|(Alternatively has the feature '''duplicate levels exchange solutions''')|text=note|menu=yes}} || || || external utility
|-
| {{tc}} | search type || {{yes}} equal and similar levels. type: rotated and mirrored, dead squares removal, normalized walls, normalized pusher position. || || || || {{yes}} equal and similar levels. type: rotated and mirrored, dead squares removal, normalized walls, normalized pusher position.
|-
| {{tc}} | relaxed match options || {{yes}}{{tip|* with/without boxes * with/without goals * with/without interior walls * with/without exterior walls}} || || || || {{yes}}{{tip|* targets only, with optional threshold count * without pusher and boxes * walls only * without internal walls * floors only}}
|-
| {{tc}} | search current level duplicates || {{yes}} || || || || {{no}}
|-
| {{tc}} | duplicate levels preview || {{yes}} || || || || {{no}}
|-
| {{tc}} | search history || {{tip|a persistent user maintained "scanned folders" list is available|text=note}} || || || || {{no}}
|-
| {{tc}} | export report duplicates ||{{yes}}|| || || ||{{yes}}
|-
| {{tc}} | duplicate levels exchange solutions || {{yes}} {{tip| normalized levels exchange solutions, i.e., an exact match is not required.}} || {{yes}} {{tip|identical levels automatically exchange their solutions}} || || || {{yes}}
|}
[[#top|Top]]

<noinclude>

==Info==
=== Related pages ===

* [[Pruning_duplicate_positions|Pruning duplicate positions]]

[[#top|Top]]
</noinclude>

Feature list : Solver

2026-02-09T08:20:54Z

Matthias Meger: /* Additional Tools : Solver */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools : Solver ==




{| class="soko-table feature-list"
! colspan="5" | Additional Tools - Solver
|- {{programs|4=<div>[http://www.ic-net.or.jp/home/takaken/e/soko/index.html Takaken]</div>|5= |6= }}
| {{tc}} | solver || common solver plugins || common solver plugins || built-in || built-in
|-
| {{tc}} | solver running mode || background, allowing continued game play || foreground, blocking game play || foreground, blocking game play || foreground, blocking game play
|-
| {{tc}} | solution types (e.g., any, move-optimal, push-optimal) || solver strategies and options depend on the plugins, not the host program || solver strategies and options depend on the plugins, not the host program || push-optimal, push-optimal with best moves, move-optimal with best pushes || move-optimal, push-optimal
|-
| {{tc}} | task queue || {{yes}} || {{no}} || {{no}} || {{no}}
|}
[[#top|Top]]

<noinclude>

==Info==
===Related Pages===
[[Solver|Solver]]

[[#top|Top]]
</noinclude>

Feature list : Optimizer

2026-02-09T08:20:44Z

Matthias Meger: /* Additional Tools : Optimizer */ removed last changed time

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools : Optimizer ==




{| class="soko-table feature-list"
! colspan="6" | Additional Tools - Optimizer !!
|- {{programs|2= |4= |5= |6= }}
| {{tc}} | optimizer || common optimizer plugins || || built-in
|-
| {{tc}} | optimizer running mode || background, allowing continued game play || || foreground, allowing continued game play
|-
| {{tc}} | optimization options (e.g., move-optimal, push-optimal) || optimization settings and options depend on the plugins, not the host program || || pushes/moves, moves/pushes, box changes, box lines
|-
| {{tc}} | task queue || {{yes}} || || {{no}}
|}
[[#top|Top]]

<noinclude>

==Info==
===Related pages===
[[Optimizer|Optimizer_Development]]

[[#top|Top]]
</noinclude>

How to play Sokoban

2026-02-09T07:55:59Z

Matthias Meger: replaced <code> by <pre>

This article explains how to play Sokoban. There are also simple strategies explained.

First let's have a look at the rules of the game:

The object of Sokoban is to take some objects (usually boxes) to designated locations by pushing them.

To do this the user moves a man who we call Sokoban. Sokoban can move up, down, left and right. He can't pass through walls or boxes. He can push only one box at a time (never pull). At any time a square can only be occupied by one of a wall, box or man.

A level contains these elements:
<pre>
Walls: #
Boxes: $
Goals: .
Free squares: ' '
The Sokoban / the player: @
</pre>

Boxes and the Sokoban can also be located on a goal.

<pre>
Boxes on goals: *
The Sokoban on a goal: +
</pre>

In the following the Sokoban is called "the player" to indicate that this is the object the user can move.

Movements:
Nearly all Sokoban games can be played using the arrow keys. Nowadays many programs also support playing with the mouse.
All moves of the Sokoban need only to be done for pushing a box.
<pre>
Level 1
#########
#@ $ .#
#########
</pre>
Using the arrow keys one has to press the "right arrow" 5 times.
Using the mouse you have to mark the box for pushing (by clicking on it) and then clicking at the position the box is to be pushed to.

<pre>
Level 2
########
# ###
#@$ ###
#### ###
## ###
## ##
# ##. #
# #
##### #
########
</pre>

Here the difference between playing with keyboard and playing with mouse is demonstrated. Using the mouse is as simple as in Level 1. Using the arrow keys needs a lot of key presses for pushing the box to the goal.
Hence, it's always recommended to use the mouse for playing. The advantages compared to keyboard playing are:
# With two clicks a box can be pushed to every possible square
# Most programs automatically calculates the best moves for the player. Hence the user doesn't have to think about how to move the player by keys.
# Some programs even show the squares a box can be pushed to. In this way it's easy to see if a box can be pushed to the selected position.
# The user can concentrate on pushes only instead of moves and pushes

Levels containing only one box are very simple to solve using the mouse: One just has to mark the box for pushing and then to choose the goal square as target.

Usually Sokoban levels are a lot more complicated.

Let's increase the difficulty step by step:
<pre>
Level 3
########
# #
# $ .#
#@ $ .#
# $ .#
# #
########
</pre>
Here the level contains 3 boxes. Nevertheless the level can easily be solved. Although every box can be pushed to each goal it doesn't matter which box is pushed to which goal. The boxes can just be pushed one after the other to any goal.

<pre>
Level 4
########
# #. #
# $# #
# # @##
# # $##
# .##
########
</pre>
This level is more complicated. The box under the player is close to a goal. Nevertheless it can't be pushed to the goal - this would result in a [[Deadlocks|deadlock]]. This level shows some problems one has to solve before it's possible to finish the level:
# Not every box can be pushed to every goal
# Boxes can't just be pushed to the nearest goal in every case
# Box pushes can create a [[Deadlocks|deadlock]]

<pre>
Level 5
#########
## # #
#.$. $ #
# # ## #
# @$.$. #
#########
</pre>

To solve this level the boxes have to be pushed to their goals in a specific order. Moreover one box has to be pushed away from its goal before it can be pushed to it.

<pre>
Level 6
#########
# # .#
#@$ $ #
# $ ##..#
# #####
#########
</pre>

This level is another example of the need to push a box away from its goal before the level can be solved. Additionally one box has to be "parked" until some other boxes have reached their goals. A situation where a box must be pushed but can't be pushed immediately to its goal occurs very often in Sokoban levels. Some of them are "parking" situations.
"Parking" means:
# a box must be pushed away from its goal
# after the box is pushed to its parking position another box has to be pushed
# parking the box at a specific position is required to solve the level

== Reverse play ==

Some Sokoban programs allow to play a puzzle backward.

Starting with all boxes on goal squares, the player pulls the boxes to return to the initial puzzle state.

Solutions found this way solve the standard puzzle when both the order and the direction of the moves are reversed.

This approach can help players better understand the puzzle structure and develop effective solving strategies.

Solver Statistics

2026-02-08T22:06:22Z

Matthias Meger: /* Disclaimer */ fixed URL

A Sokoban solver program is a program that ''tries to'' solve Sokoban levels. There are several solver programs available. (See [[Links#Sokoban Solvers |Sokoban solvers]].)

Solver programs may have different objectives:
# Find any solution
# Find push optimal solutions
# Find push optimal solutions with best moves
# Find move optimal solutions
# Find move optimal solutions with best pushes

Given the computational complexity of these tasks, a solver program is usually designed for just finding any solution. If a solution is to be optimized, an optimizer program can be used. (See [[Links#Sokoban Solvers |Optimizers]].)

The statistics presented here provide a picture of what the best freely available Sokoban solvers can do. 
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

== General benchmarking information ==

For practical reasons, almost all tests have been performed with a 10 minutes time limit. The tests are, however, not a 10 minutes contest but a showcase for what the solvers can do, so other time limits are entirely feasible.

The hardware used for the tests is a standard PC with a modern operating system (64bit).

Tests are performed with default solver settings.

{| class="soko-table feature-list"
!Solver || Version || Author || Architecture || CPU usage || Source code available || More info

|-
|[https://festival-solver.site/ Festival] || 3.1 || Yaron Shoham || 64bit || 8 threads || [https://festival-solver.site/ Festival 3.1] || [https://festival-solver.site/ Website with papers about the solver]

|-
|[http://sokolution.infinityfreeapp.com/ Sokolution] || 7.32 || Florent Diedler || 64bit || all threads || no || [[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver | Sokoban solver "scribbles" by Florent Diedler]]

|-
|[https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken] || 7.4 || Ken'ichiro Takahashi (takaken) || 64bit || 2 threads || no || [https://computerpuzzle.net/puzzle/sokoban/ver731/index.html Description of the used algorithms]

|-
|[https://festival-solver.site/curry/ Curry] || 0.3 || Yaron Shoham || 64bit || 1 thread || [https://festival-solver.site/curry/ Curry 0.3] || [https://festival-solver.site/curry/ Website with paper about the solver]

|-
|[https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || 7.0 beta 1 || 葛永 (Ge Yong) || 64bit || 1 thread || no || [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch Website of BoxSearch]

|-
|[https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || 2.153 || Brian Damgaard || 32bit + 64bit || 1 thread || [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS 2.153] || [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver | Sokoban solver "scribbles" by Brian Damgaard]]

|-
|[https://jsokoapplet.sourceforge.io/ JSoko] || 2.25 || Matthias Meger || 64bit || 1 thread || [https://sourceforge.net/projects/jsokoapplet/files/JSoko/Version%202.24/ JSoko 2.25] || [[Solver | Solver information]]
|-
|[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || 1.0 || Andreas Junghanns || 32bit || 1 thread || [https://webdocs.cs.ualberta.ca/~games/Sokoban/Src/ RS] || [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= Rolling Stone papers]

|}

Contact: SokobanoWiki@gmail.com

== XSokoban Test Suite ==

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

{| class="soko-table"
|-
! colspan="11" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width= "90" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width= "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [[JSoko Solver | JSoko]]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]
| width=" 80" | [https://festival-solver.site/curry/ Curry ]
| width=" 80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]




|- align="right"
| align="left" bgcolor="#f1efe5" | [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/ XSokoban]
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 59*]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Takaken%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/YASS%20-%20XSokoban.html 89]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban | 67 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Sokolution%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Curry%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Festival%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/BoxSearch%20-%20XSokoban.html '''89''']

|}

*) 59 solved puzzles according to paper [https://sokoban.dk/wp-content/uploads/2016/02/Single-Agent.pdf Sokoban Enhancing general single-agent search methods using domain knowledge]

{| class="soko-table"
|-


! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width=" 80" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width=" 80" | [http://www.ijcai.org/Abstract/16/100 Pereira et al.]
| width=" 80" | [http://sourceforge.net/projects/jsokoapplet/ JSoko]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]


|- align="right"
| align="left" bgcolor="#f1efe5" | XSokoban
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]
| [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/JSoko%20-%20XSokoban.html 25]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/Sokolution%20-%20XSokoban.html '''73''']

|}

The statistic shows that Sokolution is by far the best solver when searching for push optimal solutions.

== Large Test Suite ==

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is intended to be a "Large Standard Test Suite" for Sokoban solver programs.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 3272 
| '''3208''' 
| 3207 
| 2953 
| 2899 
| 2749 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/LargeTestSuite/ Click here to see the detailed results for the Large Test Suite].'''

Download the entire test suite [https://sourceforge.net/projects/sokoban-solver-statistics/files/Large%20Test%20Suite.zip/download here] or the individual level sets from [http://sokobano.de/de/levels.php www.sokobano.de].

== Open Test Suite ==

The statistics shows the results for the leading Sokoban solvers for various level collections. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

This test suite may be changed by adding new level collections from time to time.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Open Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 10043 
| '''9596''' 
| 9516 
| 8721 
| 8339 
| 8111 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/ Click here to see the detailed results for the Open Test Suite].'''

[https://sokoban-solver-statistics.sourceforge.io/statistics/Sokolution/ Comparison for the Open Test Suite for all Sokolution versions].

== Push-optimal Test Suite ==

The "Push-optimal Test Suite" comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

For this test suite the solvers must solve the puzzles push optimal.

{| class="soko-table"
|-
! colspan="6" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 1588 
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ '''1529'''] 
|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ Click here to see the detailed results for the Push-Optimal Test Suite].'''

== GroupEffort Test Suite ==

The only reason for benchmarking the GroupEffort test suite is to demonstrate the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

{| class="soko-table"
|-
! colspan="8" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels




|- bgcolor="#f1efe5" align="center" 
| width = "115" align="left" | Collection
| width = "80" | Levels
| width = "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
| width = "80" | [https://festival-solver.site/ Festival]
| width = "80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width = "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width = "80" | [https://sourceforge.net/projects/jsokoapplet/ JSoko]
| width = "80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]




|- align="right"
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
| 200
| 196 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Small-Set | '''200''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Small-Set | 192 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Small-Set | 180 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Small-Set | 191 (b) ]]




|- align="right"
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
| 2851
| 1566 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Large-Set | '''2766''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | 2471 (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Large-Set | 2462 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Large-Set | 2165 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Large-Set | 2260 (b) ]]




|- align="right" bgcolor="#f1efe5" align="right"
| align="left"| Total
| 3051 
| 1762 
| '''2966''' 
| 2671 
| 2654 
| 2345 
| 2471 
|}

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

== Disclaimer ==

Sokoban
=======
 
Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan
 
License
=======
 
Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met:
 
* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
and/or other materials provided with the distribution.
 
Credits (in no particular order)
================================
 
CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown
 
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown
 
Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown
 
Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/
 
SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: https://ljhaywood.uk/games/sokoban/
 
Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown
 
Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/
 
Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html
 
JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@mail.de
Web site: https://jsokoapplet.sourceforge.io/
 
Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: https://computerpuzzle.net/english/sokoban/ver740/index.html
 
YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
Web site: https://sourceforge.net/projects/sokobanyasc/
 
Sokoban YASC
Copyright (C) 2001-2020 by Brian Damgaard
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site: http://ygp.orgfree.com/sokoban.html
 
XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown
 
Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://sokolution.infinityfreeapp.com/
 
Festival
Copyright (C) 2020 by Yaron Shoham
Web site: https://festival-solver.site/
 
Trademarks
==========
 
Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.
 
Contact
=======
 
E-mail: sokobanowiki@gmail.com

Links

2026-01-23T18:05:59Z

Matthias Meger: Updated links

This page contains links to several web-sites with Sokoban related material, e.g., programs, levels, and publications.

== Sokoban Programs ==
[[Feature list]] comparing Sokoban programs.

{| class="soko-table"
|-
! Name || Author || Operating System
|-
| [[First Sokoban program]] || Hiroyuki Imabayashi || PC-8801
|-
| [http://sourceforge.net/projects/sokobanyasc/ Sokoban YASC ] || Brian Damgaard || Windows
|-
| [http://www.joriswit.nl/sokoban/ Sokoban++] || Joris Wit || Windows
|-
| [http://www.sokosave.org/ SokoSave Mobile] || Eric Sunshine || Windows Mobile
|-
| [http://www.sokosave.org/ SokoSave Desktop] || Eric Sunshine || Windows, MacOS/X
|-
| [https://jsokoapplet.sourceforge.io/ JSoko] || Matthias Meger || Platform independent (Java)
|-
| [http://www.sourcecode.se/sokoban/ Sokoban for Windows] || Björn Källmark || Windows
|-
| [http://ygp.orgfree.com/sokoban.html YSokoban] || George Petrov || Windows
|-
| [http://www.fuzitoo.com/ Fuzitoo] || Jean Van Laethem || Windows
|-
| [https://puzzle-dungeon.github.io/ Puzzle Dungeon] || Mikhael Goikhman || GNU/Linux, Windows
|}

== Sokoban Solvers ==
[[Solver Statistics | Statistics]] comparing Sokoban solvers.

{| class="soko-table"
|-
! Name || Author || Operating System
|-
| [https://computerpuzzle.net/english/sokoban/ver740/index.html Sokoban Automatic solver] || Ken'ichiro Takahashi (takaken) || Windows
|-
| [http://www.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || Andreas Junghanns || Linux sourcecode
|-
| [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || Brian Damgaard || Windows / Platform independent source code (Pascal)
|-
| [https://jsokoapplet.sourceforge.io/ JSoko] || Matthias Meger || Platform independent (Java)
|-
| [https://sokolution.infinityfreeapp.com/ Sokolution] || Florent Diedler || Windows
|-
| [https://festival-solver.site/ Festival] || Yaron Shoham || Windows
|-
| [https://festival-solver.site/curry/ Curry] || Yaron Shoham || Windows
|-
| [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || Ge Yong || Windows
|}

== Worldwide Sokoban High-Scores ==
{| class="soko-table"
! colspan="2" | worldwide best known highscores
|-
| [http://sokobano.de/scores/ Sokoban PROJECT] || Sokobano.de
|}

{| class="soko-table feature-list"
! colspan="2" |last XSokoban highscore list from december 2005
|-
|[http://web.archive.org/web/20051201163838/www5.cs.cornell.edu/cgi-bin/andru/xsokoban/best-scores-moves by moves] || [http://web.archive.org/web/20051201164016/www5.cs.cornell.edu/cgi-bin/andru/xsokoban/best-scores-pushes by pushes]
|}

== Level Generators ==
{| class="soko-table"
|-
! Name || Author || Operating System
|-
| [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASGen] || Brian Damgaard || Windows / Platform independent source code (Pascal)
|-
| [[User:Sokobania | sokogen]] || Jacques Duthen || UNIX / lisp
|}

== Fan Groups ==
[https://www.facebook.com/groups/539527933307469/ Facebook Sokoban Group]

[https://groups.io/g/sokoban Groups.io Sokoban Group]

== Optimizers ==
{| class="soko-table"
|-
! Name || Author || Operating System
|-
| [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASO] || Brian Damgaard || Windows / Platform independent source code (Pascal)
|-
| [http://sourceforge.net/projects/jsokoapplet/ JSoko] || Matthias Meger || Platform independent (Java)
|-
| [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || Ge Yong || Windows
|}

== Levels for Downloading ==
* [http://www.sourcecode.se/sokoban/levels.php Sourcecode.se]
* [http://sokobano.de/scores/ Sokoban PROJECT]
* [http://grigr.narod.ru/ Evgeny Grigoriev Maps]
* [http://kantorek.webzdarma.cz/sokobana.htm František Pokorný Maps]
* [https://ljhaywood.uk/games/sokoban/ Lee J Haywood Maps]

== Information about the original Sokoban game puzzles ==
* [https://wayneca.neocities.org/Sokoban/ Tribute to original Sokoban game puzzles]

== Literature ==
* [http://www.cs.ualberta.ca/~games/Sokoban/papers.html Sokoban Publications]

== Additional Sokoban links ==

* [http://www.onlinespiele-sammlung.de/sokoban/list-of-sokoban-games.php?records_to_show=-1 "Sokoban online" collection (German)]
* [http://sourceforge.net/projects/yasminuroban/ Yasminuroban (DHTML Sokoban)]

=== Online Sokoban Games ===
;'''JavaScript'''
* [http://sokoban.e-contento.com/sokoban.php Sokoban en JavaScript] by Juan Antonio Jiménez
* [http://www.game-sokoban.com Game Sokoban]
* [https://ljhaywood.uk/games/crossoban/ Crossoban] by Lee J Haywood
* [https://sokoban-solver.com/ Sokoban Solver] Explore tens of thousands of Sokoban puzzles with solutions ready for replay
* [https://www.linusakesson.net/games/autosokoban/ Autosokoban] Website which generates an unlimited number of puzzles with increasing difficulty to play online
* [http://www.letslogic.com/ Lets Logic - The Online Sokoban Community]
* [https://sokoban-solver-statistics.sourceforge.io Sokoban Javascript] by Matthias Meger

=== Online Sokoban Variant Games ===
;'''JavaScript'''
* [http://www.chrisfortey.com/#sokobanColours Sokoban Colours]

Solver Statistics

2025-08-14T15:18:29Z

Matthias Meger: /* Open Test Suite */ added BoxSearch to Open Test Suite and removed a duplicate collection from all results

A Sokoban solver program is a program that ''tries to'' solve Sokoban levels. There are several solver programs available. (See [[Links#Sokoban Solvers |Sokoban solvers]].)

Solver programs may have different objectives:
# Find any solution
# Find push optimal solutions
# Find push optimal solutions with best moves
# Find move optimal solutions
# Find move optimal solutions with best pushes

Given the computational complexity of these tasks, a solver program is usually designed for just finding any solution. If a solution is to be optimized, an optimizer program can be used. (See [[Links#Sokoban Solvers |Optimizers]].)

The statistics presented here provide a picture of what the best freely available Sokoban solvers can do. 
For copyrights, credits and redistribution of these statistics, please read the disclaimer.

== General benchmarking information ==

For practical reasons, almost all tests have been performed with a 10 minutes time limit. The tests are, however, not a 10 minutes contest but a showcase for what the solvers can do, so other time limits are entirely feasible.

The hardware used for the tests is a standard PC with a modern operating system (64bit).

Tests are performed with default solver settings.

{| class="soko-table feature-list"
!Solver || Version || Author || Architecture || CPU usage || Source code available || More info

|-
|[https://festival-solver.site/ Festival] || 3.1 || Yaron Shoham || 64bit || 8 threads || [https://festival-solver.site/ Festival 3.1] || [https://festival-solver.site/ Website with papers about the solver]

|-
|[http://sokolution.infinityfreeapp.com/ Sokolution] || 7.32 || Florent Diedler || 64bit || all threads || no || [[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver | Sokoban solver "scribbles" by Florent Diedler]]

|-
|[https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken] || 7.4 || Ken'ichiro Takahashi (takaken) || 64bit || 2 threads || no || [https://computerpuzzle.net/puzzle/sokoban/ver731/index.html Description of the used algorithms]

|-
|[https://festival-solver.site/curry/ Curry] || 0.3 || Yaron Shoham || 64bit || 1 thread || [https://festival-solver.site/curry/ Curry 0.3] || [https://festival-solver.site/curry/ Website with paper about the solver]

|-
|[https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch] || 7.0 beta 1 || 葛永 (Ge Yong) || 64bit || 1 thread || no || [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch Website of BoxSearch]

|-
|[https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS] || 2.153 || Brian Damgaard || 32bit + 64bit || 1 thread || [https://sourceforge.net/projects/sokobanyasc/files/sokobanyasc/ YASS 2.153] || [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver | Sokoban solver "scribbles" by Brian Damgaard]]

|-
|[https://jsokoapplet.sourceforge.io/ JSoko] || 2.25 || Matthias Meger || 64bit || 1 thread || [https://sourceforge.net/projects/jsokoapplet/files/JSoko/Version%202.24/ JSoko 2.25] || [[Solver | Solver information]]
|-
|[https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html Rolling Stone] || 1.0 || Andreas Junghanns || 32bit || 1 thread || [https://webdocs.cs.ualberta.ca/~games/Sokoban/Src/ RS] || [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= Rolling Stone papers]

|}

Contact: SokobanoWiki@gmail.com

== XSokoban Test Suite ==

The XSokoban level set is the de facto standard test suite in the academic literature on Sokoban solver programming.

{| class="soko-table"
|-
! colspan="11" | Sokoban Solver Statistics - XSokoban Test Suite - Solved Levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width= "90" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width= "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [[JSoko Solver | JSoko]]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]
| width=" 80" | [https://festival-solver.site/curry/ Curry ]
| width=" 80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]




|- align="right"
| align="left" bgcolor="#f1efe5" | [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/ XSokoban]
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 59*]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Takaken%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/YASS%20-%20XSokoban.html 89]
| [[SolverStatistics-jsoko-ThinkingRabbit-XSokoban | 67 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Sokolution%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Curry%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/Festival%20-%20XSokoban.html '''90''']
| [https://sokoban-solver-statistics.sourceforge.io/statistics/XSokoban/BoxSearch%20-%20XSokoban.html '''89''']

|}

*) 59 solved puzzles according to paper [https://sokoban.dk/wp-content/uploads/2016/02/Single-Agent.pdf Sokoban Enhancing general single-agent search methods using domain knowledge]

{| class="soko-table"
|-


! colspan="7" | Sokoban Solver Statistics - XSokoban Test Suite - Push-optimal Solutions
|- bgcolor="#f1efe5" align="center"
| width="115" align="left" | Collection
| width="160" | Author
| width=" 70" | Levels
| width=" 80" | [https://www.researchgate.net/publication/2305703_Pushing_the_Limits_New_Developments_in_Single-Agent_Search Rolling Stone]
| width=" 80" | [http://www.ijcai.org/Abstract/16/100 Pereira et al.]
| width=" 80" | [http://sourceforge.net/projects/jsokoapplet/ JSoko]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution ]


|- align="right"
| align="left" bgcolor="#f1efe5" | XSokoban
| align="left" | Thinking Rabbit, ...
| 90
| [https://webdocs.cs.ualberta.ca/~games/Sokoban/program.html 6 ]
| [[SolverStatistics-Pereira-ThinkingRabbit-XSokoban-Push-Optimal | 28 ]]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/JSoko%20-%20XSokoban.html 25]
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/Sokolution%20-%20XSokoban.html '''73''']

|}

The statistic shows that Sokolution is by far the best solver when searching for push optimal solutions.

== Large Test Suite ==

The large test suite comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

This test suite is not subject to change, as it is intended to be a "Large Standard Test Suite" for Sokoban solver programs.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival ]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 3272 
| '''3208''' 
| 3207 
| 2953 
| 2899 
| 2749 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/LargeTestSuite/ Click here to see the detailed results for the Large Test Suite].'''

Download the entire test suite [https://sourceforge.net/projects/sokoban-solver-statistics/files/Large%20Test%20Suite.zip/download here] or the individual level sets from [http://sokobano.de/de/levels.php www.sokobano.de].

== Open Test Suite ==

The statistics shows the results for the leading Sokoban solvers for various level collections. Please note that the grand totals are simple summations. The number of solved unique levels may differ slightly due to duplicate levels in the level packs.

This test suite may be changed by adding new level collections from time to time.

{| class="soko-table"
|-
! colspan="7" | Sokoban Solver Statistics - Open Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width= "80" | [https://festival-solver.site/ Festival]
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width=" 80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width=" 80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]
| width=" 80" | [https://notabdc.github.io/puzzle007/EngPage/e_solver.htm#BoxSearch BoxSearch]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 10043 
| '''9596''' 
| 9516 
| 8721 
| 8339 
| 8111 

|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/ Click here to see the detailed results for the Open Test Suite].'''

[https://sokoban-solver-statistics.sourceforge.io/statistics/Sokolution/ Comparison for the Open Test Suite for all Sokolution versions].

== Push-optimal Test Suite ==

The "Push-optimal Test Suite" comprises level packs selected for being a challenge for the solvers, but not too difficult. The statistics shows the results for the leading Sokoban solver programs.

For this test suite the solvers must solve the puzzles push optimal.

{| class="soko-table"
|-
! colspan="6" | Sokoban Solver Statistics - Large Test Suite - Solved levels


|- bgcolor="#f1efe5" align="center"
| width="115" align="left" |
| width=" 70" | Levels
| width=" 80" | [http://sokolution.infinityfreeapp.com/ Sokolution]

|- bgcolor="#f1efe5" align="right"
| align="left" | Total levels
| 1588 
| [https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ '''1529'''] 
|}

'''[https://sokoban-solver-statistics.sourceforge.io/statistics/Push-OptimalTestSuite/ Click here to see the detailed results for the Push-Optimal Test Suite].'''

== GroupEffort Test Suite ==

The only reason for benchmarking the GroupEffort test suite is to demonstrate the limited veracity of the statement made in section "6 Conclusion" of the thesis, where the author writes that the GroupEffort solver "outperforms existing solvers".

The benchmarks show that this was only true for the cherry-picked small test set at the time the thesis was published, never for the presumably more representative large test set.

{| class="soko-table"
|-
! colspan="8" | Sokoban Solver Statistics - GroupEffort Test Suite - Solved Levels




|- bgcolor="#f1efe5" align="center" 
| width = "115" align="left" | Collection
| width = "80" | Levels
| width = "80" | [https://baldur.iti.kit.edu/theses/SokobanPortfolio.pdf GroupEffort]
| width = "80" | [https://festival-solver.site/ Festival]
| width = "80" | [http://sokolution.infinityfreeapp.com/ Sokolution]
| width = "80" | [https://computerpuzzle.net/english/sokoban/ver740/index.html Takaken]
| width = "80" | [https://sourceforge.net/projects/jsokoapplet/ JSoko]
| width = "80" | [https://sourceforge.net/projects/sokobanyasc/ YASS]




|- align="right"
| align="left" bgcolor="#f1efe5" | [[SolverStatistics-GroupEffort-Small-Set | Small Set]]
| 200
| 196 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Small-Set | '''200''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Small-Set | '''200''' (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Small-Set | 192 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Small-Set | 180 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Small-Set | 191 (b) ]]




|- align="right"
| align="left" bgcolor="#f1efe5"| [[SolverStatistics-GroupEffort-Large-Set | Large Set]]
| 2851
| 1566 (a)(c)
| [[SolverStatistics-Festival-GroupEffort-Large-Set | '''2766''' (b) ]]
| [[SolverStatistics-Sokolution-GroupEffort-Large-Set | 2471 (a) ]]
| [[SolverStatistics-Takaken-GroupEffort-Large-Set | 2462 (b) ]]
| [[SolverStatistics-JSoko-GroupEffort-Large-Set | 2165 (b) ]]
| [[SolverStatistics-YASS-GroupEffort-Large-Set | 2260 (b) ]]




|- align="right" bgcolor="#f1efe5" align="right"
| align="left"| Total
| 3051 
| 1762 
| '''2966''' 
| 2671 
| 2654 
| 2345 
| 2471 
|}

(a): Time limit: 5 minutes     (b): Time limit: 10 minutes     (c): Best GroupEffort solver configuration

== Disclaimer ==

Sokoban
=======
 
Sokoban (R) Registered Trademark of Falcon Co., Ltd., Japan
Sokoban Copyright (C) 1982-2004 by Hiroyuki Imabayashi, Japan
Sokoban Copyright (C) 1989, 1990, 2001-2004 by Falcon Co., Ltd., Japan
 
License
=======
 
Redistribution and use of the Sokoban Solver statistics are permitted
provided that the following conditions are met:
 
* Redistributions may not be sold, nor may they be used in a commercial product or activity.
* Redistributions must reproduce the entire content of this disclaimer in the documentation
and/or other materials provided with the distribution.
 
Credits (in no particular order)
================================
 
CosmoNotes, CosmoPoly, LOMA, MicroCosmos, MiniCosmos,
NaboCosmos and PicoCosmos level sets
Copyright (C) by Aymeric du Peloux.
E-mail: aymeric.du-peloux@gadz.org
Web site: unknown
 
dh1, dh2, bagatelle, cantrip, and maelstrom level sets
Copyright (C) by David Holland
E-mail: unknown
Web site: unknown
 
Microban, Mas Microban, Sasquatch, Mas Sasquatch, Sasquatch III,
Sasquatch IV, Sasquatch V, Sasquatch VI and Sasquatch VII level sets.
Copyright (C) by David W. Skinner
E-mail: sasquatch@bentonrea.com
Web site: unknown
 
Grigr2001, Grigr2002 and GrigrSpecial level sets
Copyright (C) by Evgeny Grigoriev (aka GRIGoRusha)
E-mail: grigr@yandex.ru
Web site: http://grigr.narod.ru/
 
SokEvo and SokHard level sets
Copyright (C) 2002-2006 by Lee J Haywood
E-mail: fruise@gmail.com
Web Site: http://leehaywood.org/games/sokoban/
 
Sven level set
Copyright (C) 2007 by Sven Egevad
E-mail: sven.egevad@telia.com
Web Site: unknown
 
Sokoban Perfect and Sokoban Revenge level sets
Copyright (C) 1989, 1991 by Thinking Rabbit
Web Site: https://sokoban.jp/
 
Y.M. Auto and Y.M. Handmade level sets
Copyright (C) Yoshio Murase
E-mail: yoshio@asahi.email.ne.jp
Web Site: http://www.ne.jp/asahi/ai/yoshio/sokoban/index.html
 
JSoko
Copyright (C) by Matthias Meger
E-mail: JSoko@mail.de
Web site: https://jsokoapplet.sourceforge.io/
 
Sokoban Automatic Solver (aka Takaken solver)
Copyright (C) 2002 - 200X Ken'ichiro Takahashi (aka takaken)
E-mail: takaken@ic-net.or.jp
Web site: https://computerpuzzle.net/english/sokoban/ver740/index.html
 
YASS - Yet Another Sokoban Solver and Optimizer - For Small Levels
Copyright (C) 2007 by Brian Damgaard
Web site: https://sourceforge.net/projects/sokobanyasc/
 
Sokoban YASC
Copyright (C) 2001-2020 by Brian Damgaard
Web Site: https://sourceforge.net/projects/sokobanyasc/
 
YSokoban
Copyright (C) 2007 by George Petrov
E-mail: YGP@WriteMe.com
Web Site: http://ygp.orgfree.com/sokoban.html
 
XSokoban
Copyright (C) by Andrew Myers
E-mail: andru@cs.cornell.edu
Web Site: http://www.cs.cornell.edu/andru/xsokoban.html
 
Sokofan
Copyright (C) 2005-2007 by Eric Leung
E-mail: eleung2@hotpop.com
Web Site: unknown
 
Sokolution
Copyright (C) 2016-2019 by Florent DIEDLER
E-mail: fdiedler2000@gmail.com
Web site: http://sokolution.infinityfreeapp.com/
 
Festival
Copyright (C) 2020 by Yaron Shoham
Web site: https://festival-solver.site/
 
Trademarks
==========
 
Company names, brand names and product names are trademarks
or registered trademarks of their respective holders.
 
Contact
=======
 
E-mail: sokobanowiki@gmail.com

How to play Sokoban

2025-04-24T09:52:26Z

Matthias Meger: /* Reverse play */ added reverse mode

This article explains how to play Sokoban. There are also simple strategies explained.

First let's have a look at the rules of the game:

The object of Sokoban is to take some objects (usually boxes) to designated locations by pushing them.

To do this the user moves a man who we call Sokoban. Sokoban can move up, down, left and right. He can't pass through walls or boxes. He can push only one box at a time (never pull). At any time a square can only be occupied by one of a wall, box or man.

A level contains these elements:
<code>
Walls: #
Boxes: $
Goals: .
Free squares: ' '
The Sokoban / the player: @
</code>

Boxes and the Sokoban can also be located on a goal.
<code>
Boxes on goals: *
The Sokoban on a goal: +
</code>

In the following the Sokoban is called "the player" to indicate that this is the object the user can move.

Movements:
Nearly all Sokoban games can be played using the arrow keys. Nowadays many programs also support playing with the mouse.
All moves of the Sokoban need only to be done for pushing a box.
<code>
Level 1
#########
#@ $ .#
#########
</code>
Using the arrow keys one has to press the "right arrow" 5 times.
Using the mouse you have to mark the box for pushing (by clicking on it) and then clicking at the position the box is to be pushed to.

<code>
Level 2
########
# ###
#@$ ###
#### ###
## ###
## ##
# ##. #
# #
##### #
########
</code>

Here the difference between playing with keyboard and playing with mouse is demonstrated. Using the mouse is as simple as in Level 1. Using the arrow keys needs a lot of key presses for pushing the box to the goal.
Hence, it's always recommended to use the mouse for playing. The advantages compared to keyboard playing are:
# With two clicks a box can be pushed to every possible square
# Most programs automatically calculates the best moves for the player. Hence the user doesn't have to think about how to move the player by keys.
# Some programs even show the squares a box can be pushed to. In this way it's easy to see if a box can be pushed to the selected position.
# The user can concentrate on pushes only instead of moves and pushes

Levels containing only one box are very simple to solve using the mouse: One just has to mark the box for pushing and then to choose the goal square as target.

Usually Sokoban levels are a lot more complicated.

Let's increase the difficulty step by step:
<code>
Level 3
########
# #
# $ .#
#@ $ .#
# $ .#
# #
########
</code>
Here the level contains 3 boxes. Nevertheless the level can easily be solved. Although every box can be pushed to each goal it doesn't matter which box is pushed to which goal. The boxes can just be pushed one after the other to any goal.

<code>
Level 4
########
# #. #
# $# #
# # @##
# # $##
# .##
########
</code>
This level is more complicated. The box under the player is close to a goal. Nevertheless it can't be pushed to the goal - this would result in a [[Deadlocks|deadlock]]. This level shows some problems one has to solve before it's possible to finish the level:
# Not every box can be pushed to every goal
# Boxes can't just be pushed to the nearest goal in every case
# Box pushes can create a [[Deadlocks|deadlock]]

<code>
Level 5
#########
## # #
#.$. $ #
# # ## #
# @$.$. #
#########
</code>

To solve this level the boxes have to be pushed to their goals in a specific order. Moreover one box has to be pushed away from its goal before it can be pushed to it.

<code>
Level 6
#########
# # .#
#@$ $ #
# $ ##..#
# #####
#########
</code>

This level is another example of the need to push a box away from its goal before the level can be solved. Additionally one box has to be "parked" until some other boxes have reached their goals. A situation where a box must be pushed but can't be pushed immediately to its goal occurs very often in Sokoban levels. Some of them are "parking" situations.
"Parking" means:
# a box must be pushed away from its goal
# after the box is pushed to its parking position another box has to be pushed
# parking the box at a specific position is required to solve the level

== Reverse play ==

Some Sokoban programs allow to play a puzzle backward.

Starting with all boxes on goal squares, the player pulls the boxes to return to the initial puzzle state.

Solutions found this way solve the standard puzzle when both the order and the direction of the moves are reversed.

This approach can help players better understand the puzzle structure and develop effective solving strategies.

Scientific research

2024-11-12T15:28:51Z

Matthias Meger: clarification that the challenge is due to TWO main factors: Large search tree AND the difficulty of finding a suitable heuristic for all puzzles.

==Scientific research==

Sokoban has been studied using the theory of computational complexity.

The computational problem of solving Sokoban puzzles was first shown to be [https://en.wikipedia.org/wiki/NP-hardness NP-hard]. Further work proved it is also [https://en.wikipedia.org/wiki/PSPACE-complete PSPACE-complete].

Sokoban puzzles are challenging for computers to solve because they require complex decision-making.

The two main factors that explain this difficulty:

* Exponentially growing search space: In Sokoban, there are usually multiple boxes, each with numerous possible moves. This causes the number of possible states to grow exponentially, making it challenging to find a solution within a reasonable time.

* Heuristic challenges: Given the vast search space, good heuristics are necessary for efficient problem-solving. However, it's challenging to develop a general heuristic that works well in all situations.

The Sokoban game provides a challenging testbed for developing and evaluating planning techniques.

The first documented automated solver was [[Rolling Stone solver | Rolling Stone]], developed at the University of Alberta.

Its core principles laid the groundwork for many newer solvers.
It employed a conventional search algorithm enhanced with domain-specific knowledge.

[https://festival-solver.site/ Festival], utilizing its FESS algorithm, was the first automatic solver to complete all 90 puzzles in the widely used XSokoban test suite ([https://sokoban-solver-statistics.sourceforge.io/statistics/OpenTestSuite/Festival%20-%20XSokoban.html Festival results]).

However, even the best automated solvers cannot solve many of the more challenging puzzles that humans can solve with time and effort.

Feature list : Duplicate Finder

2024-07-17T19:50:21Z

Matthias Meger: /* Additional Tools : Duplicate Finder */ removed old programs

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools : Duplicate Finder ==
{{LastREVISIONTIME}}




{| class="soko-table"
! colspan="6" | Additional Tools : Duplicate Finder !!
|- {{programs|3= |4= |6= }}
| {{tc}} | duplicate finder || built-in ||{{ni}} {{tip|(Alternatively has the feature '''duplicate levels exchange solutions''')|text=note|menu=yes}} || || || external utility
|-
| {{tc}} | search type || {{yes}} equal and similar levels. type: rotated and mirrored, dead squares removal, normalized walls, normalized pusher position. || || || || {{yes}} equal and similar levels. type: rotated and mirrored, dead squares removal, normalized walls, normalized pusher position.
|-
| {{tc}} | relaxed match options || {{yes}}{{tip|* with/without boxes * with/without goals * with/without interior walls * with/without exterior walls}} || || || || {{yes}}{{tip|* targets only, with optional threshold count * without pusher and boxes * walls only * without internal walls * floors only}}
|-
| {{tc}} | search current level duplicates || {{yes}} || || || || {{no}}
|-
| {{tc}} | duplicate levels preview || {{yes}} || || || || {{no}}
|-
| {{tc}} | search history || {{tip|a persistent user maintained "scanned folders" list is available|text=note}} || || || || {{no}}
|-
| {{tc}} | export report duplicates ||{{yes}}|| || || ||{{yes}}
|-
| {{tc}} | duplicate levels exchange solutions || {{yes}} {{tip| normalized levels exchange solutions, i.e., an exact match is not required.}} || {{yes}} {{tip|identical levels automatically exchange their solutions}} || || || {{yes}}
|}
[[#top|Top]]

<noinclude>

==Info==
=== Related pages ===

* [[Pruning_duplicate_positions|Pruning duplicate positions]]

[[#top|Top]]
</noinclude>

Feature list : Optimizer

2024-07-17T19:37:36Z

Matthias Meger: /* Additional Tools : Optimizer */ correct format as good as I can

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools : Optimizer ==
{{LastREVISIONTIME}}




{| class="soko-table feature-list"
! colspan="6" | Additional Tools - Optimizer !!
|- {{programs|2= |4= |5= |6= }}
| {{tc}} | optimizer || common optimizer plugins || || built-in
|-
| {{tc}} | optimizer running mode || background, allowing continued game play || || foreground, allowing continued game play
|-
| {{tc}} | optimization options (e.g., move-optimal, push-optimal) || optimization settings and options depend on the plugins, not the host program || || pushes/moves, moves/pushes, box changes, box lines
|-
| {{tc}} | task queue || {{yes}} || || {{no}}
|}
[[#top|Top]]

<noinclude>

==Info==
===Related pages===
[[Optimizer|Optimizer_Development]]

[[#top|Top]]
</noinclude>

Feature list : Solver

2024-07-17T19:33:49Z

Matthias Meger:

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools : Solver ==
{{LastREVISIONTIME}}




{| class="soko-table feature-list"
! colspan="5" | Additional Tools - Solver
|- {{programs|4=<div>[http://www.ic-net.or.jp/home/takaken/e/soko/index.html Takaken]</div>|5= |6= }}
| {{tc}} | solver || common solver plugins || common solver plugins || built-in || built-in
|-
| {{tc}} | solver running mode || background, allowing continued game play || foreground, blocking game play || foreground, blocking game play || foreground, blocking game play
|-
| {{tc}} | solution types (e.g., any, move-optimal, push-optimal) || solver strategies and options depend on the plugins, not the host program || solver strategies and options depend on the plugins, not the host program || push-optimal, push-optimal with best moves, move-optimal with best pushes || move-optimal, push-optimal
|-
| {{tc}} | task queue || {{yes}} || {{no}} || {{no}} || {{no}}
|}
[[#top|Top]]

<noinclude>

==Info==
===Related Pages===
[[Solver|Solver]]

[[#top|Top]]
</noinclude>

Feature list : Level Editor

2024-07-17T19:23:53Z

Matthias Meger: /* Additional Tools : Level Editor */ correct format

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools : Level Editor ==
{{LastREVISIONTIME}}




{| class="soko-table feature-list"
! colspan="6" | Additional Tools - Level Editor !!
|- {{programs|5= |6= }}
| {{tc}} | editor || built-in || built-in || built-in || built-in
|-
| {{tc}} | drawing objects || wall, box, goal, player || none, floor, goal, box-on-floor, box-on-goal, player-on-floor, player-on-goal, wall || wall, box, goal, player, floor || floor, goal, box, wall
|-
| {{tc}} | drawing tools || objects, eraser, rubber-band, fill || objects, pencil, drop, fill, line, rectangle, filled rectangle || objects || objects, move player, move box
|-
| {{tc}} | drawing logic || select object + click-and-drag the board to put objects on the board || select object + select drawing tool + click-and-drag the board to put objects on the board || select object + click-and-drag the board to put objects on the board || select object + click-and-drag the board to put objects on the board
|-
| {{tc}} | drawing logic inconveniences || the board jumps around on the screen when automatic scaling and positioning kick in || drawing with tools like lines and rectangles don't show the objects on the screen during the drawing process || the board jumps around on the screen when automatic scaling and positioning kick in || The "move" tool works for boxes and the player only, not for goals
|-
| {{tc}} | savegames and solutions for modified levels are retained after cosmetic changes (e.g., transformations and adding/removing extra floors/walls) || {{yes}} || {{no}} the savegames and solutions are still there in the files, but they are not applicable to the modified level || {{no}} || <big style="color: red;background:beige;">?</big> {{tip|will somebody with a full version check if it is "yes" or "no"|text=help}}
|-
| {{tc}} | undo || {{yes}} unlimited || {{yes}} unlimited || {{no}} || {{yes}} unlimited
|-
| {{tc}} | redo || {{yes}} unlimited || {{yes}} unlimited || {{no}} || {{no}}
|-
| {{tc}} | undo/redo logic || one complete transaction at a time || one complete transaction at a time || || one cell at a time
|-
| {{tc}} | undo/redo history is saved from one session to the next || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | undo/redo multiple transactions: interface || pull-down menu: 1,2,4,8,... transactions || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | undo/redo multiple transactions: preview || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | "rubber-band" area selection || {{yes}}(features: move, copy, paste, delete, transform, fill) || {{no}} || {{no}} || {{no}}
|- {{programs|5= |6= }}
| {{tc}} | board transformations || {{yes}} rotate counter-clockwise and clockwise, flip vertically and horizontally. || {{yes}} rotate clockwise, flip vertically || {{yes}} rotate counter-clockwise and clockwise, flip vertically and horizontally || {{yes}} rotate counter-clockwise and clockwise, flip vertically and horizontally
|-
| {{tc}} | resize board || {{un}} {{tip|the board is automatically positioned so it's possible to draw on all 4 sides}} || {{yes}} (via toolbar button: resize level) || {{un}} {{tip|the board is automatically positioned so it's possible to draw on all 4 sides}} || {{un}} {{tip|"move board" does not clip the level to a predefined size like, e.g., Sokoban++ does}}
|-
| {{tc}} | move board || {{un}} || {{yes}} || {{un}} || {{yes}}
|-
| {{tc}} | one-click switching between play/edit mode || {{yes}} || {{no}} use menu: game->mode || {{no}} || {{yes}} {{tip|partial implementation: no visible button but a keyboard shortcut "Alt+P"|text=partial}}
|-
| {{tc}} | board validation on switching from edit mode to play mode || {{yes}} || {{no}} all boards are playable || {{yes}} || <big style="color:red;background:beige">?</big>{{tip|will somebody with a full version check if it happens automatically|text=help}}
|-
| {{tc}} | customizable skin || {{yes}} format: simple image-based skins without seamless walls || {{yes}} same skin in edit mode and in play mode || {{yes}} same skin in edit mode and in play mode || {{yes}} same skin in edit mode and in play mode
|-
| {{tc}} | customizable button images || {{yes}} || {{no}} || {{yes}} || {{un}} {{tip|the editor uses menus and has no buttons}}
|-
| {{tc}} | button images automatically synchronized with skin images || {{no}} || {{no}} || {{yes}} || {{un}}
|-
| {{tc}} | windows clipboard copy/paste || {{yes}} || {{yes}} {{tip|partial implementation: imports / exports complete levels instead of copying / pasting sections to the existing "document", i.e., the board|text=partial}} || {{no}} || <big style="color: red;background:beige;">?</big> {{tip|(will somebody with a full version check if it works here; the demo version has it on the menu in the editor and it does not mention any restrictions, but it does not work)|width=260px|text=help}}
|-
| {{tc}} | internal clipboard with multiple items || {{yes}} unlimited, persistent, with preview || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | edit board as text || {{no}} || {{no}} || {{no}} || {{no}}
|}
[[#top|Top]]

Template:Programs

2024-07-17T19:23:12Z

Matthias Meger:

class="soko-table-title feature-title"
| <div style="width:120px;"> </div> || {{{1|<div>[http://sourceforge.net/projects/sokobanyasc/ Sokoban YASC]</div>}}} || {{{2|<div>[http://www.joriswit.nl/sokoban/ Sokoban++]</div>}}} || {{{3|<div>[http://www.sokoban-online.de JSoko]</div>}}} || {{{4|<div>[http://www.sourcecode.se/sokoban/ Sokoban for Windows]</div>}}} || {{{5|<div>[http://ygp.orgfree.com/sokoban.html YSokoban]</div>}}} || {{{6|<div>[http://www.sokosave.org/ SokoSave Desktop]</div>}}}
|-

Feature list : Additional Tools

2024-07-17T18:58:43Z

Matthias Meger: /* Additional Tools */ removed column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Additional Tools ==
{{LastREVISIONTIME}}




{| class="soko-table"
! colspan="6" | Additional Tools !! colspan="50" | <div align="right">Additional Tools</div>
|- {{programs}}
| {{tc}} | level editor ([[Feature_list_:_Level_Editor|see details below]]) || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||{{no}} || {{no}}
|-
| {{tc}} | solver ([[Feature_list_:_Solver|see details below]]) || {{yes}} common solver plugins (allowing continued game play) || {{yes}} common solver plugins (blocking game play) || {{yes}} built-in (blocking game play) || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | optimizer ([[Feature_list_:_Solver#Additional_Tools_:_Optimizer|see details below]]) || {{yes}} common optimizer plugins (allowing continued game play) || {{no}} || {{yes}} built-in (blocking game play) || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | locate and browse duplicates or look-alikes ([[Feature_list_:_Duplicate_Finder|see details below]]) || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}} external program [http://geocities.com/ygp_bg/sokodup.zip Soko-Dup] can be downloaded || {{no}}
|-
| {{tc}} | skin graphics editor || {{no}} skin script editor available || {{no}} skin script editor available || {{no}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | level generator || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | optimizer for unnecessary moves between pushes || {{yes}} automatically during game-play || {{yes}} manually via menu || {{yes}} automatically during game-play || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | level file converters || {{yes}} {{tip|SokoMind (including solutions), Sokoban for Windows by Björn Källmark (including solutions), Sokofan (including solutions)|width=250px|text=file types}} || {{yes}} {{tip|ASCII (*.txt, *.xsb, *.screen, *.skm, *.scb), Sokoban (*.sls), Visual Sokoban 1 and 2 (*.pak), WinSoko (*.rdf), Games 4 Brains (*.lp0), Mark McIntyres Soko (*.sok), XML Sokoban (*.xml), Sokoban XP (*.sxl), Games 4 Brains Sokoblue (*.dat), Icons (*.ico), Björn Källmark's xml format (*.slc)|width=270px|text=file types}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | image snapshot capture || {{no}} || {{yes}} miniature level bitmap with 1 pixel per square; via menu: level->copy level || {{no}} || {{no}} || {{no}} || {{no}}
|- {{programs}}
|}
[[#top|Top]]

Feature list : Miscellaneous

2024-07-17T18:57:50Z

Matthias Meger: /* Miscellaneous */ removed column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Miscellaneous ==
{{LastREVISIONTIME}}




{| class="soko-table feature-list"
! colspan="6" | Miscellaneous !! colspan="50" | <div align="right">Miscellaneous</div>
|- {{programs}}
| {{tc}} | builtin help and program information || {{yes}} rich text document (rtf) || {{yes}} html pages (html) || {{yes}} Java help || {{yes}} html pages (htm) || {{yes}} ascii text document || {{yes}} html page (html)
|-
| {{tc}} | context sensitive help || {{no}} || {{yes}} || {{yes}} {{tip|Pressing the help key (F1) opens the help}} || {{no}} {{tip|however, the web-page says otherwise|text=note}} || {{no}} || {{no}}
|-
| {{tc}} | customizable language || {{no}} || {{yes}} || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | languages || English || English, Afrikaans, Danish (embarrassing), Dutch, German, Greek, Finnish, French, Italian, Polish, Portugese, Russian, Spanish (Spain, Argentina), Turkish, Slovenian, Swedish || English, German, Chinese (Simplified), Spanish, Dutch || English || English, Bulgarian, Chinese (Simplified, Traditional), German, Spanish || English
|-
| {{tc}} | builtin solutions || {{yes}} {{tip|all levels ship with builtin solutions}} || {{yes}} {{tip|not all levels ship with builtin solutions}} || {{yes}} {{tip|not all levels ship with builtin solutions}} || {{yes}} {{tip|not all levels ship with builtin solutions}} || {{no}} || {{no}}
|-
| {{tc}} | file type associations (optional) || {{no}} || {{yes}} .sls, .pak, .rdf, .lp0, .xsb, .sok, .sxl, .slc || {{no}} || {{no}} || {{no}} || {{yes}} .sokomaze, .xsb, .sokohex, .hsb, .sokotri, .tsb, .sokosave Windows, Mac OS X
|-
| {{tc}} | accessibility for portable version || {{no}} || {{no}} || {{no}} || {{no}} || {{yes}}{{tip|compatible installation: yes system modification: no generated data: saves the files created in the removable device. additional: edition for mobile phone, java MIDP 2.0 only.|width=200px}} || {{no}}
|- {{programs}}
|}
[[#top|Top]]

<noinclude>

==Info==
===Portable software===
''From Wikipedia, the free encyclopedia'' 

To be considered '''truly portable''', a software program must: 
<ul>
<li>Not require any form of formal installation to be carried out on any computer before it can be used, with the release package only needing to be decompressed directly to removable media before use (if it has to be installed first, and requires it's files to be manually copied to removable media, it's clearly not designed to be portable!). For example, software which is supplied as an InstallShield package could not be considered portable, though a ZIP archives containing an executable would be.</li>
<li>Settings are stored with, and can be carried around with, the software (i.e. they are written to the USB drive). If the registry is used to store settings; the application's configuration isn't portable, and must be set up on every PC it is used on</li>
<li>Leaves a zero (or near-zero) "footprint" on any PC it's run on after being used. i.e. All temporary files/registry settings should be removed once the program has exited, and files created by the user can be saved directly to the same removable media as the application is stored on.</li>
</ul>
Generally, smaller utility/toolkit software is inherently fairly portable; though larger applications are sometimes changed in order to allow a portable versions to be released (e.g. FirefoxPortable)

</noinclude>

Feature list : Multi-player Mode

2024-07-17T18:57:18Z

Matthias Meger: /* Multi-player Mode */ emoved column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Multi-player Mode ==
{{LastREVISIONTIME}}




{| class="soko-table feature-list"
! colspan="6" | Multi-player Mode !! colspan="50" | <div align="right">Multi-player Mode</div>
|- {{programs}}
| {{tc}} | [[Feature_list_:_Multi-player_Mode#Multi-player|multi-player]] || {{no}} || {{yes}}(options: create new player, change player) || {{no}} || {{yes}}(options: create new player, change player) || {{yes}}(options: create new player, change player) || {{no}}
|-
| {{tc}} | edit player information (e.g. name, email, country) || {{no}} || {{no}} || {{no}} || || {{no}} || {{yes}} {{tip|only when recording high score}}
|-
| {{tc}} | display personal high-scores || {{yes}} {{tip|cramped implementation and disabled by default. Enable it in "open" window via menu -> show solutions}} || {{yes}} via menu: level -> choose || {{no}} || {{yes}} via menu: view -> scores and solutions || {{yes}} drop-down list || {{yes}} via menu: help -> scores
|-
| {{tc}} | compare high-scores of all the players || {{ni|/a|Not applicable to single-player programs.}} || {{yes}} general and personal scores || {{ni|/a|Not applicable to single-player programs.}} || {{yes}}ranking with all the players || {{no}} || {{ni|/a|Not applicable to single-player programs.}}
|-
| {{tc}} | save and restore the player profiles (e.g. high-scores, settings) || {{ni|/a|Not applicable to single-player programs.}} || {{yes}} player position file (*.sav) || {{ni|/a|Not applicable to single-player programs.}} || ||{{yes}} player info file (*.SokoInfo) || {{ni|/a|Not applicable to single-player programs.}}
|-
| {{tc}} | remember each player's session (e.g. level, skin, quicksaves) {{tip|not to be confused with a single player program's ability to do the same. Feature implemented in Sokonline.|text=note}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|- {{programs}}
|}
[[#top|Top]]

<noinclude>

<h2>Info</h2>
=== Multi-player ===

This modality is useful for the competitions, each user can have his own configurations. As the personalization, with their scores, personal information, as the option of sending their solutions via e-mail.

These are options for the soko-programs that point, to give the option for competitive players that participate in the challenges of internet.

'''Related programs''' 
[http://sokoban.online.fr/mon_player.html Sokonline]

[[#top|Top]]
</noinclude>

Feature list : Web-based Support

2024-07-17T18:56:24Z

Matthias Meger: /* Web-based Support */ removed column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Web-based Support ==



{| class="soko-table feature-list"
! colspan="6" | Web-based Support !! colspan="50" | <div align="right">Web-based Support</div>
|- {{programs}}
| {{tc}} | website || [http://sourceforge.net/projects/sokobanyasc/ official website] || [http://www.joriswit.nl/sokoban/ official website]|| [http://www.sokoban-online.de official website] || [http://www.sourcecode.se/sokoban/ official website] || [http://ygp.orgfree.com/sokoban.html official website] || [http://www.sokosave.org/ official website]
|-
| {{tc}} | forum || {{ni}} || {{ni}} || {{ni}} || [http://www.sourcecode.se/sokoban/forum official forum] || {{ni}} || [http://www.high-speed-software.com/sokosave/forum/ official forum]
|-
| {{tc}} | additional level packs || {{un}} {{tip|practically all text-based levels for download are supported}} || {{un}} {{tip|practically all text-based levels for download are supported}} || {{un}} {{tip|practically all text-based levels for download are supported}} || {{yes}}(.slc files) || {{un}} {{tip|practically all text-based levels for download are supported)}} || {{un}} {{tip|practically all text-based single-level files for download are supported)}}
|-
| {{tc}} | additional solutions || {{no}} || {{yes}} || {{no}} || || {{yes}}[http://ysokoban.atspace.com/ ysokoban solutions] || {{no}}
|-
| {{tc}} | additional skin packs || {{un}} {{tip|all major skin formats for download are supported}} || {{yes}} || {{no}} || {{no}} {{tip|all available skins ship with the program}} || {{yes}} || {{no}}
|-
| {{tc}} | additional add-ons || {{yes}} utilities || {{yes}}language packs, solver-plugins, utilities || {{no}} || || {{yes}} utilities || {{yes}} utilities
|-
| {{tc}} | automatic update || {{no}} || {{no}} || {{yes}} automatic check for updates || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | option to jump to the official website || {{yes}} || {{yes}} || {{no}} || {{yes}} || {{no}} || {{yes}}
|}
[[#top|Top]]

Feature list : Moves Management

2024-07-17T18:55:45Z

Matthias Meger: /* Moves Management */ removed column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Moves Management ==
{{LastREVISIONTIME}}




{| class="soko-table feature-list"
! colspan="6" | Moves Management !! colspan="50" | <div align="right">Moves Management</div>
|- {{programs}}
| {{tc}} | copy/paste moves (normal) || {{yes}} || {{yes}} || {{yes}} || {{yes}} {{tip|partial implementation: solutions only, not savegames flaw: imported solutions are lost when the program exits flaw: imported moves are listed as solutions even if this is not the case|width=200px}} || {{yes}} || {{no}}
|-
| {{tc}} | copy/paste moves (run-length-encoded) || {{yes}} || {{yes}} partial: paste only || {{yes}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | copy moves after the current position || {{yes}}via keyboard: Ctrl+B || {{yes}}via menu: position -> copy || {{yes}} Ctrl+Shift+M || {{no}} || {{yes}}via keyboard: Ctrl+Alt+C || {{no}}
|-
| {{tc}} | paste moves as continuation of current position || {{yes}} || {{yes}} || {{yes}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | rotate and/or flip moves || {{no}}{{tip|board rotations and flips automatically synchronize existing savegames and solutions}} || {{no}} external program [http://www.joriswit.nl/sokoban/junk/solutionrotator.zip Solution Rotator] can be downloaded || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | edit move information (e.g, title, author, comment) || {{yes}}via snapshot window || {{yes}}via menu: position->save; properties: title || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | recreate maps from solutions || {{yes}} multiple solutions, with titles and info || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | load and save moves || sok (ascii text file, levels); clipboard: import/export || xht,txt (ascii text file, solutions), mov (sokofun movie); clipboard: import/export || sok (ascii text file, levels); clipboard: import/export || gam (xml text file, level); clipboard: import/export || txt (ascii text file, levels); clipboard: import/export || sokosave (savegame file)
|- {{programs}}
|}
[[#top|Top]]

<noinclude>

== Related pages ==
* [[Solution_format]] (German language)

== SokRFI - Sokoban Requests for Implementation ==


{| class="soko-table"
|-
! colspan="50" | Moves Management : SokRFI - Sokoban Requests for Implementation
|-
| width="120" {{tc}} | Feature || {{tc}} | Description
|-
|{{tc}}| animation snapshots capture: solutions || Sokoban++ offers a utility for this feature. (External program [http://www.joriswit.nl/sokoban/junk/ Sokoban Animator] can be downloaded)
|-
|{{tc}}| export solution as animation || Free formats: 
Text file:
:Scalable Vector Graphics ([http://www.w3.org/Graphics/SVG/ SVG]).
:Implementation with a [http://www.treebuilder.de/svg/sokoban/sokobano.svg template SVG].
Image file:
:Animated PNG ([http://wiki.mozilla.org/APNG_Specification APNG]) available with Firefox 3.
:[http://easysok.sourceforge.net EasySok] as alternative can save all the snapshots in a movie MNG.
|}
[[#top|Top]]
</noinclude>

Feature list : Level Management

2024-07-17T18:55:07Z

Matthias Meger: /* Level Management */ removed column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Level Management ==
{{LastREVISIONTIME}}




{| class="soko-table feature-list"
! colspan="6" | Level Management !! colspan="50" | <div align="right">Level Management</div>
|- {{programs}}
| {{tc}} | copy/paste level(s) (normal) || {{yes}} || {{yes}}{{tip|partial implementation of import: one level at a time; works for raw boards without meta data only}} || {{yes}}{{tip|levels can also be pasted by using drag&drop of a level file}} || <big style="color: red;">?</big>{{tip|Will somebody with a full version check if it works here the demo version has it on the menu in the editor and it does not mention any restrictions, but it does not work|text=Help}} || {{yes}} {{tip|flaw: pasted levels are not saved|text=flaw}} || {{no}}
|-
| {{tc}} | copy/paste levels (run-length-encoded) || {{yes}} || {{no}} || {{yes}} || {{no}} || {{yes}} {{tip|flaw: pasted levels are not saved |text=flaw}} || {{no}}
|-
| {{tc}} | copy map (current state) || {{yes}}via [ CTRL + click "tools"] and editor || {{yes}} || {{yes}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | copy level(s) with solution(s) || {{yes}}(multiple) || {{no}} || {{yes}}(single) || {{no}} || {{yes}}(single) || {{no}}
|-
| {{tc}} | paste level(s) with solution(s) || {{yes}}(multiple) || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | edit level information (e.g., title, author) || {{yes}} via "open" window || {{yes}} via menu: level->about; properties: title, author, comment || {{no}} || {{yes}} via menu: file->edit mode + file->attributes; properties:title, description, copyright, email, website || {{no}} || {{no}}
|-
| {{tc}} | edit levelset information (e.g., title, copyright) || {{no}} || {{yes}} via menu: levelset->about; properties: title, author, copyright, comment || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | load multiple files || {{no}} || {{yes}} || {{no}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{yes}}
|-
| {{tc}} | merge level files || {{yes}} (merge is a feature in the "open" window: menu -> file conversion...) || {{yes}}(via: open and select multiple files.) || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | recent levels history || {{yes}} 25 items {{tip|holding a unified recent file history for all loaded file-types, e.g., levels and background images}} || {{no}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{un}} {{tip|with all loaded levelsets in a list it is just as easy to browse the whole list}} || {{no}}
|-
| {{tc}} | saves levels with format || {{yes}} sok (.sok) || {{yes}} sok (.sok), xsokoban (.txt, .xsb), games 4 brains (.lp0), xml text file (.sls) || {{yes}} sok (.sok) || {{yes}} xml text file (.sls) || {{no}} || {{yes}} savegame text file (.sokosave)
|-
! colspan="6" | Level Management : Import and Export for Internet !! colspan="50" | <div align="right">Level Management : Import and Export for Internet</div>
|- {{programs}}
| {{tc}} | import levels with hyphens "-" or underscores "_" || {{yes}} via clipboard and load level || {{yes}} via clipboard and load level || {{yes}} via clipboard and load level || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | export levels with hyphens "-" or underscores "_" || {{yes}}via clipboard || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | stripping leading ">" characters || {{yes}} (all leading ">" characters are stripped) || {{no}} || {{yes}} (stripping leading ">" characters: boards, not moves) || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | accepts alternative characters for boards || {{yes}}characters: p,P,b,B,o || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|}
[[#top|Top]]

<noinclude>

== Related pages ==
* [[Level_format]]

== SokRFI - Sokoban Requests for Implementation ==


{| class="soko-table feature-list"
|-
! colspan="50" | Level Management : SokRFI - Sokoban Requests for Implementation
|-
| width="120" {{tc}} | Feature || {{tc}} | Description
|-
|{{tc}}| split levelset || SokoSave offers a utility for this feature. (External program [http://www.high-speed-software.com/sokosave/sokosavedesktop/sokosplit/ SokoSplit] can be downloaded)
|-
|{{tc}}| export levels to internet ||
 Export levels to internet 

This feature can be used to publish level(s) in a web-site. 

The export can have different variants: 
<ul>
<li>Generating the strings with code HTML. 
With links to download levels or thumbnails of each level.</li>
<li>Generating the strings with code [http://web.singnet.com.sg/~fclim/sbml/index.html SBML] (SokoBan Markup Language). 
Exporting with this language, levels can be customized by the user for the graphic representation of the maps, as well as provide a meta-information semantics of each level.
</li>
</ul>

<hr>Alternative development 
See [[SokRFI - Export Levels to Internet]].

<hr>Utility Sokoban++ offers a utility for this feature. (External program [http://www.joriswit.nl/sokoban/junk/ Sokoban Website Generator] can be downloaded) 

|}
[[#top|Top]]
</noinclude>

Feature list : Map Viewing

2024-07-17T18:52:24Z

Matthias Meger: /* Map Viewing */ removed column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Map Viewing ==
{{LastREVISIONTIME}}




{| class="soko-table"
! colspan="6" | Map Viewing !! colspan="50" | <div align="right">Map Viewing</div>
|- {{programs}}
| {{tc}} | level browser with preview || {{yes}} one level at a time || {{yes}} block graphic miniatures of all loaded levels || {{yes}} block graphic miniatures of all loaded levels || {{yes}} block graphic miniatures of all levels in a collection (customizable miniature size) || {{no}} || {{no}}
|-
| {{tc}} | resize skin to fit window || {{yes}} always || {{yes}}skin dependent || {{yes}} always || {{yes}} {{tip|flaw: Windows has 2 font settings, small (default) and large, and this only works for small fonts|text=flaw}} || {{yes}} || {{no}}
|-
| {{tc}} | resize window to fit map || {{un}} {{tip|map always fits in window}} || {{no}} || {{un}} {{tip|map always fits in window}} || {{yes}} {{tip|flaw: Windows has 2 font settings, small (default) and large, and this only works for small fonts|text=flaw}} || {{yes}} optional || {{yes}} always
|-
| {{tc}} | [[Feature_list_:_Map_Viewing#Level_scrolling|levels larger than window: scrolling]] || {{un}} || {{no}} || {{un}} || {{yes}} via scrollbars. {{tip| Windows has 2 font settings, small (default) and large, and this only works for small fonts|text=flaw}} || {{yes}} {{tip|via scrollbars with an option to autofollow (move scrollbars automatically)}} || {{un}}
|-
| {{tc}} | one-click browse levels || {{yes}} previous, next {{tip|in all level files in current level directory, with wrap-around}} || {{yes}} previous, next {{tip|in currently loaded levels, without wrap-around}} || {{yes}} previous, next {{tip|in current collection, with wrap-around}} || {{yes}} previous, next {{tip|in all loaded level files, with wrap-around}} || {{yes}} {{tip| implementation: keyboard shortcuts for: previous, next, first, last (in current collection, without wrap-around)|text=partial}} || {{yes}} next, without wrap-around
|-
| {{tc}} | one-click browse files || {{no}} || {{no}} || {{no}} || {{yes}} drop-down list with all level collections || {{yes}} drop-down list with visited level collections || {{no}}
|-
| {{tc}} | search for unsolved level || {{yes}} previous, next {{tip|in all level files in current level directory, with wrap-around}} || {{yes}} previous, next, random {{tip|in currently loaded levels, without wrap-around}} || {{yes}} previous, next {{tip|in current collection, with wrap-around}} || {{yes}} {{tip|partial implementation: auto-advance after having solved a level finds an unsolved level if settings is "unsolved levels only"|text=partial}} || {{yes}} previous, next {{tip|in current collection, without wrap-around}} || {{no}}
|-
| {{tc}} | rotate and mirror level-map || {{yes}} persistent, with reset option {{tip|savegames and solutions are automatically synchronized with current transformation}} || {{yes}} session (partial implementation: use editor) {{tip|savegames and solutions are specific to each transformation}} || {{yes}} session, with reset option {{tip|savegames and solutions are automatically synchronized with current transformation}} || {{yes}} <big style="color: red;">?</big>{{tip|Will somebody with a full version check if it is session, with reset option or persistent, with reset option additionally check if savegames and solutions are automatically synchronized with current transformation or savegames and solutions are specific to each transformation|width=300px|text=Help}} || {{yes}} session, with reset option {{tip|savegames and solutions are automatically synchronized with current transformation}} || {{no}}
|-
| {{tc}} | multiple windows, one per level || {{no}} || {{no}} || {{no}} || {{yes}}via tabs. multiple levels can be opened in separate tabs. || {{no}} || {{yes}}
|-
| {{tc}} | multiple views of a level || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | full screen || {{no}} || {{no}} || {{no}} || {{no}} || {{yes}} via : keyboard: F11 || {{no}}
|- {{programs}}
|}
[[#top|Top]]

<noinclude>

<h2>Information</h2>
=== Level scrolling ===

levels larger than window: scrolling 
levels larger than window: scrollbars 

Briefly, the first line is there to give a program the chance to tell that it has a scroll feature, and the second line is there to tell if the program does it the right way - with scrollbars.

Since the first graphical user interfaces emerged, scrollbars have been used for depicting the situation where a document doesn't fit in the window, so the user can rightfully expect to find that logic (or something equally user-friendly) in a Sokoban program as well.

Therefore, it's embarrasing for programs that requires scrolling if they don't have scrollbars or something equivalent. The line "levels larger than window: scrollbars" must be listed so readers can see this major design flaw, and so new programmers are reminded that they definitely should do better.

On the other hand, Sokofan deserves credits for at least having a scroll feature, despite the fact that it's not done the right way with scrollbars. The user doesn't get any visible clue that the board is bigger than the window, and the user must read the instructions to find the keyboard and mouse/key combinations that controls the scrolling.

So the line "levels larger than window: scrolling" is there to give Sokofan a chance to tell that it indeed has a scroll feature, even though it's not as user-friendly as the user rightfully can expect from a good Sokoban clone.

-bd

=== Multiple views of a level ===
A user often works on several alternative paths at the same time. It would be a great help if each of them was fully visible. For instance, multiple views are beneficial during the process of optimizing existing solutions.

=== SokRFI - Sokoban Requests for Implementation ===



{| class="soko-table feature-list"
|-
! colspan="50" | Map Viewing : SokRFI - Sokoban Requests for Implementation
|-
| width="120" {{tc}} | Feature || {{tc}} | Description
|-
|{{tc}}| show/hide redundant walls ||It fills jagged wall edges, fills unused "tubes", removes redundant walls, unused boxes, and unused goals. Implemented in [http://sokoban.ws/usokoban/usokoban.htm USokoban] as 'Normalize level'.
|}

[[#top|Top]]
</noinclude>

Feature list : Skin Features

2024-07-17T18:51:10Z

Matthias Meger: /* Skin Features */ removed column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Skin Features ==
{{LastREVISIONTIME}}




{| class="soko-table"
! colspan="6" | Skin Features !! colspan="50" | <div align="right">Skin Features</div>
|- {{programs}}
| {{tc}} | customizable skin || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}}
|-
| {{tc}} | skin formats || {{yes}} meta-script language {{tip|includes scripts for importing the following skin formats: common sokoban skin images (YSokoban), Sokoban++ skin scripts, Sokofan skin scripts, Visual Sokoban skin scripts, Sokoban for Windows skin scripts (Björn Källmark), Sokoban BDE images, SuperSoko skin images, SokoStation4 skin scripts JSoko skin scripts|width=210px}} || {{yes}} Sokoban++ skin scripts (ini) || {{yes}} two built-in skins || {{yes}} Sokoban for Windows skin scripts (skn) || {{yes}} common sokoban skin images (YSokoban) || {{no}}
|-
| {{tc}} | resizeable skins || {{yes}} || {{no}} || {{yes}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | pseudo-3D skins (sokoban++ style) || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | legal moves box animation (ysokoban style) || {{yes}} || {{no}} || {{no}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | legal moves player animation (ysokoban style) || {{yes}} || {{no}} || {{no}} || {{no}} ||{{yes}} || {{no}}
|-
| {{tc}} | solution animation (ysokoban style) || {{yes}} || {{no}} || {{no}} || {{no}} || {{yes}} || {{no}}
|-
| {{tc}} | animation frame extrapolation (morphing) || {{yes}} 30 frames || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | directional player || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | directional player can return to an "at ease" position || {{no}} || {{no}} || {{no}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | directional box|| {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | directional box can return to an "at ease" position || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | support for seamless walls (as opposed to discrete walls) || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}}
|-
| {{tc}} | walls can be transparent || {{no}} || {{no}} skin dependent || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | floors can be transparent || {{yes}} || {{no}} skin dependent || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | skin browser with preview || {{yes}} image-based skins; not scripted skins || {{no}} || {{yes}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | recent skins history || {{yes}} || {{yes}} || {{no}} || {{un}} {{tip|with all skins in a list it is just as easy to browse the whole list}} || {{no}} || {{no}}
|-
| {{tc}} | quick browse skins || {{yes}} menu: default, recent skins; keyboard shortcuts: next, default || {{yes}} menu: default, recent skins || {{yes}} menu: skin list || {{yes}} menu: skin list || {{yes}} use F4-F8 to select one of the loaded skins || {{no}}
|- {{programs}}
|}
[[#top|Top]]

Feature list : Customizing

2024-07-17T18:43:17Z

Matthias Meger: /* Customizing */ removed extra column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Customizing ==
{{LastREVISIONTIME}}




{| class="soko-table"
! colspan="6" | Customizing !! colspan="50" | <div align="right">Customizing</div>
|- {{programs}}
| {{tc}} | settings interface || {{yes}} graphical user interface (tree-view) || {{yes}} graphical user interface (tabbed notebook view) || {{yes}} graphical user interface || {{yes}} graphical user interface (tabbed notebook view) || {{yes}} graphical user interface (window) || {{yes}} graphical user interface (window)
|-
| {{tc}} | configurable statusbar (e.g., level title, moves, pushes) || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | configurable game state graphics (e.g., moves/pushes) || {{yes}} fonts, colours, buttons (static layout) || {{yes}} skin graphics (configurable layout) || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | customizable cursors || {{no}} || {{yes}} graphics, skin dependent || {{no}} || {{yes}} small/large built-in cursors || {{no}} || {{no}}
|-
| {{tc}} | customizable mouse actions || {{yes}}(only right-click) || {{no}} || {{no}} || || {{yes}}(buttons: left, middle, right) || {{no}}
|-
| {{tc}} | customizable sound events || {{yes}} independent || {{yes}} skin dependent || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | background music || {{no}}  || {{no}} || {{no}} || {{yes}} source: folder formats: midi, mp3. || {{no}} || {{no}}
|-
! colspan="6" | Customizing : Background Image!! colspan="50" | <div align="right">Customizing : Background Image</div>
|- {{programs}}
| {{tc}} | customizable backgrounds || {{yes}} independent, with preview || {{yes}} skin dependent || {{yes}} independent || {{yes}} skin dependent || {{yes}} independent, with preview || {{no}}
|-
| {{tc}} | background control || {{yes}} source: color, image; (image view: center, scale, stretch, tile) || {{yes}} source: color, image; (image view: center, stretch, tile) || {{no}} || {{yes}} source: image; (image view: tile) || {{yes}} source: image; (image view: center, stretch, tile) || {{no}}
|-
| {{tc}} | quick browse backgrounds || {{no}} "slow" browse via settings || {{no}} || {{yes}} browse with preview via settings || {{no}} || {{yes}} tool button with drop-down list || {{no}}
|}
[[#top|Top]]

<noinclude>

== SokRFI - Sokoban Requests for Implementation ==


{| class="soko-table feature-list"
|-
! colspan="50" | Customizing : SokRFI - Sokoban Requests for Implementation
|-
| width="120" {{tc}} | Feature || {{tc}} | Description
|-
|{{tc}}| background-image changer || This feature is for the users that look for to always have a different background, playing a level. It is applied to the following events in the program: 
• On program start-up • After solving a level. 
For the convenience of users and updates are groups all backgrounds in a single folder. One can also choose the mode in that the background will be changed: 
• Next image. • Previous image. • Random image.Implemented in Sokomind
|}
[[#top|Top]]
</noinclude>

Feature list : Game Play

2024-07-17T18:37:12Z

Matthias Meger: /* Game Play */ removed column

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Game Play ==
{{LastREVISIONTIME}}




{| class="soko-table"
! colspan="6" | Game Play !! colspan="50" | <div align="right">Game Play</div>
|- {{programs}}
| {{tc}} | autosave best solutions || {{yes}} tiebreaking: moves, pushes, secondary metrics || {{yes}} tiebreaking: moves, pushes || {{no}} || {{yes}} tiebreaking: moves, pushes || {{yes}} tiebreaking: moves, pushes, secondary metrics || {{no}}
|-
| {{tc}} | autosave solutions options || always autosaves better solutions; inferior solutions are discarded || autosave solutions options: never/always/if better/ask; existing solutions are kept || {{no}} || autosave solutions options: none/best 5/best 10/all || always autosaves better solutions; inferior solutions are discarded || optionally saves game when solved; only one solution per saved game
|-
| {{tc}} | push or move optimized pathfinding || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}}
|-
| {{tc}} | move animation modes || smooth, cell by cell, instant || cell by cell, instant || cell by cell || smooth || cell by cell, instant {{tip|(instant with [[Feature_info#Choice points|choice points]] is listed but is too fast to be useful)|menu=yes}} || cell by cell, instant
|-
| {{tc}} | mouse move control: drag and drop || {{yes}} with reachable squares || {{yes}} without reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{no}}
|-
| {{tc}} | [[#Mouse_Move_Control:_Select_and_drop|mouse move control: select and drop]] || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} with reachable squares || {{yes}} without reachable squares
|-
| {{tc}} | [[#Mouse_Move_Control:_Drag_and_track|mouse move control: drag and track]] || {{no}} experimental click-less tracking available || {{no}} || {{no}} || {{no}} || {{no}} || {{yes}}
|-
| {{tc}} | reverse mode play starting at end position (pull instead of push) || {{yes}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | show secondary metrics (box-pushes, box-changes and pushing-sessions) || {{yes}} display: mouse over || {{yes}} display: optional, configurable || {{no}} || {{no}} || {{yes}} || {{yes}}
|-
| {{tc}} | [[#Lowerbound_of_solution_length_regarding_pushes|show a lowerbound of the solution length]] || {{no}} || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | timing || {{yes}} optional; optional idle time threshold || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | move player through boxes ||{{no}}|| {{no}} || {{yes}} || {{no}} || {{yes}} target: reachable squares through boxes. figure: small black square. via: options -> go through boxes. || {{no}}
|-
! colspan="6" | Game Play : Legal moves !! colspan="50" | <div align="right">Game Play : Legal moves</div>
|- {{programs}}
| {{tc}} | show player's reachable squares|| {{yes}} figure: transparent small skin graphics || {{no}} || {{yes}} figure: transparent small skin graphics || {{yes}} || {{yes}} figure: small round blobs || {{no}}
|-
| {{tc}} | show box's reachable squares || {{yes}} figure: transparent small skin graphics || {{yes}} figure: skin graphics, independent of box || {{yes}} figure: transparent small skin graphics || {{yes}} || {{yes}} figure: small round blobs || {{no}}
|-
| {{tc}} | show pushable boxes || {{yes}} dynamically by clicking a wall. figure: configurable border || {{no}} || {{no}} || {{no}} || {{yes}} permanent with CTRL+F9. dynamically by clicking a wall. figure: skin graphics, independent of box || {{no}}
|-
| {{tc}} | show [[Deadlocks#Dead square deadlocks|dead squares]] || {{yes}}figure: configurable shaded square || {{no}} || {{yes}}figure: darker shaded square || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | [[#Simple deadlock detection|simple deadlock detection]] || {{yes}} dead squares, freezing boxes || {{no}} || {{yes}} dead squares, freezing boxes || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | [[#Advanced deadlock detection|advanced deadlock detection]] || {{yes}} {{tip|bipartite: n boxes for m goals; 1 goal for n boxes; corrals: precalculated at level load time + 100 ms search after a push}} || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}}
|-
! colspan="6" | Game Play : History !! colspan="50" | <div align="right">Game Play : History</div>
|- {{programs}}
| {{tc}} | undo/redo || unlimited || unlimited || unlimited || unlimited || unlimited || unlimited
|-
| {{tc}} | undo all || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} press [esc]|| {{yes}}
|-
| {{tc}} | redo all || {{yes}} || {{no}} || {{yes}} || {{no}} ||{{no}} || {{yes}}
|-
| {{tc}} | replay || {{yes}} forwards and backwards || {{yes}} forwards || {{yes}} forwards || {{yes}} forwards and backwards || {{yes}} forwards (solutions only) || {{yes| via trackbar dragged to any position replays to that position}}
|-
| {{tc}} | replay ergonomics || unified start/stop button; click anywhere to stop; keyboard shortcuts available; speed and direction can be changed during replay || separate start/stop buttons; click stop-button to stop; keyboard shortcuts available || unified start/stop button; click anywhere to stop; speed can be changed during replay || || with start/stop: CTRL+F2 to begin. SPACE to replay to next box-change. without start/stop: F2 || trackbar represents replay history; drag trackbar to control replay; click anywhere, click [stop] button, or press [esc] to stop
|-
| {{tc}} | mousewheel undo/redo/replay support || {{yes}} combined moves || {{yes}} single step or optional combined moves || {{yes}} combined moves || {{no}} || {{yes}} combined moves || {{no}}
|-
| {{tc}} | browse move history || {{yes}} trackbar (choice-points, with preview) || {{yes}} trackbar (all moves, with preview) || {{yes}} trackbar (choice-points, with preview) || {{no}} || {{no}} || {{yes}} trackbar (all moves, no preview)
|-
| {{tc}} | quicksave slots || {{yes}} unlimited (interface: graphical, window, thumbnail preview) || {{yes}} unlimited (interface: graphical, pop-up, list) || {{no}} || {{yes}} 3 (interface: graphical) || {{no}} || {{no}}
|-
| {{tc}} | one-click load quicksaves || {{yes}} keyboard: press [Enter] to load currently selected snapshot; mouse: double-click a snapshot on the list || {{no}} || {{no}} || {{yes}} || {{no}} || {{no}}
|-
| {{tc}} | remember last session || {{yes}} file, level, history with redo, position {{tip|position is optional, default "off", additionally, up to 25 recent (file, level)}} || {{yes}} file, level || {{yes}} file, level || {{yes}} file, level, history without redo, position || {{yes}} file, level, history without redo, position || {{no}}
|- {{programs}}
|}

[[#top|Top]]

<noinclude>

== Info ==

=== Choice points ===

A choice point in the game is when the player changes from one box to another, or finishes a series of moves that pushed a box in a single direction.

Several programs have replay features related to choice points. Sokofan, for example, has replay buttons (called "smart do/undo") to move from one choice point to another. Another example is the game history browser in Sokoban YASC which works with choice points instead of individual moves.

=== Mouse Move Control: Select and drop ===
Lift and drop. Left click on a box to lift it, move to the wanted position and left click again to drop. Lift and drop is easier for long moves than the drag and drop.

=== Mouse Move Control: Drag and track ===
Point at the pusher with the mouse and move it in the direction you want. The pusher will track your movements.

=== Simple deadlock detection ===

Simple deadlock detection deals with deadlock types that require rather simple analysis of the board and the game state. Good examples are:

* [[Deadlocks#Dead square deadlocks|Dead squares]]

* [[Deadlocks#Freeze deadlocks|Freeze deadlocks]]

=== Advanced deadlock detection ===

Advanced deadlock detection deals with deadlock types that require quite sophisticated computations. Good examples are:

* [[Deadlocks#Bipartite deadlocks|Bipartite deadlocks]]

* [[Deadlocks#Corral deadlocks|Corral deadlocks]]

=== Lowerbound of solution length regarding pushes ===

For solving a level all boxes have to be pushed to goals. A program can calculate the distance of every box to the nearest goal. While doing this it is presumed only one box is on the board (hence the box does not need to be pushed around other boxes). The sum of all these box distances to their goals results in a lowerbound - no matter how the boxes are pushed to their goals the level can never be solved with fewer than the calculated number of pushes. Some programs can calculate a lowerbound for the solution length (in pushes): 
number of pushes so far + sum of all box distances to their nearest goals (presuming no other boxes are on the board). 
This lowerbound can be useful in levels like the "Kobus Theron"-series.

[[#top|Top]]
</noinclude>

Feature list : General Information

2024-07-17T18:07:41Z

Matthias Meger: /* Game Types */

<noinclude>__NOTOC__{{:Feature_list}}</noinclude>


== Platforms ==



{| class="soko-table"
! colspan="6" | Platforms !! colspan="50" | <div align="right">Platforms</div>
|- {{programs}}
| {{tc}} | Java (platform independent) || {{no}} || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | Linux || {{no}} || {{no}} || {{yes}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | Mac OS X || {{no}} || {{yes}} {{tip|Sokoban++ for macOS lacks many of the features listed here, this feature list reflects the Windows version|text=partial}} || {{yes}} || {{no}} || {{no}} || {{yes}}
|-
| {{tc}} | Windows || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}}
|-
| {{tc}} | Windows Mobile || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
! colspan="6" | Program Information !! colspan="50" | <div align="right">Program Information</div>
|-
| {{tc}} | license || free software || freeware || free software || shareware || freeware || freeware
|}
[[#top|Top]]

== Limits ==



{| class="soko-table"
! colspan="6" | Limits !! colspan="50" | <div align="right">Limits</div>
|- {{programs}}
| {{tc}} | maximal map size || 50x50 || 70x70 || 200x200 || unlimited || unlimited || unlimited
|-
| {{tc}} | maximal moves || 100000 || unlimited || unlimited || unlimited || unlimited || unlimited
|-
| {{tc}} | [[Feature_list_:_General_Information#Maximal boxes limited by map size|maximal boxes]] || 1200 || unlimited || unlimited || unlimited || unlimited || unlimited
|}
[[#top|Top]]

== Game Types ==



{| class="soko-table"
! colspan="6" | Game Types !! colspan="50" | <div align="right">Game Types</div>
|- {{programs}}
| {{tc}} | sokoban || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}}
|-
| {{tc}} | sokoban + (numbered sokoban) || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | trioban || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{yes}}
|-
| {{tc}} | hexoban || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} {{tip|separate download available}} || {{yes}}
|-
| {{tc}} | octoban || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|-
| {{tc}} | multiban || {{no}} || {{no}} || {{no}} || {{no}} || {{no}} || {{no}}
|}
[[#top|Top]]

<noinclude>

==Info==
=== Maximal boxes limited by map size ===

There is no limit to the number of boxes. The limit is that imposed by the size of the map.

(The table uses the term "unlimited" here. In this context, it means the same, and it avoids burdening the reader with unnecessary details like "limited by map size".)

[[#top|Top]]
</noinclude>

Level format

2024-06-14T10:46:55Z

Matthias Meger: moved Level format to Puzzle format

#REDIRECT [[Puzzle format]]

User:Matthias Meger

2024-06-12T14:06:22Z

Matthias Meger:

Matthias Meger
Hamburg, Germany
E-Mail: JSoko@mail.de

Main Page

2024-04-23T18:24:51Z

Matthias Meger: /* Welcome to the Sokoban Wiki */ added scientific research page

=='''Welcome to the Sokoban Wiki'''==

[[Image:SokobanExample.gif|frame|right|A ''Sokoban'' puzzle being solved]]

'''Sokoban''' is a puzzle video game in which the player pushes boxes around in a warehouse, trying to get them to storage locations.

The game was designed in 1981 by Hiroyuki Imabayashi, and first published in December 1982.
The original game of SOKOBAN was written by Hiroyuki Imabayashi.

Today Sokoban is one of the most popular thought and logic games.

The name comes from Japan and means "warehouse keeper".

As simple as that name is, so is the idea of this game:

A Sokoban puzzle represents a store room, where boxes appear to be randomly placed.
You help the warehouse keeper to push the boxes around the maze of the room so that, at the end, all boxes are on marked fields.

The only restrictions are that the warehouse keeper can only push a box, never pull, and that just one box may be pushed at a time.

Each puzzle has a different structure, which requires a different solution - often with a different strategy as well.
The magic of the game is that boxes, which are out of the way on one move, might be in the way on the next move.

The simplicity of the rules, in combination with the many puzzles ranging from easy to extremely difficult, have made Sokoban become a real classic.

This Wiki is dedicated to this exciting game.

<div class="box margin-3">
<div class="title" align="center">Contents</div>

:'''Information'''
:* [[The rules of the game]]
:* [[How to play Sokoban]]
:* [[Moves vs. Pushes]]
:* [[Deadlocks]]
:* [[Scientific research]]
:* [[level format | The level format]]
:* [[general Sokoban information | General Sokoban information]]

:'''Programs'''
:* [[First_Sokoban_program | The first Sokoban program]]
:* [[Links | Sokoban Programs and links]]
:* [[feature_list | Sokoban program feature comparisons]]

:'''Solvers statistics'''
:* [[Solver Statistics | Sokoban solver statistics]]

:'''Development'''
:* [[Solver | Solver development]]
:* [[Optimizer | Optimizer development]]

</div>

== SokobanWiki Buttons ==

Add a SokobanWiki [[Buttons|Button]] to your web site.

This Sokoban Wiki was printed on 100% recycled electrons!

File:SokobanExample.gif

2024-04-23T18:18:59Z

Matthias Meger:

File:FirstSokoban.png

2024-04-17T11:49:44Z

Matthias Meger: uploaded a new version of "File:FirstSokoban.png": Screenshot: First Sokoban program

Image of the first Sokoban game

Solver

2024-04-13T12:56:58Z

Matthias Meger: /* Deadlocks */ Changed the text a bit so it's clearer that deadlocks are a good thing and can help the solver find a solution quicker

== Terms and Definitions ==

;Level
:Another term for a Sokoban puzzle.
:A level contains a board and usually additional data like title, author name and solutions.
:Sometimes it’s also called “maze”.

;Board
:The board is a 2 dimensional area containing the objects of a Sokoban level (walls, boxes, goals, player and empty squares).

;Boxes
:The objects on the board which the player can push around.

;Goals
:The target positions for the boxes.
:A level is solved when all boxes have been pushed to a goal.

;Box Configuration
:The positions of all boxes on the board form a specific ''Box Configuration''.

;Board position
:The positions of all boxes and the player position constitute a ''Board Position''.

;State
:The positions of all boxes and the player position constitute a Board Position.
:
:The term State is used when additional data are stored together with a Board Position.
:
:For instance, a solver may store: pushes needed to reach the board position or the information of which box has been pushed last.
:
:The search tree consists of states being generated during the search.
:
:States can be stored in a transposition table so duplicate game positions can be detected, for instance.
:Other terms for a state are: game position, game state and game position.

;Player reachable area
:The player reachable area consists of all squares on the board currently reachable for the player.

;Corral
:The boxes and walls on the board can split the board into several areas.
:
:An area of the board which the player cannot reach, surrounded by a barrier made of one or more boxes, and any number of walls is called “corral”.

== Data Structures ==

=== Positions on the board ===
The board is a two-dimensional area containing the objects of a Sokoban level.

Hence, a natural data structure for storing the board is a two-dimensional array.

However, many solvers use a one-dimensional data structure for this task, numbering the board positions from 0 to n-1, where 'n' is the number of board squares.

Accessing the elements of a one-dimensional vector is easier and faster for a computer program than accessing the elements of a two-dimensional array, simply because the address calculation is less complicated.

Using a one-dimensional vector has also the advantage for the programmer, that a square number can be stored in just one variable.

The board data structure can also include additional data, for instance flags for:
* Is a box frozen?
* Is the position a dead position?

=== Storing a state ===
In Sokoban a state consists (among possible additional data associated with it) of the positions of the boxes and the position of the player.

Every other element of the board cannot change its position and therefore needn’t to be stored per state.

Therefore a state can be stored by using:
* One integer array for storing all box positions.
* One integer for storing the player position.

For a better memory alignment the player position and box positions can also be stored in one integer array together.

The data structure usually consists of additional data fields like for storing information about the state like pushes needed to reach it or which box has been pushed last.

Example data structure for Java:
<pre>
public class State {
int[] boxPositions;
int playerPosition;
}
</pre>

=== Transposition Tables ===
Solvers for the Sokoban game use a graph search as the search algorithm.

The search creates a directed graph of states.

In nearly every Sokoban puzzle many states can be reached through different paths in the search graph.<br /
In these cases the graph is cyclic and the search reaches specific states multiple times during the search.<br /
The search effort can therefore be considerably reduced by eliminating duplicate states from the search.<br /
A common technique is to use a large hash table, called the transposition table, which stores all already explored states.<br /

The transposition can also be used to store additional data per state – for instance the depth the state has been reached in during an IDA*-search.

==== Tradeoff between space and time ====
The transposition table may need to hold several million states.<br /
Hence, an efficient data structure has to be chosen for storing the states.

There are different approaches to address the high memory usage problem.

===== Limit the transposition table size =====
One solution for the high memory usage of the transposition is limiting the size of the transposition table.

This makes the search algorithm a kind of hybrid between tree search and graph search. <br /
The advantage is the ability to search for solutions for larger levels due to the lower memory usage, while an obvious disadvantage is that it may lead to duplicated search effort.

===== Incremental storage of states =====
Instead of storing all box positions and the (normalized) player position for every state it’s also possible to store the data relative to another state.

This divides the states in two types:
* States that store all box positions and the player position.
* States that store a link to another state and the difference to that linked state.

Example: 
State 1:
box positions: 10, 13, 21, 33, 45, 47, 48, 49
player position: 17</pre>

Now another state consisting of these data has to be stored:
<pre>
State 2:
box positions: 11, 13, 21, 33, 45, 47, 48, 49
player position: 10</pre>

State 2 can be stored relative to state 1 this way:
<pre>
State 2:
link to: state 1
boxNo: 0
newBoxPosition: 11
Player position: 10 </pre>

=== Hash Function ===
Since the transposition table is usually implemented as hash table a hash function is needed for storing the states.

The hash function takes the position of every box and the normalized player position into account.

One efficient way to implement this is using Zobrist values (see: Albert L Zobrist. A new hashing method with application for game playing. ICCA journal, 13(2):69–73, 1970.)

== Normalizing the player position ==
Solvers not interested in finding solutions optimized for moves can consider two states equivalent if the boxes are at the same positions and the player positions are in the same player access area.

This can be implemented by storing only normalized player positions, e.g. the top-left reachable position instead of the actual position of the player.

This significantly reduces the number of states in the search tree.

== Calculation of player reachable positions ==
The reachable player positions must be calculated very often during the solver search.
Hence, an efficient algorithm is required.

=== Algorithm ===
In order to generate successor states from a specific state during the search the solver must know which side of which boxes the player can reach.

Instead of calculating a path for the player to every side of every box separately it’s quicker to calculate all player reachable positions at once.

This can be done by performing a simple Breadth First Search.

The BFS marks all reachable positions. This can be done by using a boolean array where each bit represents a specific position on the board. 
For a better performance time stamps can be used to mark the reachable positions of the player instead of boolean flags.

== Brute force ==
The first step we do is to code a routine that generates all possible pushes for a given level situation.
In our level for the first push there are four possible pushes: up, down, left and right. All of these pushes are done and the resulting states are stored in a queue.

With only one push the box can be pushed to the following positions:

[[Image:SolverLevel2.png]]

After this is done we take every of these saved states as new start state and generate all possible successor states. For example, this is one state than occurs after the first push has been made:

[[Image:SolverLevel3.png]]

We take this state and generate all successor states of it (that just means we push the box to every possible direction again). Again we save every generate state in the queue.

Described as algorithm this looks like this:

This is done again and again:
# Add the initial state (the level begin) to the queue

# Take the first state of the queue
# Generating all successor states of the state we got of the queue
# Add all states we've just generated in the queue
# continue by step 1

Finally we reach the state where the box is located on the goal.

== Pruning duplicate positions ==
The described algorithm can be improved a lot. One thing that can be improved is the following:
At any time the algorithm pushes the box on square to the right. Then it adds this state to the queue. At some time it takes this state from the queue again and generates all successor states - including the state resulting by pushing the box one square to the left.
This results in a loop: Pushing a box to the right, then back to the left, again to the right, ...
we generate duplicate positions which slows down the search a lot. So what we have to do is avoiding duplicates states.
To avoid duplicate positions we have to detect them. Therefore we have to store every state reached during the solving process.
After a new state has been generated we have to check if it has already been generated before and if so we just discard it.
This reduces the number of states to search until a solution is found a lot and therefore improves the performance of the solver.

New solver process logic:
# Take the first state of the queue
# Generating all successor states of the state we got of the queue
# Delete all successor states that have already been generated before
# Add all left states to the queue
# continue by step 1

== Deadlocks ==

Due to the constraints given by the rules of Sokoban some states in the game are deadlocked.

That means it isn’t possible to push every box to goal, anymore.

In general, deadlocks can be arbitrarily complex and potentially include all the boxes.

Hence, detecting all deadlocks is only feasible for very small levels.

However, a lot of deadlocks can be identified also in bigger levels.

Detecting deadlocks can prune huge parts of the search tree and therefore is an important part of every solver.

A balance has to be found between the time spent on deadlock detection and the time spent on the actual search.

While the detection process itself has some computational cost, the benefits of pruning large parts of the search tree usually outweigh the drawbacks.

See the [[Deadlocks]] section for an overview of some common deadlocks that may occur.

[[How to detect deadlocks]]

== Pushes Lowerbound Calculation ==

The ability to admissibly estimate the number of box pushes needed to solve a specific state is useful for the heuristic function used in a guided search - like for example the A*-search.

The more accurate the calculated lower bound is the better it can guide the search. 
However, calculating a good lower bound is a CPU intensive calculation.

A good lower bound calculation is especially important for solvers that search push optimal solutions.

The lower bound can also be used as information whether a level has been solved, since a lower bound of 0 means all boxes are on goals.

=== Performance vs. Accuracy ===
Calculating an accurate pushes lower bound is a quite expensive task. 
Hence, depending on the needed accuracy different algorithms are used.

==== Free Goals Count ====
A trivial lower bound can be calculated by counting the number of goals not occupied by a box.

This calculation is very fast but the results are quite inaccurate. 
However, this calculation can be used to identify specific level types.

Example:
If the initial state of a level has 20 boxes but only one goal not occupied by a box then this level belongs to a specific level type where most of the boxes are on goals right from the beginning. 
For such levels a lower bound calculation can often not guide the search as well as in other level types.

==== Simple Lower Bound ====
A simple lower bound calculation calculates the sum of the distances of each box to its nearest goal.

The distance from a box to its nearest goal can be calculated with various degrees of sophistication. 
The simplest method is to calculate the so-called [http://en.wikipedia.org/wiki/Taxicab_geometry Manhattan distance].

A more accurate method is to use the minimum push distance from a box to its nearest goal. 
The program can precalculate the minimum push distance to the nearest goal for all squares on the board during initialization. 
That way, it's a simple and efficient table lookup to find the distance to the nearest goal for each box during the search.

Both of these methods have the notable property that they are so-called [http://en.wikipedia.org/wiki/Admissible_heuristic admissible heuristics], i.e., they never overestimate the true shortest solution. This means the lower bound estimate can be used for solving a level with a push-optimality guarantee.

Calculating a simple lower bound is fast and accurate enough for very small levels. It does, however, grossly underestimate the true lower bound in most cases. The simple lower bound ignores that all boxes must go to different goals, and it also ignores how the boxes interact with (typically block) one another.

==== Minimum Matching Lower Bound ====
The Minimum Matching Lower Bound algorithm calculates a minimum-cost perfect matching on a bipartite graph. 
The “cost” is represented by the push distance of a specific box to a specific goal. 
Each box is assigned to a goal so that the total sum of distances is minimized.

The matching can be calculated using the Hungarian method or the Auction algorithm, for instance. 
The complexity of this calculation is about O(N3), where N is the number of boxes and therefore are quite expensive calculation.

The benefits of this expensive calculation are:
* It produces much more accurate results than the Simple Lower Bound calculation.
* It provides the parity of the any solution, i.e. if the value returned by the algorithm is even, then the number of pushes in a solution is also even.
This makes it possible to skip every other iteration in an iterative deepening search.
* It can detect deadlocks where not every box can reach an own goal anymore.

==== Greedy approach ====
Calculating a minimum-cost perfect matching on a bipartite graph as described above is an expensive computation.

A greedy approach can be used to approximate a minimal perfect matching: 
the push distances of all boxes to every goal are calculated and stored in a list sorted ascending by distance.

Example:
: box1 to goal 1: distance = 3
: box 2 to goal 1: distance = 4
: box1 to goal 2: distance = 10
: box 2 to goal 2: distance = 12

There is also a list of all already matched boxes and goals. 
We then iterate over this list of distances. 
If the box and the goal both aren’t matched, yet, we match them. 
In the example, we would match box 1 to goal 1. 

Then the second list entry is reached: 
“box 2 to goal 1: distance = 4“ 
Since goal1 is already matched with box 1 the box can’t be matched and we discard this entry.

However, it is possible that not every box is assigned a goal after the list has been completely iterated over – although a valid matching for all boxes may be possible. 
In that case all not yet matched boxes are simply assigned to its closest goal.

This approach isn’t as expensive to calculate as a minimum-cost perfect matching with the disadvantage of being less accurate.

=== Algorithm Optimization ===
The algorithm used to calculate the pushes lower bound can be optimized using specific optimization ideas:

* If the lower bound of a state is L1 and a push is made the new lower bound L2 has to be calculated. When the algorithm finds a matching that reduces this lower bound L1 by the cost of the push, it’s clear that the lower bound can’t be reduced further. Hence, the algorithm can stop immediately in these cases.

* During the search the algorithm only needs to update the previous found matching, because each push results in only one box changing its distances to the goals.

* Only perfect matchings are relevant. Hence, as soon as it is clear that a perfect matching isn’t possible the algorithm needn’t to search for the minimum matching anymore.

=== Calculating the Box Distances ===
For calculating the pushes lower bound the algorithm needs the distances for all boxes to all goals.

Calculating these distances can be done in different ways.

Since the wall positions and goal positions never change, the distances for a specific box depend on:
* the player position
* the positions of the other boxes

Calculating the real distances for all boxes regarding all other box positions is too difficult and time consuming. In fact this can be as difficult as the task to solve the whole level.

Hence, the common practice is to just consider the distance of a box to a goal under the assumption that no other box is on the board. 
This also has the advantage that the distances can be computed and cached before the solver starts since they never change while the solver is running.

==== Position of the Player ====
For a more accurate calculation of the distance of the box to the goals the player position can be taken into account. 

Example 1: 
[[Image:PositionOfThePlayer.png]]

The needed pushes to push the box to the goal having the player on the right of the box is 6 pushes. 
However, the needed pushes to push the box to the goal having the player on the left of the box is only 2 pushes. 

Hence, it's necessary to calculate the distance of the box to the goals for every possible player access area. 
In this example there are two possible player access areas: one having the player left from the box and one having the player right from the box.

The player position has also to be taken into account of for calculating the real distance of the box to the goals.

Example 2: 
[[Image:BoxDistanceExample.png]]

There is only one player access area in this example. 
However, the box distance to the goal is not 2 pushes but 8 pushes.

Both examples have something in common: 
There is a so called ''Gate Square''.
;Gate Square
: A ''Gate Square'' divides the board into at least two different player access areas.

If the goal distances of a box on a ''Gate Square'' has to be calculated the player position has to be taken into account (like in Example 1). 

''Gate Square''s in general have to be taken account of when calculating the box distances, like shown in Example 2.

This is example 2 with the ''Gate Squares'' highlighted: 
[[Image:LevelWithGateSquaresHighlighted.png]]

=== Linear Conflicts ===
The restriction of only considering one single box for calculating the box distances has the obvious disadvantage of not taking into account other boxes that may block the box or the player.

It's however possible to detect some of the box configurations that inevitably increase the calculated pushes lower bound.

Example: 
[[Image:PenaltSquares.png]]

In this example the calculated pushes lower bound is 8 pushes when using the ''Minimum Matching Lower Bound'' calculation.

However, the real number of needed pushes to push both boxes to a goal is 10 pushes. 
The reason for this is both boxes block each other in a way that both boxes can only be pushed vertically. Since all possible vertical pushes will push a box further away from a goal the needed pushes for solving the level increases. 
In such situations the calculated pushes lower bound can be increased by 2.

==== Pitfalls ====

Example 1: 
[[Image:PenaltyPitfall1.png]]

This example shows three boxes that all can only be pushed vertically. 
However, this doesn't mean that we can add a penalty higher that 2 to the calculated pushes lower bound.

Since pushing the middle box down (or up) makes it possible to push the other two boxes push optimal to the goals only a penalty value of 2 may be added to the calculated pushes lower bound.

Note: if there were a wall above or below the middle box it would be valid to add a penalty value of 4!

Example 2: 
[[Image:PenaltyPitfall2.png]]

This example is the same as Example 1 but with one goal at a different position. 
Since now a vertical push of the middle box is on the push optimal path to a goal it's not valid to add any penalty value to the pushes lower bound!

==== Complex linear conflicts ====
Sophisticated conflict detection algoritms may also detect linear conflicts involving more than two boxes and more complex linear conflics like in this example: 
[[Image:ComplexLinearConflict.png]]

==== Frozen Boxes ====
The distanes used for the lower bound calculation are usually precomputed before the solver search starts. 

They represent the number of box pushes required to push a box from any square on the board to any other square. 
These distances are optimistic distances in that they assume no interference with other boxes. 
The only restrictions are the walls on the board.

However, boxes on a goal which can't be pushed anymore (-> frozen box) can be treated as walls. They therefore potentially change the distances.

Example: 
[[Image:LowerBoundWithFrozenBox.png]]

In this example the pushes lower bound is 3 pushes. 
However, when the left box is pushed two squares to the right to its goal the right box can't be pushed up immediately anymore: 
[[Image:LowerBoundWithFrozenBox2.png]]

In such situations the box distances have to be recalculated while treating the box on the goal as a wall. 
By doing so the correct pushes lower bound can be calculated.

==== Pattern databases ====
Some solver programs use pattern databases where precalculated box configurations are stored together with a penalty value.

This way it's possible to detect even complex penalty situations and add high penalty values.

== No influence pushes ==

=== Tunnels ===
Having teached the solver to use the algorithms described above our little level is solved very quickly. Usually Sokoban levels are a lot more complicated. Therefore we have to search for further ideas how to reduce the number of states we have to generate during the solving process.

New example level:

[[Image:TunnelExample1.png]]

Here we have a (still very easy) level containing two boxes. The solver takes the given state as initial state. Then it generates all possible successor states. This means: Pushing box 1 to every possible direction AND pushing box 2 to every possible direction. The solver doesn't know which push is the best for solving the level - hence it has to generate all possible successor states. This soon leads to an enormous number of generated states (at least in larger Sokoban levels). It would be a great advantage if we knew that only pushes of one box are relevant in a specific state.

Let's assume the player has just pushed the box next to him one square to the right.
What to do next?

The solver will consider every possible next push: all possible pushes of the higher box and all possible pushes of the lower box. But: The higher box is in a tunnel - the just performed push has been a "no influence push".
The reason is:
The squares the lower box can ever be pushed to stayed the same. There aren't any additional squares the lower box can reach, nor are there any squares the lower box can't reach due to the push of the higher box.
The just pushed box has definitely to be pushed sooner or later. So there is no reason why not to push it further to the right immediately!

In general such a "no influence push" is always created when the situation AFTER the push looks like this (or any flipped / mirrored version of it):

[[Image:TunnelExample2.png]] or [[Image:TunnelExample3.png]]

Every time a push of a box results in such a situation the box can immediately be pushed one square further!
This rule can reduce the number of states to be generated in some levels a lot.

=== PI-Corrals ===

This section describes an admissible domain-dependent move pruning technique for the Sokoban game called PI-Corral pruning.

PI-Corral pruning has highly attractive properties for a Sokoban solver program:
* It prunes a significant number of states from the search
* It steers the search towards positions with a certain class of deadlocks, thereby helping to detect these deadlocks early on, increasing the pruning even further
* It preservers push-optimality guarantees provided by the solver

PI-Corral pruning leverages the same idea that is also used for pruning due to tunnels:
It identifies pushes that don’t influence certain parts of the board and then ignores all boxes that aren’t influenced by the performed push.

A simple example of a PI-Corral: 
[[Image:ICorralExample1.png]]

In this level the player just has pushed the box to the left.

Normally the solver now generates all possible pushes for all boxes including the box in the lower right corner. The push creates an area the player can't reach marked with a [[Image:BlueQuadrat.png]].

The boxes that are part of this area can only be pushed inside this corral (= on squares that are marked) with the next push. Hence, these pushes don’t have any impact on the rest of the level. The reachable player positions aren’t reduced and also the reachable positions of the box in the lower right part of the board aren’t reduced.

At least one of boxes at the border of the marked area must be pushed into that area sooner or later.
This is always necessary when a box at the border or inside the area isn't located at a goal square, or when a goal square inside the area isn't filled with a box.
In the current position, the player can make all the possible pushes which ever can be made into the marked area. Therefore, the solver just needs to generate the pushes for the boxes at the border of the marked area. The legal pushes for all other boxes on the board can be ignored.

This can reduce the pushes to be generated a lot - particularly when there are a lot of boxes in the level that aren't involved in the PI-Corral.

The key insight with PI-corrals is the fact that as the boxes on its barrier can only be pushed inwards, one of them will indeed have to be pushed there before any of the boxes in the corral can be pushed elsewhere.
So, if the corral has to be dealt with eventually, it is best to deal with it right away and all pushes of other boxes can be discarded. 

The reason that this works, and that it only applies to PI-corrals and not other corral types is due to box influence. 
In a PI-corral no other box can be influenced by the fact that a box is pushed into the corral, because any boxes outside the PI-corral are by definition either accessible or inaccessible regardless of whether the player can walk in the area of the corral, while boxes completely inside the corral (not on the boundary) are by definition inaccessible to the player and could not be pushed before the corral is dealt with. 
In other words: all the pushes of boxes not part of the PI-Corral are still possible after a box is pushed into the PI-Corral.

==== Terms and Definitions ====

;Corral
:The boxes and walls on the board can split the board into several areas.
:An area of the board which the player cannot reach, surrounded by a barrier made of one or more boxes, and any number of walls is called “corral”.
:The corral includes all the boxes on the barrier between the inside and the outside of the corral, and all interior boxes, if any.
:
:An example corral:
:[[Image:CorralExample.png]]
:Positions part of the corral are marked with [[Image:BlueQuadrat.png]].

;I-Corral
:A corral where all boxes on the barrier can only be pushed inwards (into the corral) by the first push.
:The "I" in "I-corral" is a reference to "inside" or "inward".
:
:An example corral:
:[[Image:I-CorralExample.png]]
:Positions part of the I-corral are marked with [[Image:BlueQuadrat.png]].
:Note how in this I-Corral example (in contrast to the Corral example) it's not possible to push any box to a position not part of the corral.

;PI-Corral
:An I-Corral where the player can perform all legal first pushes into the corral, 
:meaning the player can reach all the relevant boxes from all relevant directions.
:The "P" in "PI-Corral" is a reference to "player" or "pusher".
:A "PI-Corral" is the important sub-class of the I-Corrals where the player can reach all the boxes on the barrier of the corral and perform all their legal inwards pushes.
:An example PI-Corral:
:[[Image:PI-CorralExample.png]]
:The boxes on the barrier of the PI-Corral are highlighted in red.
: 
:Counter-example: an I-Corral which isn't a PI-Corral because of the outside blocking box:
:[[Image:PI-CorralCounterExample.png]]
:This example isn't a PI-Corral because the player cannot push the highlighed box inwards; 
:there is an outside box that blocks the access. 
:Note that if that outer box was a wall then the level is a PI-Corral:
:[[Image:PI-CorralExample2.png]]
:The rule is: the player must be able to perform all legal inwards pushes of the PI-Corral boxes on the barrier.
:This can be checked: remove all boxes which aren’t part of the PI-Corral, then compare the possible pushes.

==== PI-Corral Pruning ====

The PI-Corral property in itself is not enough to permit pruning states from the search. 
There is the additional constraint that sooner or later, at least one of the boxes on the barrier must be pushed into the corral in order to solve the puzzle. 
There are different reasons why such a push may be necessary, so this constraint can be implemented with various degrees of sophistication.

The constraint "Pruning is only permitted if at least one box in the PI-Corral is not on a goal square, or if at least one goal square in the PI-Corral does not contain a box" can be implemented by simple inspection of the board position.

A more sophisticated solver may form plans which permit pruning for more involved reasons, e.g., "The player must pass though the corral", or "A box from the outside must be parked inside the corral".

If there is a PI-Corral and one of the involved boxes has to be pushed in any way to solve the level then PI-Corral pruning can be applied.
That means in such a situation the solver only has to generate pushes for boxes part of the PI-Corral but not for boxes outside the PI-Corral.

The key-insight is this: pushing a box inwards, into the PI-Corral, never affects the player's access to boxes outside the PI-Corral. Therefore, when we choose which box to push next, we might as well push one of the PI-Corral-boxes because we have to do that sooner or later anyway.

In the next push, we still have full access to all boxes outside the corral so we can pick one of them, if we wish to. However, if there still is a PI-corral on the board, we continue only checking if PI-Corral pruning can be used and if yes, we again only consider the PI-Corral-boxes for generating new board positions.

So the bottom line is that for each position we meet during the solving process, we first check for PI-corral pruning, and if it can be applied, we never generate pushes for boxes outside the PI-corral.

A very simple example of a PI-Corral is a tunnel: 
[[Image:PI-CorralTunnel.png]]

In this simple PI-Corral all conditions are fulfilled:
# there is a corral
# all possible pushes of the boxes on the corral barrier are pushes into the corral
# at least one of the boxes in the corral has to be pushed to solve the level
# the player can perform already now all theoretically possible legal pushes (not generating a deadlock) into the corral

Hence PI-Corral pruning can be applied and only pushes of the marked box must be considered for the next push.

In this simple example the key idea behind PI-Corral pruning becomes clear: 
There may be some complicated push sequences needed to push the boxes outside the PI-Corral to goals. However, no matter how complex these push sequences may be: all of these pushes are still possible after the box has been pushed into the PI-Corral. 
The push of the box into the PI-Corral has no "influence" on the rest of the level.

==== Multi Room PI-Corral ====
It's rather seldom that a board position contains simple PI-Corrals like the one depicted above. 
Even when there is an I-Corral, the player seldom has access to all the boxes (from all the required directions). 
Often, the player's access to the I-Corral boxes is blocked by neighboring corrals like in this (small) example: 
[[Image:MultiRoomPICorralExample1.png]]

Neither does the top-left corral (red border) nor the neighboring corral (blue border) fulfill all PI-Corral constraints. 
In both cases there is a box which can't be pushed into the corral at the moment (the box having a red and a blue border).

However, both corrals can be combined to a multi room corral. 
The combined corral then fulfills all PI-Corral constraints: 
[[Image:MultiRoomPICorralExample2.png]]

In order to find these Multi Room PI-Corrals the algorithm combines corral after corral until a (multi room) PI-Corral has been found. 
This way the algorithm also ensures that there are as few boxes in the found PI-Corral as possible.

Example: 
[[Image:MultiRoomPICorralExample3.png]]

The marked area is a (combined) PI-Corral, since the boxes can only be pushed into the corral and all of the legal pushes are currently possible.

However, when the algorithm starts with the top-left I-Corral, this corral is classified being a PI-Corral without the need to combine it with another corral: 
[[Image:MultiRoomPICorralExample4.png]]

This means instead of two boxes there is only one single box to consider for the next push.

Note: 
After having pushed the PI-Corral box one square into the PI-Corral there are two PI-Corrals now: 
[[Image:twoPICorralsExample.png]]

In such a situation the solver can choose which PI-Corral to consider first. 

This is another example showing the importance of the algorithm only combining corrals if necessary: 
[[Image:SinglePICorralExample.png]]

This example also shows that a deadlock detection can help identifying PI-Corrals. 
The marked PI-Corral has two boxes. 
However, only one of the boxes can currently be pushed into the PI-Corral. 
Nevertheless it's a PI-Corral because pushing the lower left box of the PI-Corral into the PI-Corral creates a deadlock and therefore this isn't a legal/valid push.

==== Deadlock Situations ====
PI-Corral pruning can help detecting deadlocks earlier as a side-effect of successor-pruning.

If there is a (smallish) deadlock situation on the board consisting of a PI-Corral, then pruning leads to a position where the legal moves dry out, in effect finding a deadlock like in this (very small) example: 
[[Image:DeadlocksAndPICorrals.png]]

The solver only considers these boxes for the next push. Since no further legal push is possible (assumed that “freeze deadlocks" can be detected by the solver) a deadlock is detected.

==== Statistics ====
In his [[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver|solver scribbles]] Brian Damgaard wrote:

There is always an overlap when different pruning techniques are used in a solver, but conservatively speaking, this new technique [PI-Corral pruning] is itself able to prune at least 20% of the search tree according to my experiments, and empirically the savings always outweighs the extra costs.

My program uses precalculated deadlocks to handle simple deadlocks like this one, but the corral-pruning is a valuable contribution to the program, and experiments shows that the corral-pruning almost can hold its candle to the precalculated deadlocks, if it is asked to do so:

Statistics - SokEvo/107 - Forwards search - no packingorder - AMD 2600+
Configuration A: A* search + transposition table
Configuration B: A* search + transposition table + corrals
Configuration C: A* search + transposition table + precalculated deadlocks
Configuration D: A* search + transposition table + precalculated deadlocks + corrals

"B" is the experiment with corrals only, without precalculated deadlocks, and its 21 seconds (on my amd 2600+ pc) is in the same league as the "C" experiment with precalculated deadlocks but no corral-pruning.
"D" with all currently implemented pruning techniques reduces the total solving time to 7 seconds, showing that the different pruning techniques work well together.

{| class="soko-table"
|-


! colspan="4" | Solver Statistics
|- bgcolor="#f1efe5" align="center"
| | Configuration
| | Generated states
| | Pushes
| | Time


|- align="right"
| align="left" bgcolor="#f1efe5" | A
| | 11974023
| 51938064
| 65 seconds


|- align="right"
| align="left" bgcolor="#f1efe5" | B
| | 4632203
| 11918161
| 21 seconds


|- align="right"
| align="left" bgcolor="#f1efe5" | C
| | 2030736
| 7011203
| 11 seconds


|- align="right"
| align="left" bgcolor="#f1efe5" | D
| | 1231376
| 3299797
| 7 seconds

|}

==== Temporary Auxiliary Pushes ====
Usually there are a lot of I-Corrals for which the player can’t perform all inwards pushes at the moment.

Example: 
[[Image:temporaryAuxiliaryPushes.png]]

One box is blocking the player from pushing one of the boxes into the I-Corral.

An obvious aim now is to push this blocking box away to create a PI-Corral. 
This destroys push optimally guarantees but results in more detected PI-Corrals and therefore in a smaller search tree for the solver.

One way to check whether the box can be pushed away is to check whether the box can be pushed away and then immediately back to where it is now. If this is possible, we can perform all pushes into the I-Corral and after that is done the blocking box is always back where it is now.

Currently this is not implemented in any solver.

A subclass of those “I-Corrals with access blocking boxes” could be used for pruning with some further investigations.

Example: 
[[Image:temporaryAuxiliaryPushes2.png]]

The marked box of the I-Corral can’t be reached by the player. 
However, through further calculations the program could prove that the I-Corral can never be opened by pushing this box. 
Pushing the box into the corral does never allow the player to push any other corral boxes. 
Hence, in these seldom situations even pruning on I-Corrals may be applied. 
This also preserves push optimality.

==== "Real world" PI-Corral Examples ====

The program [http://www.sokoban-online.de JSoko]. offers a debug mode for testing PI-Corral pruning. 
The shown example PI-Corrals are taken from JSoko version 1.81 having that debug setting activated.

To let JSoko highlight the found PI-Corrals:
# Start JSoko
# Type the letters “debug” when JSoko has the keyboard focus. This shows a new menu called “debug”
# In the debug menu select “Show I-Corral during solving"

Note: although the menu text is ''"Show '''I-Corral'''"'' JSoko will show '''PI-Corrals''' and only those for which PI-Corral pruning can be applied.

Note 2: PI-Corrals that include all boxes on the board aren’t shown by JSoko since there is no benefit in applying pruning when all boxes are part of the PI-Corral.

When the PI-Corral debug settings is activated JSoko will check for PI-Corrals and highlight them after every push that is made.

Thinking Rabbit - Original Level 1: 
[[Image:OriginalLevel1PICorral.png]]

Due to PI-Corral pruning the solver has only to consider the PI-Corral boxes for the next push, only one of which is currently reachable for the player. 
This example shows that a deadlock detection can help detecting PI-Corrals.

The lower left box of the PI-Corral isn't reachable by the player at the moment. 
However, both pushes of that box would result in a [[Deadlocks#Freeze deadlocks|freeze deadlock]]. 
Hence, no legal push is possible for this box.

Thinking Rabbit - Original Level 3: 
[[Image:OriginalLevel3PICorral.png]]

In the shown situation the solver has choose which PI-Corral to consider first.

Thinking Rabbit - Original Level 4: 
[[Image:OriginalLevel4PICorral.png]]

There is a huge multi room PI-Corral containing nearly all of the boxes. 
Nevertheless, PI-Corral pruning can also help pruning some states for the solver in such situations where only one box is outside the PI-Corral.

Thinking Rabbit - Original Level 6: 
[[Image:OriginalLevel6PICorral.png]]

This is an example where a sophisticated deadlock detection can help to detect more PI-Corrals.

Thinking Rabbit - Original Level 10: 
[[Image:OriginalLevel10PICorral.png]]

This example shows that JSoko detects some PI-Corrals where pruning is possible but not that useful. 
Since there is only possible push there is nothing to be pruned.

Thinking Rabbit - Original Level 15: 
[[Image:OriginalLevel15PICorral.png]]

The player is surrounded by a huge multi room PI-Corral. 
Every push of one of the PI-Corral boxes results in a further PI-Corral that can be used for pruning.

Figure 3 level of an article about PI-Corral pruning: 
[[Image:DDMPFigure3Level.png]]

There is an article about PI-Corrals written by Renato R. Leme, André G. Pereira, Marcus Ritt and Luciana S. Buriol where the authors claim that JSoko and YASS can't detect the correct PI-Corral in the shown level.

However, the screenshot shows that JSoko can correctly identify all the boxes and positions that are part of the PI-Corral (and so does YASS)! 
Note: an additional box has been added to this example level (the box on the goal below the player) because JSoko only highlights PI-Corrals that don't contain all boxes. However, this extra box doesn't affect the PI-Corral detection used in JSoko (and YASS).

== Parking ==
Many levels cannot be solved by just pushing one box at a time to the goal position.

Most levels are constructed in such a way that some of the boxes have to be specifically rearranged to make room for pushing other boxes.

In some cases boxes have to be actually pushed over a goal position to a “parking” position, from where they can then later be pushed to their final goal position.

Example: 
[[Image:parking example.png]]

== YASS Solver ==

[[Sokoban solver "scribbles" by Brian Damgaard about the YASS solver]]

== Sokolution Solver ==

[[Sokoban solver "scribbles" by Florent Diedler about the Sokolution solver]]

== Solver "Rolling Stone" ==

[[Rolling Stone solver]]

== Limited search ==

Ideas by David Holland on computer solving by limited search are linked below. They aren't fully wikified yet as author has RSI. Features new concepts such as free space, shuffling, relocation and generalized deadlock detection. Sketches of algorithms included. Other new concepts such as goal traps with algorithms may be implemented in existing solvers. Author hopes other programmers will discuss and implement what they find relevant. Limited search as opposed to exhaustive search uses macros, heuristics and domain-specific knowledge to effectively search deeper in the tree of positions by not looking at every position. A new category of "Planner" plug-in is suggested for limited search to be tried when the Solver plug-in fails, indicating too large a tree.
[[David Holland's computer Sokoban solving ideas]]

== See also ==

* A Spanish explanation of the [[MSAMA Sokoban Solver]].
* [[Heiner's solver]]
* [[Solving Sokoban Optimally with Domain-Dependent Move Pruning - Stolen Ideas, Lies, and Incompetence]]

Rolling Stone solver

2024-03-21T15:16:17Z

Matthias Meger: /* Main menu */ Description how to start the solver

The Rolling Stone Sokoban solver is a significant milestone in the field of automated Sokoban puzzle solving. Developed at the University of Alberta by Andreas Junghanns and Jonathan Schaeffer, it laid the groundwork for many modern solvers.

Here's a breakdown of Rolling Stone's key aspects:

= Algorithm =

Rolling Stone utilizes the Iterative Deepening A* (IDA*) algorithm as its core search strategy.

IDA* is an iterative deepening search algorithm that combines the efficiency of depth-first search with the optimality guarantees of A* search.

It starts by searching for a solution with a limited depth and gradually increases the depth limit until a solution is found or it's proven that no solution exists within that depth.

To improve search efficiency, Rolling Stone incorporates several enhancements described in various [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= papers].

Rolling Stone's approach paved the way for further advancements in Sokoban solver design. Many modern solvers build upon its core principles.

It demonstrated the effectiveness of combining general search algorithms with domain-specific enhancements for efficiently solving Sokoban puzzles.

Further information can be found in the [https://scholar.google.com/scholar?hl=de&as_sdt=0%2C5&q=rolling+stone+sokoban&btnG= papers] or on the [https://webdocs.cs.ualberta.ca/~games/Sokoban/ website of Rolling Stone].

= How to compile Rolling Stone =

Carlos Montiers has published a source code that has been adapted so that it can also be compiled with modern operating systems and compilers. In this way, Rolling Stone can still be used today.

This is the link to his repository: [https://github.com/carlos-montiers/rolling-stone Carlos Montiers Rolling Stone]

= Screenshot Rolling Stone =

Rolling Stone can only be used from the console.

This is an example output of the solver when solving puzzle "XSokoban 1"

[[File:Rolling Stone XSokoban1.png]]

= Menu structure =

== Main menu ==

{| class="soko-table"
!Command || Function
|-
|S nam\num kind || Solve Maze
|-
|A || Set Abort Node Count
|-
|T sec [REAL\VIRT] || Set Abort time
|-
|C a b kind || Test a to b in screen
|-
|P nam\num kind || Print Maze
|-
|L a b kind || All 90 Lower Bounds
|-
|N num || Set PosNr with num
|-
|M num-num\XX-YY || move from num to num
|-
|X [lrud]* || move center for xdist
|-
|Z || Show Menu
|-
|O || Options Menu
|-
|Q || Quit Program
|-
|}

The command "'''S 1'''" loads the puzzle "./screens/screen.1" and tries to solve it.

The command "'''S 1 test'''" loads the puzzle "./screens/test.1" and tries to solve it.

The command "'''S test.sok'''" loads the puzzle "./test.sok" and tries to solve it.

== Show menu ==

{| class="soko-table"
!Command || Function
|-
|D || Hist of man-distances
|-
|S || Hist of stone-distances
|-
|X || Hist of X-distances
|-
|C || Print Conflicts prev search
|}

== Options menu ==

{| class="soko-table"
!Command || Function
|-
|E || Examine all settings
|-
|H [on/off] || HashTable on/off
|-
|D [on/off] || deadlock det. movegen on/off
|-
|Z [on/off] || deadlock2 det. movegen on/off
|-
|R [on/off] || areasearch on/off
|-
|S [on/off] || deadsearch on/off
|-
|N [on/off] || pensearch on/off
|-
|W [on/off] || scan search on/off
|-
|J number || node limit for pattern searches
|-
|K [on/off] || minimization on/off
|-
|Y [on/off] || limit patterns on/off
|-
|m [on/off] || lazy maximization on/off
|-
|X [on/off] || store tested on/off
|-
|P number || Switch Pattern DBs on/off (0-7)
|-
|M [on/off] || LB manpos on/off
|-
|C [on/off] || LB conflict on/off
|-
|d [on/off] || Dynamic distances on/off
|-
|T [on/off] || Tunnel Macro on/of
|-
|G [on/off] || Goal Macro on/off
|-
|U [on/off] || Cut Goal Macro on/off
|-
|A [on/off || eXtended Distance on/off
|-
|L k m d || Local Cut (k,m,d), -1 -1 turns off
|-
|B [on/off || Auto Set Local Cut Parameter
|-
|V [s] [h] || Overestimation scaling factor and h-scaling
|-
|F [on/off] || Assume dead on/off
|-
|O number || Set Move order index (0-off)
|}

== General command ==

{| class="soko-table"
!Command || Function
|-
|? || Help command. Displays availible menu options
|-
|< || Back (quit)
|}

File:Rolling Stone XSokoban1.png

2024-03-21T10:21:23Z

Matthias Meger:

File:Sokoban Puzzle solving.gif

2024-03-07T13:42:02Z

Matthias Meger: Example: Solving a Sokoban puzzle

Example: Solving a Sokoban puzzle