%% 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)"

% Domain predicates

time(0..t).  pos(1..4).  entry(0..15). 

% Select where to move tile 0
{ move(T,X,Y) } :- time(T), T < t, pos(X;Y;X1;Y1), 
        in(T,X1,Y1,0), abs(X-X1) + abs(Y-Y1) == 1. 

% Only one move at a time allowed 
:- 2 { move(T,X,Y):pos(X):pos(Y) }, time(T), T< t. 

% For every time there must be a move
:- { move(T,X,Y):pos(X):pos(Y) } 0, time(T), T< t. 


% Effects of a move 
% Define the moving tile for each time T
moving(T,A) :- time(T), T < t, pos(X;Y), entry(A),
        move(T,X,Y), in(T,X,Y,A).

% The moving tile A is moved to the location of tile 0
in(T+1,X,Y,A) :- time(T), T < t, pos(X;Y), entry(A), 
        moving(T,A), in(T,X,Y,0). 

% Tile 0 is moved to the location (X,Y) when doing move(T,X,Y)
in(T+1,X,Y,0) :- time(T), T < t, pos(X;Y), move(T,X,Y).

% Frame axiom
in(T+1,X,Y,A) :- time(T), T < t, entry(A), pos(X;Y), A != 0, 
        in(T,X,Y,A), not moving(T,A).

% An example of a pruning rule
% Do not undo the last move
:- time(T), T < t-2, pos(X;Y), in(T,X,Y,0), in(T+2,X,Y,0).

% 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).

% Goal configuration must be satisfied
:- entry(A), pos(X), pos(Y), in(t,X,Y,A), not in_t(X,Y,A). 
:- entry(A), pos(X), pos(Y), not in(t,X,Y,A), in_t(X,Y,A). 

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