Sokoban Puzzle Solver

            Sokoban Puzzle Solver is easy to use software that can solve Sokoban puzzles. It is completely free. The idea of creating such a software has come to my mind after I felt madness and crazy in my brain while I was trying to solve a Sokoban puzzle. SPS has some methods to find out possible moves and combinations. It calculates all possible and sensible moves and tries to find new combinations. It uses some database files to store combinations. Since a solution has been reached in >70 moves in even a simple maze, figuring out a move in depth of 70 is not easy.

            In Chess games, when computer player thinks, computer does not have to find checkmate position. If there are 25 sensible combination of moves in a position, even famous chess programs can see in depth of 12. This is not a despisable number ofcourse. After 12th depth , the number of combination reaches a big number : 25 ¹² = 5.96 x 10 ¹⁶ which means   59,600,000,000,000,000 sensible moves.

            In Sokoban game, computer must find the shortest solution. There are only 4 moves max. at a position. But the depth is crazy. Even in a simple maze, A solution comes after 70 moves which means the depth of 70. This number makes the game impossible to be solved : 4 ⁷⁰ = 1.39 x 10 ⁴² which means 1,390,000,000,000,000,000,000,000,000,000,000,000,000,000 moves. However it is not impossible to solve a maze. See Info section.

 Sokoban Puzzle Solver v1.2 :

            SPS has a simple and user friendly menu to control the maze : File, Puzzle, Play, About.

 File : File Menu allows you to do file operations such as loading map, loading / saving solutions, and to exit program.

            Load LAB : Allows you to load LAB (Labyrinth) file. LAB file contains the data of maze, blocks and targets. You can learn how to make LAB file in this page below.

            Load Solution : Allows you to load SLN (Solution) file. This option will be active when a LAB file loaded. You can load a solution by this option to see how the solution is. The SLN file must be the solution of the current loaded LAB file.

            Save Solution : Allows you to save SLN file. This option will be active if there is a solution found, after solving the puzzle. You can use Load Solution to see the solution later.

            Exit : Quits the program. It is not recommended to exit program while solving. You should stop solving first.

 Puzzle : Puzzle Menu is the most important menu. It allows you to start computer thinking for solving, stopping, or showing solution.

            Start Solving : This option allows you to start the computer solving and will be active after LAB file loaded.

            Stop Solving : This option stops the solving operation and will be active while solving.

            Show Solution : After a solving operation, If there is a solution, then it will be active. You can select this option to see the solution on the map one by one move. You can click on map to see next move.

 Play : Play Menu allows you to play puzzle.

             Play Puzzle : It will be active after LAB file loaded. You can select this option to turn play mode on. You can use arrow keys to move the sokoban.

             Stop Playing : Turns play mode off.

             Reset Puzzle : Resets the puzzle to beginning position.

 About : About SPS :)

            You can see the maze on map :

: WALL     : TARGET     : SOKOBAN     : BLOCK      : BLOCK ON TARGET

            You can get information about status in Status Bar :

            You can also get information about 'scanned moves' or 'evaluated moves' in Info Section.

 How to create LAB file ?

            LAB File is text file, You can create it with notepad. Extension of LAB file should be '.lab'

Map

Example for LAB file

 Description

First Line must be the number of lines for maze data containing 1s and 0s.

It can be max. 64.

'1' : Walls

'0' : Empty zones / Floors

Each line can be max.64 characters long.

After maze data, coordinate datas are coming. Coordinates start from 0. That means coordinate of left most and top most zone, is 0 0. (x,y).

x defines left to right, y defines top to bottom.

Sokoban's coordinate (x,y)

Number of blocks

Coordinate of block (x,y)

Coordinate of block (x,y)

Coordinate of block (x,y)

Coordinate of target zone (x y)

Coordinate of target zone (x y)

