Sokoban is a puzzle game in which the player must push crates around a
warehouse, trying to put them in storage locations. It was created in 1981 and
has since found a home in the AI research community as a useful problem domain
for testing automated planners.
The Sokoban world is a rectangular grid containing walls, crates, a player, and
storage locations. The goal is to push the crates to the storage locations. The
player can move around the world and push crates up, down, left, and right, but
only if the crate isn’t blocked by a wall or another crate.
|> (hash-visualize-plan! problem #:draw-state-with sokoban-pict)|
A predicate for grid spaces in a Sokoban level. A space is a pair of an X
coordinate and a Y coordinate.
Constructs a grid space with x
coordinates. The origin
(space 0 0)
represents the top left corner
of a Sokoban level.
Returns the X and Y coordinates of s, respectively.
A predicate for objects in the Sokoban world.
The various objects that can exist in a Sokoban level. The
objects are like the
objects, except they represent cases where
the player or crate is standing on top of a storage location space. Distinct
objects for these cases are necessary because the Sokoban world uses the
hash state representation
, so a single space cannot contain multiple
Constructs a hash table representing a Sokoban level with dimensions of
width and height. In addition to each of the space-object
pairs specified by the s and object arguments, walls are
placed on the edges of the level.
Constructs a set of all actions that are applicable
Constructs a set of all possible actions that could be performed over the
course of a Sokoban game starting from initial-state. This includes
actions that are not mmediately applicable, but which can be applied if other
The set of possible actions returned is an optimistic estimate. Every
possible action is returned, but some impossible actions may also be returned.
An estimate is returned because computing the exact set of possible actions can
be complex and prohibitively expensive.
of every Sokoban level is the same: push every crate into
storage. Because pushing a crate
into a storage location changes it
into a crate-in-storage
, this means that all that’s required to win is
for the Sokoban level’s hash table to not contain any crate
Draws a picture of state.