Erim SEVER From Turkey - Sokoban Web Pages

SOKOBAN LEVEL SOLVER PROGRAMS :

Some of descriptions are taken from Faris Serdar TASEL's SPS Solver Program "info" web page.

These programs automatically solve level maps. Some properties make finding solution extremely hard. Some of these properties are;
1 ) Algorithm that finds solution is unknown. (like "Chess")
2 ) Order of pushing blocks and its direction are unknown.
3 ) In how many depth that there is a solution, is unknown.

Computer calculates much more moves to in this method to reach 70th depth. There is an example for understanding that clearly :
1st move : There is 4 unrepeated moves
2nd move : There is 3 unrepeated moves for each 4 moves in 1st move. (4x3 = 12 unrepeated)
3rd move : There is 3 unrepeated moves for each 12 moves in 2nd move. (12x3 = 36 unrepeated)
4th move : There is 3 unrepeated moves for each 36 moves in 3rd move. (36x3 = 108 unrepeated)
. . .
69th move : There is 2 unrepeated moves for each move in 68th move, that is 4 million total.
70th move : There is 2 unrepeated moves for each 4 million move in 69th move, that is 8 million total.

Now the number of the all moves is : 4 +12 + 36 + 108 + ... + 4 million + 8 million

It is possible to calculate all of the moves but it will take MUCH time.
Algorithms contain lots of big loops and arithmetic operations and take time due to number of blocks and wideness of movable area.

Example at SPS : After elimination of the moves, a simple maze that requires 1.39 x 10⁴² moves, will only require a few thousand moves. (that takes just 3 secs or so)
Because of these bad conditions, Solver Program Authors follow different ways for less calculates. Because of this for any level's solution time is different results for different solver programs.

For explain "the number of permutations" with level's solution search tree pictures from Lee J. Haywood 's Sokoban Evolution's SokHard ink blots web page :
The starting position is at the bottom, the final moves are at the top.
Vertical positions represent the number of box pushes made.
The width represents the number of permutations found in the search tree.
A solution would be represented as a line running from bottom to top.
The number of permutations indicated here is not representative in each case.
The complexity of the patterns is unlikely to reflect actual difficulty.
The computer actually started with the solution and pulled the boxes back, which results in fewer permutations.
Not to scale.

These examples from Lee J. Haywood 's SokHard (for only 4 levels). If you want to download the complete set of 1024 × 768 blot images - SokHard_blots.zip (1.9 MB).

Pictures & diagrams from Problemdomänen Lloyd’s Puzzle und Sokoban R. Hofstetter, M. Zesiger - FH Bern - 07.01.03 (a German language pdf file)
If you "Save" the pictures maybe you will see them in a larger sizes, but perhaps best is download this "Pdf file".
I didn't explain these, because of 1 ) I think all are not complicated, 2 ) I don't know German and I can't explain same "Source Sentences".

This picture is from SVB Sokoban Web page. Explains are in Russian language. Translated Web Page
And you can also find Solver - Generator - TxCalc programs.

Sven Egevad share From Ming. part at his Sokoban web page. And this page compare 3 solver program's (BoxSearch v5.1 beta / Takaken v7.0 / YASS v2.66) solving styles and time limits. I think a very good work about understanding solver programs and of course he spend lots of times for those tables.
"Though some people might be interested in how long it takes to solve a given level and/or how good the solution is (optimal or not), this summary disregards all timing associated with solving the levels and solution statistics. These tests are mainly for gauging solvability, not timing nor how good the solution is."

Summary some of articles :
All solvers failed levels
"BoxSearch" failed levels where at least one solver solved
"Takaken" failed levels where at least one solver solved
"YASS" failed levels where at least one solver solved
"BoxSearch" solved levels where all other solvers failed
"Takaken" solved levels where all other solvers failed
"YASS" solved levels where all other solvers failed
"BoxSearch" failed levels where all other solvers solved
"Takaken" failed levels where all other solvers solved
"YASS" failed levels where all other solvers solved
And finally he count solver program's % of success on his 1623 levels.

For lots of Solver Program you can copy and paste any level's XSB characters into solver program's text input side or you must introduce any level to solver program at program's own description.
Especially for "dos solver programs" please read their own help files. (lots of them accept "drag and drop" XSB file perhaps for default settings)

Tip : Some of Solver Programs can be easily use for "level editor" also.

