SEARCH ENGINE :

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^{42} 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 prealpha2 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 bestpush or bestmove. There are other algorithm in program tool to get bestpush or bestmove, 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, reoptimize 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 :)) THANKS ! 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  RBOX 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 "JXmx224m" Special thanks to Author : Paul VOYER Published by Paul VOYER 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/200401/2005 (and upper versions) support "Start With End Position" levels :)) THANKS ! The program finds pushoptimal solutions. Pushoptimal solutions may not be optimal in the sense that there can be other solutions of the same length which use fewer nonpushing playermoves. Solving Sokoban levels is a complicated task for a computer program, hence, the program can only handle small levels. (YASS v1.25 also find moveoptimal solutions and given in same .zip file too. Moveoptimal solutions are optimal, but the search is much slower than searching for pushoptimal 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 32bit MS Windows (95/98), 32bit MS Windows (NT/2000/XP), All 32bit MS Windows (95/98/NT/2000/XP), All BSD Platforms (FreeBSD/NetBSD/OpenBSD/Apple Mac OS X), All POSIX (Linux/BSD/UNIXlike 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. :)) THANKS ! 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 SWIProlog. 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, depthfirst 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 "CNSEW". From 20050518 JeSokobanSolver solve "Start with end position"levels. :)) THANKS ! SOLVER 18  SOKOBAN SOLVER ROLLING STONE  October 16, 1999 Pushing the Limits: New Developments in SingleAgent Search Special thanks to Authors : Andreas Junghanns from Edmonton, Alberta and Jonathan Schaeffer from Edmonton, Alberta SOLVER 19  EASYSOK v0.3.5  released 20050314  Operating System : All POSIX (Linux/BSD/UNIXlike 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  PATHSEARCHING 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 depthfirst algorithm to find a solution as quickly as possible. Moveoptimal : Uses a breadthfirst algorithm to find a solution with the fewest moves. This is slowest. Pushoptimal : Uses a breadthfirst algorithm to find a solution with the fewest pushes. This is faster than finding moveoptimal 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 humansolvable size, this is slower than the above searches, so it is not the default. For finding moveoptimal solutions, it should handle large levels better than the defaults. Unfortunately, have yet to find a good heuristic for guiding pushoptimal 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 32bit 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 turnbased 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 PLUGINS 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) plugin PocoSolv plugin (1.0d) BoxSearch plugin Tse's Sokoban Solver plugin Prolog Solver Generator Takaken Solver plugin based on an older version of the Takaken solver (version 2.7) If you want to make your own solver plugin, 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++ plugins 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/200401/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 : SOLVEUR 56  Limit 11 Box
Based on the Algorithm by Ken'ichiro TAKAHASHI (Takaken) Solver on my design skin "XSB Format" ( 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. 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 