Rolling Stone solver

_{Published: May 15, 2026}

A pioneering automated Sokoban solver, created in 1997, whose development stopped around 2000. It used a standard set of 90 problems from Xsokoban. The solver is of historical interest. Newer automated solvers have surpassed it, but it's a great resource for learning. A modern successor may be Sokolution, due to its use of classical algorithms. You can find a version of Rolling Stone for Windows here.

I have been intrigued by the fact that a paper from 2001 reported that Rolling Stone solved 59 problems, a number I suspected was wrong, with the real number being 58, as I mentioned here. However, worth mentioning is that there was not a single version of the program. The papers mention versions from R0 to R10.

Considering that the documented achievement used the last version featuring the Rapid Random Restart enhancement (R10), whose source code is currently lost, I wanted to determine whether it is possible to solve at least 58 puzzles using the last public version of Rolling Stone, which seems to correspond to version R9.

Using standard search, 53 problems are solved:

#1–12, 17, 19, 21, 23, 25, 26, 33, 34, 36, 38, 40, 43, 45, 49, 51, 53–65, 67, 68, 70, 72, 73, 76, 78, 79, 80, 81, 82, 83, 84.

Solving #23 took nearly 9 hours. ⌛

Here is a trick to solve more problems: searching with different overestimation values instead of the default value (0).

Here is a custom overestimation value mentioned in Pushing the Limits: New Developments in Single-Agent Search (1999), page 129:

#77: Overestimation 2.2.
For this problem also works: 2.3–2.5, 2.7–5.0

This increases the list of solved problems to 54. It is the same list that appears in that paper on page 127.

It is possible to create a script, that searches using a distinct overestimation value ranging from 1.0 to 5.0, with a time limit of 7 minutes per value (420 seconds) to find the values that yield solutions.

Using that approach, I found these:

#28: Overestimation 2.2.
Also works: 2.6, 2.8, 3.0–3.1, 3.3–3.4, 3.6, 3.8–5.0.

#30: Overestimation 1.0.
Also works: 1.1–2.9, 3.2–3.3, 3.5–3.8, 4.0, 4.2–4.3, 4.5–4.6, 5.0.

#71: Overestimation 3.1.
Also works: 3.3, 3.4, 3.6–4.8, 5.0.

#75: Overestimation 1.8.
Also works: 2.5, 2.7, 2.8, 3.1, 4.0.

This increases the list of solved problems to 58.

Testing overestimation values with problems that have already been solved could reduce the search time, though it yields less optimized solutions regarding pushes. For example:
Problem #23: 8+ hours to around 2 minutes (1.5 overestimation)
Problem #26: 20 minutes to 1 second (5.0 overestimation)
Problem #36: 40 minutes to 25 seconds (5.0 overestimation)

The most impressive problem to solve was #71. Using standard search, the solution is not found, even after waiting more than two days. Using an overestimation of 3.1, the solution is found in 32 seconds.

Commands inside Rolling Stone to solve problem #71 using an overestimation of 3.1:

T 420
O
V 3.1
<
S 71

Table of solutions found

Curiosity: In the program files, there is a file named screen.91. It only contains the puzzle. The puzzle with author information can be found in the sokoban-ml-scratch set (Japanese Mailing List). I include it here for reference.

###############
#   ##   ##   #
#   #  $ $    #
##$ $ ## ######
#  $  $ $     #
# $ $ ## ##   #
#  $ #.....#  #
##   #.#...#$ #
# $ $ ..#..   #
#  $ #... .#$##
# $ $#..*..# #
#  $  ## ##  #
##$ $  @$   ##
#        ####
##########
Author: Darse Billings <darse@cs.ualberta.ca>
Comment:
Andreasさんの "Rolling Stone"のア〖カイブに #91として箭峡されて
いる烫です。笆涟疽拆された烫(附 sokoban-ml #27)とは操湿の疤弥が
办つだけ般います((5,4) -> (6,4))。

[-][*][-][-] [sokoban-ML - No.00707]
[+][*][-][-] [sokoban-ML - No.00140]
Comment-End:

Regarding the script I utilized, here it is.

—Carlos