SOLVER 1 - Box Search v 5.0 and Box Search v pre-alpha2 is in test now
Download - Download from Here v.5 (program needs from here MFC7.1 library, extract it to the same folder of the program)
Special thanks to Author : Ge YONG - Mail 2
I can't find box limit
The main algorithm is used to solve sokoban game "quickly", the answer is not best-push or best-move.
There are other algorithm in program tool to get best-push or best-move, but they are much slower.
The 3.1 version solver appeared in menu is reserved only for test.
Tip from Sokofan Author Eric Leung : Optimize, re-optimize again and again to get better and better solutions.
My not answered levels :
100 more than 6.153.958 states examined - 156 more than 4.627.962 states examined - 165 more than 6.139.000 states examined
171 more than 4.907.212 states examined - 176 more than 1.151.998 states examined - 177 - 179 - 181 - 182new

SOLVER 2 - Sokoban Automatic Solver v 7.2.2 January 2008/01
Download Web Page English
Special thanks to Author : Ken'ichiro TAKAHASHI (Takaken)
Program version 7.0.0 January 2003 is limited to 64 boxes.
Lots of Solvers based on his Java Applet Code of the Japanese Takaken.
OLD PAGE (Ver2.7 for JAVA) is Here
And one mail is explain this solver's settings (Mails from yahoo Sokoban mail group at August 29, 2008 :
Question : I tried Takaken 7.22 on the first level. The only answer I got was "Failed in 1 or 2 seconds". How do you manage to get a solution?
Answer: This happened to me since I have 4 Gbytes RAM. Just reduce the usable RAM in the solver by setting, not automatic. Depending on your OS, the working limit is between 1.0 and 1.8 Gbyte. Try what is adequate for you.
Solved Question : I just replaced my computer with 0.5Gbytes by a computer with 4 Gbytes. I tried 1000 Mbytes and it worked, then 2000 Mbytes and it didn't. I tried then 1500 Mbytes and it didn't. And so on. Eventually, 1266 Mbytes was the highest value accepted by the program. I have sent a mail to Takaken to inform him of the problem.
Paul Voyer's mail about "the memory management bug in Takaken's solver 7.2.2." :
I confirm a need for manual setting of the memory. But I found different working limits :
On a 32 bit XP, I can reach 1160 Mb
On a 64 bit Win7, 6Gb machine, I can reach 2050 Mb

My failed levels for version 7.0.0 2003 :
5 - 8 - 24 too big map - 100 - 122 - 139 - 142 - 156 - 161 - 165 - 171 - 175 the "limit" of program - 176 - 177 - 179 - 181 - 182new

SOLVER 3 - SPS v 3.72 04/2005
Download Web Page
Special thanks to Author : Faris Serdar TASEL
I can't find box limit.
Choosing the best mode.
SPS v 3.7.2 04/2005 (and upper versions) support "Start With End Position" levels :)) T-H-A-N-K-S !
Still the one and only Sokomind Plus Level Solver Program.
Sokomind+ xsb file support. (Recognizing 'goalorder' and 'boxorder' tags.)
Search solution @ SSDB feature.
Author's notes : The Sokoban Level Map & Solutions DB (SSDB) at author's web page , has been started to be tested. To send your solutions, you'll need to register(quick and easy). That web page runs with your help, and sokoban lovers will make SSDB be a helpful service.
My not answered levels :
100 HD used 571 MB - 156 HD used 506 MB - 165 HD used 470 MB - 171 HD used 435 MB - 176 HD used 513 MB - 177 HD used 458 MB - 179 - 181 - 182new

SOLVER 4 - R-BOX r1
Download from Here
Special thanks to Author : Andreas STABEL
A Dos program with help document.
The problem will be solved with a minimum of ball pushes or with a minimum of moves or creating your own maps. (with program options)

