Sokoban (Japanese for "warehousekeeper") is a game puzzle which has originally been developed by the Japanese company Thinking Rabbit, Inc. in 1982.

Each puzzle consists of a room layout, which is given by tiny ("atomic") square fields representing wall or floor locations, which are aligned in a rectangular grid. It is sufficient to represent floor squares and the upper, lower, left, and right neighbour relation, resp. its symmetric reduction, since wall squares serve only as boundaries of and holes in the warehouse floor. Floor locations can be designated as solution squares.

Each floor location can be occupied by at most one box or the Sokoban (but not simulataneously). The number of boxes (which are undistinguishable) varies from puzzle to puzzle, but there is always only one Sokoban.

The goal is to get from a given initial situation to a situation in which all boxes reside on solution squares, by moving the Sokoban and the boxes. Boxes can only be moved by the Sokoban. To do so, the Sokoban must be located next to the box, and behind the box (from the Sokoban's point of view) an empty field must exist. Then the Sokoban may push the box onto the empty field, so after the action both the Sokoban and the box have moved by one square. The Sokoban alone is allowed to move from empty fields to other empty fields.

In order to make the number of actions manageable, it is sensible to group multiple pushes of the same box in the same direction to a single action. Likewise, the walk actions are not very interesting, and they can be omitted as long as it is sure that there is an unobstructed path to the square in which the next push action is initiated. It can be further assumed that there are exactly the same number of boxes as there are solution locations.

The problem of deciding whether a fixed-length sequence of generalized actions leading from the initial state to the goal state exists can be solved using Answer Set Programming.

There is a standard for representing Sokoban puzzles as an ASCII file, characters represent the little squares, and the neighboring relation is implicit by rows and columns of the file. It should be noted that room layout and initial situation are mangled in the description. Furthermore, usually only the bounding walls are drawn, and hence only floor squares reachable by the Sokoban are considered. The meaning of the characters in these files is as follows:

INPUT: A room layout and initial situation as described above, and an integer k defining the number of pushes that should be made. The goal situation follows from this information.

OUTPUT:A sequence of length k of generalised push actions (as described above) which leads from the initial situation to the goal situation, if such a sequence exists.

DATASETS:

Name	k	solvable
yoshio-auto.5	13	yes
yoshio-auto.6	10	no
yoshio-auto.7	11	yes
yoshio-auto.28	11	no
yoshio-auto.35	12	yes
yoshio-auto.51	10	no
duthen-990602.37	13	yes
duthen-990602.48	14	no
duthen-990602.51	14	yes
original.1	7	no

NOTES:

An example encoding for DLV can be found in sokoban.dl. The input parameter k is set on DLV's command line. The DLV call for the first instance is:

DLV sokoban.dl yoshio-auto.5 -N=13 -n=1

duthen-990602.* are by Jacques Duthen. We have downloaded them via the ksokoban page at http://hem.passagen.se/awl/ksokoban/, the direct link is http://hem.passagen.se/awl/ksokoban/sokogen-990602.skm.

original.1 is the first level of the original Thinking Rabbit game. It is contained e.g. in the xsokoban distribution.

We provide a Tcl script sokoban2facts.tcl, which transforms one such puzzle (passed via stdin) to facts as in the example instances (on stdout). Often, puzzles are grouped into files, so we provide an awk script  split-puzzles.awk and a shell-script frontend split-puzzles which splits such a file into multiple single-puzzle files.

There are many resources and levels around. A starting point could be the Yahoo Sokoban Club.