1 % Written by Wolfgang Faber <wf@wfaber.com>
   2 %
   3 % Input:
   4 % right(L1,L2) : location L2 is right of location L1
   5 % top(L1,L2): location L2 is on top of location L1
   6 % box(L): location L initially holds a box
   7 % solution(L): location L is a target for a box
   8 % sokoban(L): the sokoban is at location L initially
   9 % step(S): S is a step
  10 % next(S1,S2): step S2 is the successor of step S1
  11 
  12 % actionstep: can push at any step but the final one
  13 actionstep(S) :- next(S,S1).
  14 
  15 % utility predicates: left and bottom
  16 left(L1,L2) :- right(L2,L1).
  17 bottom(L1,L2) :- top(L2,L1).
  18 
  19 % utility predicates: adjacent
  20 adj(L1,L2) :- right(L1,L2).
  21 adj(L1,L2) :- left(L1,L2).
  22 adj(L1,L2) :- top(L1,L2).
  23 adj(L1,L2) :- bottom(L1,L2).
  24 
  25 % identify locations
  26 location(L) :- adj(L,_).
  27 
  28 % Initial configuration.
  29 box_step(B,F) :- box(B), initial_step(F).
  30 sokoban_step(S,F) :- sokoban(S), initial_step(F).
  31 
  32 % push(B,D,B1,S):
  33 % At actionstep S push box at location B in direction D (right, left, up, down)
  34 % until location B1.
  35 % The sokoban must be able to get to the location "before" B in order to push
  36 % the box, also there should not be any boxes between B and B1 (and also not
  37 % on B1 itself at step S.
  38 push(B,right,B1,S) v -push(B,right,B1,S) :- 
  39     reachable(L,S), right(L,B), box_step(B,S), pushable_right(B,B1,S), good_pushlocation(B1), actionstep(S).
  40 push(B,left,B1,S) v -push(B,left,B1,S) :-
  41     reachable(L,S), left(L,B), box_step(B,S), pushable_left(B,B1,S), good_pushlocation(B1), actionstep(S).
  42 push(B,up,B1,S) v -push(B,up,B1,S) :-
  43     reachable(L,S), top(L,B), box_step(B,S), pushable_top(B,B1,S), good_pushlocation(B1), actionstep(S).
  44 push(B,down,B1,S) v -push(B,down,B1,S) :-
  45     reachable(L,S), bottom(L,B), box_step(B,S), pushable_bottom(B,B1,S), good_pushlocation(B1), actionstep(S).
  46 
  47 % reachable(L,S):
  48 % Identifies locations L which are reachable by the sokoban at step S.
  49 reachable(L,S) :- sokoban_step(L,S).
  50 reachable(L,S) :- reachable(L1,S), adj(L1,L), not box_step(L,S).
  51 
  52 % pushable_right(B,D,S):
  53 % Box at B can be pushed right until D at step S.
  54 % Analogous for left, top, bottom.
  55 pushable_right(B,D,S) :- box_step(B,S), right(B,D), not box_step(D,S), actionstep(S).
  56 pushable_right(B,D,S) :- pushable_right(B,D1,S), right(D1,D), not box_step(D,S).
  57 pushable_left(B,D,S) :- box_step(B,S), left(B,D), not box_step(D,S), actionstep(S).
  58 pushable_left(B,D,S) :- pushable_left(B,D1,S), left(D1,D), not box_step(D,S).
  59 pushable_top(B,D,S) :- box_step(B,S), top(B,D), not box_step(D,S), actionstep(S).
  60 pushable_top(B,D,S) :- pushable_top(B,D1,S), top(D1,D), not box_step(D,S).
  61 pushable_bottom(B,D,S) :- box_step(B,S), bottom(B,D), not box_step(D,S), actionstep(S).
  62 pushable_bottom(B,D,S) :- pushable_bottom(B,D1,S), bottom(D1,D), not box_step(D,S).
  63 
  64 % The sokoban is at a new location after a push and no longer at its original
  65 % position.
  66 sokoban_step(L,S1) :- push(_,right,B1,S), next(S,S1), right(L,B1).
  67 sokoban_step(L,S1) :- push(_,left,B1,S), next(S,S1), left(L,B1).
  68 sokoban_step(L,S1) :- push(_,up,B1,S), next(S,S1), top(L,B1).
  69 sokoban_step(L,S1) :- push(_,down,B1,S), next(S,S1), bottom(L,B1).
  70 -sokoban_step(L,S1) :- push(_,_,_,S), next(S,S1), sokoban_step(L,S).
  71 
  72 % Also the box_step has moved after having been pushed.
  73 box_step(B,S1) :- push(_,_,B,S), next(S,S1).
  74 -box_step(B,S1) :- push(B,_,_,S), next(S,S1).
  75 
  76 % Inertia: Boxes and the sokoban usually remain where they are.
  77 box_step(LB,S1) :- box_step(LB,S), next(S,S1), not -box_step(LB,S1).
  78 sokoban_step(LS,S) :- sokoban_step(LS,S), next(S,S1), not -sokoban_step(LS,S1).
  79 
  80 % Don't push two different boxes in one step.
  81 :- push(B,_,_,S), push(B1,_,_,S), B != B1.
  82 % Don't push a box in different directions in one step.
  83 :- push(B,D,_,S), push(B,D1,_,S), D != D1.
  84 % Don't push a box onto different locations in one step.
  85 :- push(B,D,B1,S), push(B,D,B11,S), B1 != B11.
  86 
  87 % Avoid pushing boxes into dead ends. There should be a location to the left
  88 % and right or to top and bottom. Otherwise the box cannot be taken out again,
  89 % for instance from corners. Obviously if the location is a target, these
  90 % restrictions do not apply, as the box may remain there forever.
  91 good_pushlocation(L) :- right(L,_), left(L,_).
  92 good_pushlocation(L) :- top(L,_), bottom(L,_).
  93 good_pushlocation(L) :- solution(L).
  94 
  95 final_step(S) :- step(S), not no_final_step(S).
  96 no_final_step(S) :- next(S,S1).
  97 
  98 initial_step(S) :- step(S), not no_initial_step(S).
  99 no_initial_step(S) :- next(S1,S).
 100 
 101 push_happens(S) :- push(_,_,_,S).
 102 push_missing :- actionstep(S), not push_happens(S).
 103 :- push_missing.
 104 solution_notfound :- solution(L), final_step(S), not box_step(L,S).
 105 :- solution_notfound.