SOLVER 5 - SOLVEUR 56 & SOLVEUR 224
Download Solveur 56 - Download from Here
Online Java applets Sokoban Solvers for 56 & 224 Mbytes RAM.
Online Solveur56 or Online Solveur224 256Mb RAM required - JVM params "-J-Xmx224m"
Special thanks to Author : Paul VOYER
Published by Paul VOYER , based on the algorithm of the Japanese Takaken.
Solveur56 is limited to 11 boxes(can handle levels with a maximal size of 18x14), download includes Sources. (per default just get's 64 MB)
Solveur224 is limited to 15 boxes, download includes Sources.
In their complete form there is no need for translation as they use the locale configuration of the computer.
(files SolverResource_xx.properties) default is english. xx=de(utsch), fr(ench), es(pañol) -
All java applets (soko56, soko224 and hexoban) once loaded don't need to remain on line.
Each line should be xxxx=yyyy ; the left reference (xxxx) should be kept as is, because it is the name inside the applet.
Example for Turkish : "Nouveau=Clear" should be "Nouveau=Temizle" instead.
Also can be easily use for "level editor" too.
And perhaps with his "special permission" I share this program in my web page.

SOLVER 6 - MYSOL20
Download (from Paul Voyer's web page)
Special thanks to Author : Adolfo OVALLE
Based on Paul VOYER's applets. (Solveur56 & Solveur224)
Program is limited to default 17 boxes, adjustable by user.

SOLVER 7 - SOLUTION (SOKOSOLVE) - Sokoban Level Solver & Generator

Download from Here
Special thanks to Author : Paul KEIR
A Dos program with help document.
Program can be run in one of 2 ways :
Solver : The solution is not for optimal.
Generator : If no parameter is given, the program will sequentially generate every 4 by 4 room, check if it is possible, then save it. Currently it saves a generated room if it is possible, AND its solution is at least 14 moves. It saves files and solutions in directories created in the current one, with names like 0, 1, 2, 3, 4...

SOLVER 8 - TSE'S SOKOBAN v 1.1.6 'S SOLVER (sk3solver2)
Download Web Page
Special thanks to Author : T T K Tse Shum FAT
This is the solver that was included in previous versions of Sokoban++. For this to work you need to have Tse's Sokoban installed
Solver based on Java Applet Code of the Japanese Takaken.

SOLVER 9 - YASS - Yet Another Sokoban Solver - For Small Levels v 2.33 - Program Language is Delphi
Download web page - Web Page
Special thanks to Author : Brian DAMGAARD from Denmark - Mail2
A Windows console program with help document.
YASS v2.00 - 12/2004-01/2005 (and upper versions) support "Start With End Position" levels :)) T-H-A-N-K-S !
The program finds push-optimal solutions.
Push-optimal solutions may not be optimal in the sense that there can be other solutions of the same length which use fewer non-pushing player-moves.
Solving Sokoban levels is a complicated task for a computer program, hence, the program can only handle small levels.
(YASS v1.25 also find move-optimal solutions and given in same .zip file too. Move-optimal solutions are optimal, but the search is much slower than searching for push-optimal solutions.)

SOLVER 10 - SOLVSOKO v 1.2
Web Page - Download Web Page
Special thanks to Author : Jim HOWELL
Solver for Allan B. Liss’s Sokoban.
It will probably not work with other versions of Sokoban. And for only for Allan B. Liss’s Sokoban levels.

SOLVER 11 - UNCLE CHUCK'S SOLUTIONS
Web page - Download Web Page
Special thanks to Author : Uncle Chuck (George Meier)
HTML program with Play or Solve His Levels.
You can also find his game's level's solution tips with pictures or animation pictures.

SOLVER 12 - SOKOSOLVE - Program Language is C++
Homepage and Project Web Page - 2
Special thanks to Author : Guy LANGSTON
SokoSolve is a Sokoban puzzle solver and related tools. Features include: Puzzle Solver, The Full Game, Level Editor, XML Puzzle & Solution Library, general Analysis Tools and Level Generator.
It works 32-bit MS Windows (95/98), 32-bit MS Windows (NT/2000/XP), All 32-bit MS Windows (95/98/NT/2000/XP), All BSD Platforms (FreeBSD/NetBSD/OpenBSD/Apple Mac OS X), All POSIX (Linux/BSD/UNIX-like OSes), FreeBSD, Linux, Win2K, WinXP systems.

SOLVER 13 - JSoko Applet v1.07 - Playable with every operating system supporting Java; for MacOS 10.3 too
Special thanks to Author : Matthias Meger
A java program with a solver included. Download - 2
It haven't implemented the possibility to import levels from clipboard for applet. But you can start that applet as application.
Just type "java -jar JSokoApplet.jar". Started as an application the programm is capable to import levels from clipboard or load levels from harddisk.
Solver is designed to find "pushoptimal" solutions which is a lot more difficult than finding just any solution. So for just solve rather small levels / rather easy levels.
The sourcecode of his Java applet is published too.
And for "Start With End Position" Levels" the solver included in the applet will show "Level solved" when loading such a level. However, if you say "Solve Level" from the "Solver"-menu the solver would solve the level. So it can be used to solve "Start with end position"-levels. :)) T-H-A-N-K-S !

SOLVER 14 - POCOSOLV V 1.0d - A solver program for Sokoban and Pocoman - 5 March 2006
Download Web Page with UserGuide.txt
Special thanks to Author : David White
It finds a solution in the fewest pushes possible, but at this stage it's mostly limited to small to medium sized puzzles if you want an answer in a reasonable period of time. It works best for highly congested puzzles.

