1 dir(e). dir(w). dir(n). dir(s).
   2 inverse(e,w). inverse(w,e).
   3 inverse(n,s). inverse(s,n).
   4 
   5 row(X) :- field(X,Y).
   6 col(Y) :- field(X,Y).
   7 
   8 num_rows(X) :- row(X), not row(XX), XX = X+1.
   9 num_cols(Y) :- col(Y), not col(YY), YY = Y+1.
  10 
  11 goal(X,Y,0)   :- goal_on(X,Y).
  12 reach(X,Y,0)  :- init_on(X,Y).
  13 conn(X,Y,D,0) :- connect(X,Y,D).
  14 
  15 step(S) :- max_steps(S),     0 < S.
  16 step(T) :- step(S), T = S-1, 1 < S.
  17 
  18 %%  Direct neighbors
  19 
  20 dneighbor(n,X,Y,XX,Y) :- field(X,Y), field(XX,Y), XX = X+1.
  21 dneighbor(s,X,Y,XX,Y) :- field(X,Y), field(XX,Y), XX = X-1.
  22 dneighbor(e,X,Y,X,YY) :- field(X,Y), field(X,YY), YY = Y+1.
  23 dneighbor(w,X,Y,X,YY) :- field(X,Y), field(X,YY), YY = Y-1.
  24 
  25 %%  All neighboring fields
  26 
  27 neighbor(D,X,Y,XX,YY) :- dneighbor(D,X,Y,XX,YY).
  28 neighbor(n,X,Y, 1, Y) :- field(X,Y), num_rows(X).
  29 neighbor(s,1,Y, X, Y) :- field(X,Y), num_rows(X).
  30 neighbor(e,X,Y, X, 1) :- field(X,Y), num_cols(Y).
  31 neighbor(w,X,1, X, Y) :- field(X,Y), num_cols(Y).
  32 
  33 %%  Select a row or column to push
  34 
  35 neg_goal(T) :- goal(X,Y,T), not reach(X,Y,T).
  36 
  37 rrpush(T)   :- step(T), neg_goal(S), S = T-1, not ccpush(T).
  38 ccpush(T)   :- step(T), neg_goal(S), S = T-1, not rrpush(T).
  39 
  40 orpush(X,T) :- row(X), row(XX), rpush(XX,T), X != XX.
  41 ocpush(Y,T) :- col(Y), col(YY), cpush(YY,T), Y != YY.
  42 
  43 rpush(X,T)  :- row(X), rrpush(T), not orpush(X,T).
  44 cpush(Y,T)  :- col(Y), ccpush(T), not ocpush(Y,T).
  45 
  46 push(X,e,T) :- rpush(X,T), not push(X,w,T).
  47 push(X,w,T) :- rpush(X,T), not push(X,e,T).
  48 push(Y,n,T) :- cpush(Y,T), not push(Y,s,T).
  49 push(Y,s,T) :- cpush(Y,T), not push(Y,n,T).
  50 
  51 %%  Determine new position of a (pushed) field
  52 
  53 shift(XX,YY,X,Y,T) :- neighbor(e,XX,YY,X,Y), push(XX,e,T), step(T).
  54 shift(XX,YY,X,Y,T) :- neighbor(w,XX,YY,X,Y), push(XX,w,T), step(T).
  55 shift(XX,YY,X,Y,T) :- neighbor(n,XX,YY,X,Y), push(YY,n,T), step(T).
  56 shift(XX,YY,X,Y,T) :- neighbor(s,XX,YY,X,Y), push(YY,s,T), step(T).
  57 shift( X, Y,X,Y,T) :- field(X,Y), not push(X,e,T), not push(X,w,T), not push(Y,n,T), not push(Y,s,T), step(T).
  58 
  59 %%  Move connections around
  60 
  61 conn(X,Y,D,T) :- conn(XX,YY,D,S), S = T-1, dir(D), shift(XX,YY,X,Y,T), step(T).
  62 
  63 %%  Location of goal after pushing
  64 
  65 goal(X,Y,T) :- goal(XX,YY,S), S = T-1, shift(XX,YY,X,Y,T), step(T).
  66 
  67 %%  Locations reachable from new position
  68 
  69 reach(X,Y,T) :- reach(XX,YY,S), S = T-1, shift(XX,YY,X,Y,T), step(T).
  70 reach(X,Y,T) :- reach(XX,YY,T), dneighbor(D,XX,YY,X,Y), conn(XX,YY,D,T), conn(X,Y,E,T), inverse(D,E), step(T).
  71 
  72 %%  Goal must be reached
  73 
  74 :- neg_goal(S), max_steps(S).
  75 
  76 %% Project output
  77 
  78 % #hide.
  79 % #show push(Z,D,T).