1 % 15-puzzle 
   2 %
   3 % The key predicates are move and in.
   4 % Atom move(T,X,Y) has the meaning: at time T tile 0 is moved to
   5 % location (X,Y) and 
   6 % in(T,X,Y,A) is read as: at time T tile A is in location (X,Y).
   7 % Initial configuration is given as facts in0(x,y,a). 
   8 
   9 neighbor(X0,Y,X1,Y) :-  pos(X0), pos(Y), pos(X1), X1=X0+1.
  10 neighbor(X0,Y,X1,Y) :-  pos(X0), pos(Y), pos(X1), X1=X0-1.
  11 neighbor(X,Y0,X,Y1) :-  pos(X), pos(Y0), pos(Y1), Y1=Y0+1.
  12 neighbor(X,Y0,X,Y1) :-  pos(X), pos(Y0), pos(Y1), Y1=Y0-1.
  13 
  14 in(0,X,Y,A) :- in0(X,Y,A).
  15 
  16 goal(T)   :- in(T,1,1,0),  in(T,1,2,1),  in(T,1,3,2),  in(T,1,4,3),
  17              in(T,2,1,4),  in(T,2,2,5),  in(T,2,3,6),  in(T,2,4,7),
  18              in(T,3,1,8),  in(T,3,2,9),  in(T,3,3,10), in(T,3,4,11),
  19              in(T,4,1,12), in(T,4,2,13), in(T,4,3,14), in(T,4,4,15), time(T).
  20 
  21 goal(T1) :- goal(T), time(T), maxtime(M), T < M, T1=T+1.
  22 :- not goal(M), maxtime(M).
  23 
  24 move(T,1,1) v move(T,1,2) v move(T,1,3) v move(T,1,4) 
  25 v move(T,2,1) v move(T,2,2) v move(T,2,3) v move(T,2,4) 
  26 v move(T,3,1) v move(T,3,2) v move(T,3,3) v move(T,3,4) 
  27 v move(T,4,1) v move(T,4,2) v move(T,4,3) v move(T,4,4) :- time(T), maxtime(M), T < M, not goal(T).
  28 
  29 :- move(T,X,Y), in(T,XX,YY,0), not neighbor(X,Y,XX,YY).
  30 
  31 in(T1,X,Y,0) :- move(T,X,Y), T1=T+1.
  32 in(T1,X,Y,A) :- in(T,X,Y,0), in(T,XX,YY,A), move(T,XX,YY), neighbor(X,Y,XX,YY), 
  33                  entry(A), A > 0, T1=T+1.
  34 in(T1,X,Y,A) :- in(T,X,Y,A), not move(T,X,Y), pos(X), pos(Y),
  35                  entry(A), A > 0, time(T), maxtime(M), T < M, not goal(T), T1=T+1.
  36 
  37 % Goal configuration
  38 %  0  1  2  3
  39 %  4  5  6  7
  40 %  8  9 10 11
  41 % 12 13 14 15
  42 
  43 in_t(1,1,0).   in_t(1,2,1).   in_t(1,3,2).   in_t(1,4,3).
  44 in_t(2,1,4).   in_t(2,2,5).   in_t(2,3,6).   in_t(2,4,7).
  45 in_t(3,1,8).   in_t(3,2,9).   in_t(3,3,10).  in_t(3,4,11).
  46 in_t(4,1,12).  in_t(4,2,13).  in_t(4,3,14).  in_t(4,4,15).