SOLVER 15 - PROLOG SOLVER GENERATOR
Download - 2
This is a solver for programmers only. It generates a solver for a level in the Prolog language. The solver is very bad, more than 2 boxes is taking way too long to solve. You need a Prolog compiler to run the generated solver, for example SWI-Prolog. From the prolog command prompt, simply type "solve." (including the dot) to start the solving.

SOLVER 16 - SOKOBAN SOLVER - FOR MACINTOSH - (sokoban.tar.gz)
Download Web Page
Special thanks to Author : W. Hummel
It is written in C and can be compiled without need of any further libraries.

SOLVER 17 - JESOKOBAN SOLVER
Download Web Page
Special thanks to Author : Johan Eliasson from Uppsala
jeSokobanSolver is using a brute force, depth-first alghoritm coupled with a number of optimizations that drastically reduces the time to find a solution. The goal of jeSokobanSolver is to find the OPTIMAL solution for any level, not just ANY solution. The optimal solution is the one that requires the least number of moves to complete the level.
Will solve any sokoban level (that is solvable). Finds the OPTIMAL solution (least number of moves). No restrictions on level size, or number of blocks, or available memory. I don't like restrictions. The software is way too slow right now. No worries though, all in good time. :)
A note on the output of the program: I'm using the letters N,S,E and W for North, South, East and West. I'm also "compressing" the string by replacing multiple occurances of a direction with a number and the direction. Thus instead of "neeeeesennnessssss" the output will read "n5ese3ne6s". It's an obvious improvement resulting in a shorter solution string, and easier to read. I call this format "C-NSEW".
From 2005-05-18 JeSokobanSolver solve "Start with end position"-levels. :)) T-H-A-N-K-S !

SOLVER 18 - SOKOBAN SOLVER ROLLING STONE - October 16, 1999
Pushing the Limits: New Developments in Single-Agent Search
Special thanks to Authors : Andreas Junghanns from Edmonton, Alberta and Jonathan Schaeffer from Edmonton, Alberta

SOLVER 19 - EASYSOK v0.3.5 - released 2005-03-14 - Operating System : All POSIX (Linux/BSD/UNIX-like OSes) - Program Language is C++
Download web page
Special thanks to Author : Ralf Schmelter
EasySok is a sokoban game for KDE. It is themeable, has a level editor and a solver, various import/export functions, a retro mode and other nice features.

SOLVER 20 - SVB_SOLVER - Program Language is Dos
Download web page in Russian lang.
Special thanks to Author : Serg
Download Game - Level Solver - Level Generator - Squares Generator - TxCalc from here - 574kB
Sorry for explain, but you can find Google translated web page here

SOLVER 21 - SOKOBAN SOLVER
Download web page
Special thanks to Author : Bartosz Podlejski

SOLVER 22 - PATH-SEARCHING TEST PROGRAM Ver.1.1 2004.06.02
Web page is closed - Download from Here
Special thanks to Author : David Woods

SOLVER 23 - SOKOBAN SOLVER - REASONING UNDER UNCERTAINLY
Web page
A Dos program, download web page
Special thanks to Author : Eric Bengfort

SOLVER 24 - MZMSOLVE
Web page
Special thanks to Author : Malcolm Tyrrell
A program which solves MazezaM levels.
The program can find three different types of solution:
Any solution : Uses a depth-first algorithm to find a solution as quickly as possible.
Move-optimal : Uses a breadth-first algorithm to find a solution with the fewest moves. This is slowest.
Push-optimal : Uses a breadth-first algorithm to find a solution with the fewest pushes. This is faster than finding move-optimal solutions. Note: the solution produced is not guaranteed to be a solution with the fewest moves of those which have the fewest pushes.
New : An implementation of the A* search algorithm. For levels of human-solvable size, this is slower than the above searches, so it is not the default. For finding move-optimal solutions, it should handle large levels better than the defaults. Unfortunately, have yet to find a good heuristic for guiding push-optimal searches, so don't expect it to work well in that case. Download

SOLVER 25 - Box World Solver 1.03
Web page
Special thanks to Author : Duisendpoot - South Africa mail
An optimised solver for Sokoban (aka. Boxworld) with all 32-bit MS Windows (95/98/NT/2000/XP) - max. 200 moves
You can easyly see picture frames solution and can be use like a level editor.
Download From Here

SOLVER 26 - Ban (solveban) - For now abandonware
Special thanks to Author : Sinisa Segvic
Program Author's notes :
This is solveban, an educational program to demonstrate some principles behind solving a turn-based game such as Sokoban.
The program can solve some of the games from the Microban suite, but is quite unsuited for regular levels.
I started writing this as a future lab excercise, however I stopped working on AI courses a few weeks before I finished the first version.
Thus, the project became abandonware a long time ago.
Feel free to use the program under the Free BSD license.
I request program from authot by email, you can Download From Here

