Sokoban Optimization

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.

In order to keep the search space small, we consider the sokoban walking to a box and pushing it a certain number of locations 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 considering 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.

In the optimization version of this problem, the minimum number of walk-and-push actions should be determined, providing a witness for this minimum.

Predicates

• Input: right/2, top/2, solution/1, box/1, sokoban/1, step/1, next/2

• Output: push/4

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. This information is encoded as facts using predicates right/2, top/2, solution/1, as follows:

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, encoded as facts using predicates box/1 and sokoban/1, as follows:

box(l): location l initially holds a box sokoban(l): the sokoban is at location l

Each instance has exactly one fact for sokoban/1.

An instance also contains a sufficiently long sequence of time-steps for warehouse configurations, between which the actions occur and their successorship relation, using predicates step/1 and next/2 as follows:

step(s): s is a step next(s1,s2): step s2 is the successor of step s1

The information encoded by next/2 will always form a sequence (a linear acyclic graph).

Output format

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 walk-and-push action is performed and such that in the final configuration all target locations contain a box.

The sequence of walk-and-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 up (where it is in the next step), and s is the step in which the push is initiated.

A walk-and-push action is feasible if the sokoban can reach the location adjacent to the box location from which the box can be pushed in the indicated direction (i.e. the location adjacent to the pushed box in opposite push direction). This location must be reachable from the sokoban's location on a box-free path of locations at step s (going any direction and making arbitrarily many turns). Furthermore the location on which the box ends up 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.

Example

Author(s)

• Author: Wolfgang Faber
  • Affiliation: University of Calabria, Italy