Coordinate of target zone (x y)

 Sokoban Puzzle Solver v1.3 :

          . In 'Play' menu, 'Control Moves' feature added. If you turn this on, SPS control your moves for bas moves while you are playing. If It warns, than that means 'Reset Puzzle' should be selected :))

 Sokoban Puzzle Solver v2.0 :

          . 'Priority' menu added. You can switch to high priority mode to solve faster when multiple processes running on your machine. If you don't have any other proccess running on your machine, you don't need to switch to high priority because it will not make it faster.

          . 'Make' menu added. You can create your own LAB files. You can select 'Make Puzzle' to switch the make-puzzle mode. After selecting the object (Wall, Block, Sokoban, Target), you can put it onto map by clicking mouse. Walls and blocks can be removed, if they are already exist on clicked place. Targets will be automaticly put on coordinates (0,0) when you put blocks. If you try to put a target on the map, then a target on (0,0) will be moved to the place you click. You cannot put targets more than blocks. If you want to change a target's place, click on existing target then It will be removed to (0,0) again. Now you can click on map where you want to put.

             After you finish to create the map, you can select 'Save As LAB' to save your map. To Play or solve, You should turn the make-puzzle mode off and load your LAB file again.

           . IMPORTANT : Format of solution files (.sln) in v1.3 and v2.0 are different. You can't use .sln files generated by SPS v1.3, in SPS v2.0 and viceversa.

 Sokoban Puzzle Solver v3.0 :

            . Faster solutions with improved methods and functions! Progress Bar has been removed since it became useless with new methods and now there are two info lines. One shows forward moves, the other shows backward moves. The total depth is the sum of forward depth and backward depth.

            . Format of Solution (.sln) files changed again. You can use (.sln) files of v2.0 in v3.0, but you cannot use (.sln) files generated by v3.0 in v2.0.

            . Timer added to see calculation time.

 Sokoban Puzzle Solver v3.1 :

            . Some information is in 'News' section in main page.

            . The techninal change in this version, is 'Forward' and 'Backward' solvings are independent. More amount of time is wasted for which one gives more depth at that moment.

            . A Bug fixed by changing and improving the function calculates 'blocked move'.

            . System Requirements Analysis is done for SPS 3.1;

                         Minimum System Requirements: P3 500Mhz, 256 MB Sdram, Win98, Max. 350 MB HD Space

                         Recommended System Requirements : P4 2Ghz+ , 1 GB Ram (RDram is recommended), WinXP

                                                                                           1,5 GB HD Space (7200+ rpm)

 Sokoban Puzzle Solver v3.2 :

            . 'Optimized Moves' : This option allows the program to act pushing a block continuously, therefore it does not switch the block to push and it continues to push the same block when it's necessary. This action creates a solution which is more humanistic and reduces the number of carry (a collection of pushing the same block continuously). It usually reduces the number of moves but it does not guarantee. This option never changes the number of pushes of the solution. It finds another shortest solution which has the same number of pushes. The option is not turned on by default. If you turn it on, It may change the duration of solving.

 Sokoban Puzzle Solver v3.3 :

             . 'Give Solution As Text' function : This function gives the solution as text in a new window. Each letter states a move. If a letter is capital, it is a push. (u - up , d - down , l - left , r -right) (UDLR for pushes). You can see number of moves and pushes at the end of the text. You can select and copy the text for later use. 'Close' button closes the window.

 Sokoban Puzzle Solver v3.4:

             . Multi XSB support allows you to load a level from multi XSB file in a given list. 'Show Level List' option bring the list of levels of currently loaded XSB file.

             . 'Load XSB From Clipboard' allows you to load any XSB file in clipboard. You can copy a piece from multi XSB file and use this function to load and use 'Show Level List' option to see the list of levels you copied.

 Sokoban Puzzle Solver v3.5:

             . See 'News' section.

 Sokoban Puzzle Solver v3.6:

             . SPS v3.6 supports solving Sokomind+ mazes which each block must be pushed onto specific targets.

             . 'Sokomind+' option allows you to switch to Sokomind+ mode. To use this option, simply load a sokoban maze and select this option. A small window will appear. Here you can enter block and target (box and goal) orders according to xsb file of a Sokomind+ maze by seperating numbers with space. For ex. BlockOrder : 1 2 3 4 5 , TargetOrder : 5 4 3 2 1. Note that each block and target must be numbered. More than one block or target may have same number, so unnumbered blocks and targets can be numbered with an unused number instead of leaving them unnumbered. For ex. BlockOrder : 1 2 3 99 99 98 98, TargetOrder : 99 98 1 2 3 98 99. In this example, each block no.99 must go onto one of the targets with number 99 and each block no.98 must go onto one of the targets with number 98. It is clear that, for normal sokoban mazes, all blocks and targets have same number. To switch to normal sokoban mode, select the option again.

 Sokoban Puzzle Solver v3.7:

             . "Choose Best" option allows SPS to continue to analyse pushes after a solution is found. SPS chooses the best solution which has the least number of moves from the generated pushes, if "Choose Best" option is selected. This feature allows SPS to give shorter solutions but it does not guarantee the best solution possible (which has minimum number of moves and is one of the solutions which have minimum number of pushes), because of some pushes that may be ignored and treated as a repeated position.

             . "Search Solution @ SSDB" feature allows you to search for a solution of the loaded puzzle from the Sokoban Solutions DB by using your browser and internet.

 Sokoban Puzzle Solver v3.72:

             . "Start With End Position" option allows SPS to solve the puzzles which start solved position. This kind of puzzle gives "0 push - 0 move solution" without selecting that option.