SOLVER PLUG-INS FOR GAMES (A to Z) :

SOKOBAN++ v1.6.1
You can find at Sokoban++'s web page author Joris Wit.
YASS (Yet Another Sokoban Solver) plug-in
PocoSolv plug-in (1.0d)
BoxSearch plug-in
Tse's Sokoban Solver plug-in
Prolog Solver Generator
Takaken Solver plug-in based on an older version of the Takaken solver (version 2.7)
If you want to make your own solver plug-in, download the development kit from the Sokoban++ 's solver's download page on Sokoban++'s web page. With this kit an example with source code is included.

SOKOBAN YASC (Yet Another Sokoban Clone)
All Sokoban++ plug-ins can use in Sokoban Yasc web page author Brian Damgaard, Denmark.

A HINT AT SOLVER PROGRAMS FOR MY "START WITH END POSITION" LEVELS :

Only ;
YASS - Yet Another Sokoban Solver - For Small Levels v2.00 - 12/2004-01/2005 (and upper versions)
&
SPS v3.72 - 04/2005 (and upper versions)
&
JSoko Applet v1.07 (and upper versions)
solver programs supports these levels !

The other solver programs does not support these "Start With End Position" levels, (they gave 0 moves for solve answer) and I find this hint :

There are 2 ways for introduce "the" level for any solver program. You must "think" the first push and :

1) make the first push and then copy and paste for the solver program

2) the first push and change the * to . with add space to $

like this :
for #@* # :
1) make : # +$# your first play "R" (please don't forget you must add the first push "R" for your solution)

2) make : #@.$# in this time solver programs will say your first push "r", please make that "r" to "R" for your solution)

example :
        ####
    #####  #
    #      #
    # ### *##
 #### # * * ##
 #    #  * *@#
 # #  # # * ##
 # ##      ##
## ### #####
# **  * #
#       #
#  ######
####
Title: Original level erim172.xsb
Author: Erim SEVER from TURKEY

and for all solver programs copy and paste this (first way) :
        ####
    #####  #
    #      #
    # ### *##
 #### # * * ##
 #    #  *$+ #
 # #  # # * ##
 # ##      ##
## ### #####
# **  * #
#       #
#  ######
####
Title: First push played at erim172.xsb
Author: Erim SEVER from TURKEY
(At solution, you must add beginning push "L")

or this (second way) :
        ####
    #####  #
    #      #
    # ### *##
 #### # * * ##
 #    #  *$.@#
 # #  # # * ##
 # ##      ##
## ### #####
# **  * #
#       #
#  ######
####
Title: First push played but sokoban man at first place at erim172.xsb
Author: Erim SEVER from TURKEY
(At solution, youmust change first move "l" to push "L"

I wish you like idea...

SOKOBAN LEVEL SOLVER :
SOLVEUR 56 - Limit 11 Box

Java Sokoban Solver Program by Paul VOYER from FRENCH
Based on the Algorithm by Ken'ichiro TAKAHASHI (Takaken)
Solver on my design skin "XSB Format"

SOKOBAN LEVEL SOLVE ANALYSER (LuRd) :
( If you have 1- Level and solution 2- Solution only )

This Analyser is getting from Sokoban.Online.Fr © 2001 - François MARQUES Mail1 - Mail2
I'm still waiting François MARQUES 's special permission !!! Now online available for only test.

Level :

Solution :

Condense LuRd
Analyser
Comments :

RESULTS :

Useful Level :

Size :		Number of boxes :

Number of Moves :

Number of Pushes :

Linear Pushes :

Box Changes :

Pushing Sessions :

The original codes with rotate level and solution but i can't put these addings here.
I rebuilt some levels with this algorithm :
erim179.xsb to erim181.xsb with Michael STEINS's rare solution,
erim156.xsb to erim182.xsb with Philippe LAMAT's rare solution,
erim181a_sharpen.xsb to erim181b_sharpen.xsb with Marek LETRAB's rare solution.

SOKOBAN LEVEL SOLUTIONS :

Original Sokoban (50) & Yoshio Murase autogenerated (52) & Yoshio Murase handmade (??) Solutions Web page closed
Sokoban Levels and Solutions Web page closed
SPS Solver Author's Sokoban Solutions DB Search (Type level number / name / collection name / XSB map of the sokoban level you look for a solution)
Enter a Sokoban Solution Manually - for XSokoban
Solution to Box World
Uncle Chuck's Sokoban Solutions - Interactive Java Applets 1 - 2
George Meier's Sokoban Solutions with pictures
Soko Hunter solution files for original levels