% 15-puzzle 
%
% The key predicates are move and in.
% Atom move(T,X,Y) has the meaning: at time T tile 0 is moved to
% location (X,Y) and 
% in(T,X,Y,A) is read as: at time T tile A is in location (X,Y).
% Initial configuration is given as facts in0(x,y,a). 

neighbor(X0,Y,X1,Y) :-  pos(X0), pos(Y), pos(X1), X1=X0+1.
neighbor(X0,Y,X1,Y) :-  pos(X0), pos(Y), pos(X1), X1=X0-1.
neighbor(X,Y0,X,Y1) :-  pos(X), pos(Y0), pos(Y1), Y1=Y0+1.
neighbor(X,Y0,X,Y1) :-  pos(X), pos(Y0), pos(Y1), Y1=Y0-1.

in(0,X,Y,A) :- in0(X,Y,A).

goal(T)   :- in(T,1,1,0),  in(T,1,2,1),  in(T,1,3,2),  in(T,1,4,3),
             in(T,2,1,4),  in(T,2,2,5),  in(T,2,3,6),  in(T,2,4,7),
             in(T,3,1,8),  in(T,3,2,9),  in(T,3,3,10), in(T,3,4,11),
             in(T,4,1,12), in(T,4,2,13), in(T,4,3,14), in(T,4,4,15), time(T).

goal(T1) :- goal(T), time(T), maxtime(M), T < M, T1=T+1.
:- not goal(M), maxtime(M).

move(T,1,1) v move(T,1,2) v move(T,1,3) v move(T,1,4) 
v move(T,2,1) v move(T,2,2) v move(T,2,3) v move(T,2,4) 
v move(T,3,1) v move(T,3,2) v move(T,3,3) v move(T,3,4) 
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).

:- move(T,X,Y), in(T,XX,YY,0), not neighbor(X,Y,XX,YY).

in(T1,X,Y,0) :- move(T,X,Y), T1=T+1.
in(T1,X,Y,A) :- in(T,X,Y,0), in(T,XX,YY,A), move(T,XX,YY), neighbor(X,Y,XX,YY), 
                 entry(A), A > 0, T1=T+1.
in(T1,X,Y,A) :- in(T,X,Y,A), not move(T,X,Y), pos(X), pos(Y),
                 entry(A), A > 0, time(T), maxtime(M), T < M, not goal(T), T1=T+1.

% Goal configuration
%  0  1  2  3
%  4  5  6  7
%  8  9 10 11
% 12 13 14 15

in_t(1,1,0).   in_t(1,2,1).   in_t(1,3,2).   in_t(1,4,3).
in_t(2,1,4).   in_t(2,2,5).   in_t(2,3,6).   in_t(2,4,7).
in_t(3,1,8).   in_t(3,2,9).   in_t(3,3,10).  in_t(3,4,11).
in_t(4,1,12).  in_t(4,2,13).  in_t(4,3,14).  in_t(4,4,15).