Sokoban

Problem 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.

Input format

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

Output format

Please note that for n steps, exactly n-1 actions should be performed. 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(b_before,d,b_after,s), where b_before is the location of the pushed box at step s, d is a direction (one of the constants right, left, up, down), b_after 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.

The action of pushing a block to its current position has no effect. Yet, since one push action is needed per time point, such dummy actions may be necessary to solve certain instances of the competition!

Author: Wolfgang Faber.