Class Tree  

Description 
Sokoban is a game puzzle developed by the Japanese company Thinking Rabbit, Inc. in 1982. 'Sokoban' means 'warehousekeeper' 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 n1 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 boxfree 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 () LevelAuthor: Jacques Duthen 
Encodings 1  3 of 3 
