computers can solve sokoban levels?

Questions on levels and solutions
Post Reply
Posts: 11
Joined: Mon Mar 22, 2004 10:50 pm

computers can solve sokoban levels?

Post by Roberto »

Hi everyone! I'm not a computer expert, so I wonder if the advanced computers of this days (like deep blue) can solve huge sokoban levels with lots of pieces (#boxes>10). If this machines can make milions of calculations in a second for solving tradicional board games like chess and checkers, can't they do the same for sokoban? Beside, can they find the best solutions (minimal number of moves, pushes, ans so on...)? I've tried to use some solvers avaiable on the internet into my computer, but for some kinds of levels (like that ones of Francois Marques) they dont't work. It's even more difficult if I choose the option 'with best moves' or 'best pushes'.

I ask that because I've just been at Francois Marques excelent page ( There, I've seen the 'challenges of the month' section (, in which some boards are like I've described above. For each sokoban challenge, there is a list of records. I wonder if the records listed there are really from human brains or from the computer chips.

Unfortunately, there are no more challenges at that page for the months after November/2003. And I hope someone here in this forum could tell me where I can find sites like Francois': with challenges, new challenges in the next month (or week) and a list of records. Thanks.

Posts: 2
Joined: Thu Sep 02, 2004 1:31 am

Re: computers can solve sokoban levels?

Post by fst »

Super computers or expert systems can solve huge sokoban puzzles with some complex algorithms and find a solution (not the best) for it. This level may be a very huge maze like size of 128x128, but used artificial search algorithms does not guarantee that it will find a solution for every level.

The algorithms used for finding the best solution is really slower and un-efficient so the result depends on movable area of the maze and number of boxes.

Sokoban game is really different from chess and chess-like games. In the chess game, you don't have to think the deepest move. In computers, Chess engines regulate their moves according to time to think. They think the moves deeper and deeper and some point they decide that the best move is found. So the computer does not have to think checkmate position from beginning, and after each move they generally think from that position as it is the beginning position (for ex. they forget the exact beginning position of the chess game because there is no need) but in Sokoban game, a computer must think from the beginning until the solution is found. Therefore, the computer needs less calculations for chess game :)

If someone finds the real-sokoban algorithm someday, then sokoban game would be finished by computers but hey it is not still found for the chess game :)

Posts: 3
Joined: Tue Sep 14, 2004 10:21 pm

Re: computers can solve sokoban levels?

Post by SpOiLeR »


Although I know at least two great sokoban solving programs I don't really use them as long as author of level guaratees that level is solvable. Using solvers just spoils fun of trying to find perfect solution by myself. I'm kind of fanatic with that, because there are levels that I have found like 9 diferent solutions. Of course, there is always one best solution for moves and one for pushes, but just keeping tryng to find it by myself makes whole fun of sokoban. What do you people think about that? Are you satisfied with first solution found or you keep searching even when level is solved?

Ah, yes, the programs I was talking about...

First one is rbox (link to it is in download page of Sokoban)

Second one can be found at :

I have tried both of them, and rbox ocasionally gives shorter solutions, but SPS looks better and it supports Sokoban+ levels (although I haven't tried that part of it)...
:P :shock:

Posts: 4
Joined: Wed May 11, 2005 9:42 am

Re: computers can solve sokoban levels?

Post by Nebol »

Of course it's possible to solve Sokoban levels.

Here's the webpage about my own solver-software:

My software can currently find the optimal solution for the 3500 or so easiest levels within a reasonable amount of time... but then it goes downhill as the levels grow in complexity. But I have many ideas on how to improve on the time needed to find the solution.

Serg Belyaev
Posts: 1
Joined: Sun Nov 19, 2006 7:55 pm

Re: computers can solve sokoban levels?

Post by Serg Belyaev »

Here's my solver-software:


Posts: 99
Joined: Wed Dec 22, 2004 1:20 am

Re: computers can solve sokoban levels?

Post by CellarDweller »

It is now October 2019, and I'm looking for a solver. It seems they're all gone or don't work anymore for various reasons.

I used to use SPS from Codecola, but that's nowhere to be found.

Can anyone help?
Post Reply