Joshua Taylor and Ian Parberry,
"Procedural Generation of Sokoban Levels",
Proceedings of the 6th International North American Conference on Intelligent Games and Simulation (GAMEON-NA),
pp. 5-12, EUROSIS, 2011.
Abstract
We describe an algorithm for the procedural generation of
levels for the popular Japanese puzzle game Sokoban. The
algorithm takes a few parameters and builds a random instance
of the puzzle that is guaranteed to be solvable. Although
our algorithm and its implementation runs in exponential
time, we present experimental evidence that it is
sufficiently fast for offine use on a current generation PC
when used to generate levels of size and complexity similar
to those human-designed levels currently available online.
What is Sokoban?
Sokoban (Japanese for "warehouse keeper") is a top-down puzzle
in which the player pushes boxes around a grid into specially marked destinations.
Only one box may be pushed at a time, and boxes cannot be pulled.
For example, the image at right shows how to move a single box to the destination location, which
is marked with a cross in the top left corner. The player is represented by the yellow bulldozer. See
the Wikipedia article
and the Sokoban Wiki
for more information about this game.
To play it yourself, download (for example) JSoko,
an open source Java implementation of Sokoban. The screenshots in this webpage were taken from JSoko.
(Disclaimer: We are not the creators of JSoko, and therefore cannot be held responsible for its content.)
Four Levels Solved
The following video shows four levels generated by our procedural generator being solved using JSoko's autosolver.
These are not necessarily the best solutions, nor are they the best possible,
but they are certainly plausible and give some indication of the difficulty of
the levels.
Try Our Procedurally Generated Level Sets
The following level sets were created by our generator.
Each one starts with easy (sometimes trivial) instances, and gets harder with each one
you solve.
To try it out for yourself,
first install JSoko if you haven't already, then download one
or more of the files below
into your JSoko folder.
(Note that each level set below is a human-readable text file.)
In JSoko, select Load Level from the menu bar, then External Level.
You will see a dialog box containing a list of files. Select one, click the Open
button, and start playing.
