is a transport puzzle in which the player pushes boxes around a maze, viewed from above, and tries to put them in designated locations. Only one box may be pushed at a time, and boxes cannot be pulled. The puzzle is usually implemented as a video game.
Sokoban was created in 1980 by
Hiroyuki Imabayashi, and was
published in 1982 by Thinking
Rabbit, a software house based in
Selected Sokoban releases by Thinking Rabbit
- Sokoban (1982), with 20 levels.
- Sokoban 2 (1984), with 50 levels.
- Sokoban (1988), with 50 levels.
- Sokoban Perfect (1989), with 306 levels.
- Sokoban Revenge (1991), with 306 levels.
In 1988 Sokoban was imported to the US by Spectrum HoloByte
for the Commodore 64
Apple II series
, and by Spectral Associates
for the TRS-80 Color Computer
. A 1988 review
in Computer Gaming
praised the game for being "pure and simple, very
playable and mentally challenging," citing its addictive
Implementations of Sokoban
Implementations of Sokoban have been written for numerous computer platforms
, including almost
all home computer
and personal computer
systems. Versions also
exist for several hand held
video game consoles
, mobile phones
, graphic calculators
, and Canon PowerShot
digital cameras. Many other puzzle
games, such as Chip's
and Rocks and
, implement Sokoban-based gameplay. The roguelike computer
sequence of dungeon levels
designed to simulate a Sokoban game. The Royal Puzzle in Zork III
has elements of Sokoban.
Several puzzles can be considered variants of the original Sokoban
game, in the sense that they all make use of a controllable
character who pushes boxes around a maze.
:In the standard game, the
mazes are laid out on a tiling of
. Several variants apply the rules of Sokoban to mazes
laid out on other tilings. Hexoban
uses a tiling of regular hexagons
a tiling of
:In the variants Multiban
the player can control multiple
:Several variants adjust the
requirements for completing a level. For example, in
the boxes are different colours and the goal
is to push them onto squares which match their colours.
implements a similar idea, with boxes and
target squares uniquely numbered. In Interlock
, the boxes are also different colours, but the
goal is to move them so that similarly coloured boxes are adjacent.
, each level has a designated exit square, and
the goal is to reach that exit. In a variant called
, the elements of the level must be pushed onto
the goal in a fixed sequence.
Additional game elements
new elements to the basic puzzle. Examples include holes,
teleports, moving blocks and one-way passages. PocoMan
refers to the blocks as treasures and when placed onto the goal,
they transform into the treasure for the next level.
character can pull boxes in addition to pushing them.
Scientific research on Sokoban
can be studied using the theory of computational complexity
The problem of solving Sokoban
puzzles has been proven to
. This is interesting also for
researchers, because solving Sokoban
can be compared to
designing a robot which moves boxes in a warehouse. Further work
has shown that solving Sokoban
is also PSPACE-complete
is difficult not only due to its branching factor
(which is comparable to
), but also its enormous search tree
depth; some levels require more than
1000 "pushes". Skilled human players rely mostly on heuristics
; they are usually able to quickly
discard futile or redundant lines of play, and recognize patterns
and subgoals, drastically cutting down on the amount of
puzzles can be solved automatically by using
algorithm, such as IDA*
, enhanced by
several techniques which make use of domain-specific knowledge.
the method used by Rolling Stone, a Sokoban
solver developed by the University of Alberta GAMES Group.
The more complex Sokoban
levels are, however, out of reach even for the best automated
The 1988 Spectrum HoloByte version of Soko-Ban
for the IBM
was reviewed in 1988 in Dragon
#132 by Hartley, Patricia, and
Kirk Lesser in "The Role of Computers" column. The reviewers gave
the game 4 1/2 out of 5 stars.
- Joseph C. Culberson, Sokoban is PSPACE-complete. Technical Report TR 97-02,
Dept. of Computing Science, University of Alberta, 1997. Also:
- Andreas Junghanns, Jonathan Schaeffer (2001) Sokoban: Enhancing general single-agent search
methods using domain knowledge, Artificial
Intelligence 129(1-2):219-251 (Special issue
on heuristic search in artificial intelligence)