Class Tree
Description Sokoban is a game puzzle developed by the Japanese company Thinking
Rabbit, Inc. in 1982. 'Sokoban' means 'warehouse-keeper' in Japanese.
Each puzzle consists of a room layout (a number of square fields
representing walls or parts of the floor, some of which are marked as
storage space) and a starting situation (one sokoban and a number of
boxes, all of which must reside on some floor location, where one box
occupies precisely one location and each location can hold at most one
box). The goal is to move all boxes onto storage locations. To this end,
the sokoban can walk on floor locations (unless occupied by some box),
and push single boxes onto unoccupied floor locations.

In our setting, an instance contains the warehouse layout, representing
the floor locations, and in particular their horizontal and vertical
relationships, and storage locations, where the boxes should eventually
go to:
right(L1,L2) : location L2 is immediately right of location L1
top(L1,L2): location L2 is immediately on top of location L1
solution(L): location L is a storage location

An instance also consists of a description of the initial configuration:
box(L): location L initially holds a box
sokoban(L): the sokoban is at location L
It can be assumed that each instance has exactly one sokoban.

In order to keep the search space small, we consider the sokoban walking
to a box and pushing it any number of fields in one direction as an
atomic action. This is motivated that in any minimal solution, the
sokoban will walk without pushing only in order to push a box, so making
walking an action on its own is superfluous. Moreover, pushing a box
several fields in one direction does not involve any walking (in a
minimal solution), and thus it makes sense to collapse it into one
action. An instance also contains a fixed number of labels ('steps') for
configurations, between which these atomic actions occur, and their
successorship relation:
step(S): S is a step
next(S1,S2): step S2 is the successor of step S1

Please note that for n steps, exactly n-1 actions should be performed
if not minimizing the number of pushes, while the goal for the optimization
problem is to find the minimum amount of pushes as described next.
Any answer set should contain a sequence of push actions (as defined
above, in the syntax described next), such that between each pair of
successive configurations exactly one push action is performed and such
that in the final configuration all target locations contain a box. The
sequence of push actions should be represented by atoms of the form
push(Bbefore,D,Bafter,S), where Bbefore is the location of the pushed
box at step S, D is a direction (one of the constants right, left, up,
down), Bafter is the location on which the box ends (where it will be
in the next step), and S is the step in which the push is initiated.

A push action is feasible if the sokoban can reach the field, from which
the pushed box is in the adjacent location in the pushed direction (i.e.
o the location adjacent to the pushed box in opposite push direction),
on a box-free path of locations at step S (going any direction).
Furthermore the location on which the box ends must obviously be in the
correct direction and all fields in the pushed direction up to and
including the end location must not contain any box at step S. In the
successive step, the pushed box will be on the new location, and the
sokoban will be adjacent to the pushed box in opposite pushing
direction. All other boxes are on the same locations as in the previous
step.

Author: Wolfgang Faber ()
Level-Author: Jacques Duthen
Encodings
1 - 3 of 3