%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Sam Lloyd's puzzle with 16 cells and 15 tiles
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Coded by DFP, August 2010
%%% as required for the by ASP competition 2009
%%% http://dtai.cs.kuleuven.be/events/ASP-competition/Benchmarks/15Puzzle.shtml
%%% by Lengning Liu, Miroslaw Truszczynski, and Martin Gebser
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 1   2   3   4   (Y)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 1 % 0   1   2   3
% 2 % 4   5   6   7
% 3 % 8   9  10  11
% 4 %12  13  14  15
%(X)%%%%%%%%%%%%%%%%%%

coord(A) :-  interval(A,1,4). %%% pos(A).   %%%
tile(N)  :- interval(N,0,15). %%% entry(N). %%%

%%% Encoding followiung ideas of Gebser's encoding in ASP.
%%% tile 0 means empty slot.
%%% Moves are moves of the empty slot
%%% in0(x,y,n) means that val n is at entry (X,Y) at the beginning

%%%% Topology of the chessboard

near(X1,Y,X2,Y,s) :- coord(X1),coord(X2),coord(Y), X2 is X1 + 1.
near(X,Y1,X,Y2,e) :- coord(X),coord(Y1),coord(Y2), Y1 mod 4 \= 3, Y2 is Y1 + 1.
near(X1,Y,X2,Y,n) :- coord(X1),coord(X2),coord(Y), X1 > X2, near(X2,Y,X1,Y,s).
near(X,Y1,X,Y2,w) :- coord(X),coord(Y1),coord(Y2), Y1 > Y2, near(X,Y2,X,Y1,e).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Action Theory
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

fluent(at(N,X,Y)) :- tile(N),coord(X),coord(Y).

action(move(X,Y)) :- coord(X), coord(Y).

%%%%%%%%

executable(move(X,Y), [at(0,X1,Y1)]) :-
      action(move(X,Y)),near(X,Y,X1,Y1,_).

%%%%%%%%% all encoded in static...

causes(move(X,Y), at(0,X,Y),[]) :-
      action(move(X,Y)).
causes(move(X,Y), at(N,X1,Y1),[at(N,X,Y),at(0,X1,Y1)]) :-
      action(move(X,Y)), tile(N), N > 0, near(X1,Y1,X,Y,_).

%%% The following two dynamic laws can be replaced by the
%%% static laws below.

causes(move(X,Y),neg(at(0,X1,Y1)),[]) :-
      action(move(X,Y)), coord(X),coord(Y),coord(X1),coord(Y1),diffpair(X,Y,X1,Y1).

causes(move(X,Y), neg(at(N,X,Y)),[]) :-
      action(move(X,Y)), tile(N), N > 0.

%%%%% Just in case...
%caused([at(N,X,Y)],neg(at(M,X,Y)))   :- coord(X),coord(Y),tile(M),tile(N),diff(M,N).
%caused([at(N,X,Y)],neg(at(N,X1,Y1))) :- coord(X),coord(Y),coord(X1),coord(Y1),tile(N),
%    diffpair(X,Y,X1,Y1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Expected Goal

goal(at(N,X,Y)) :- coord(X),coord(Y),tile(N),N =:= Y-1+4*(X-1).

%%%%% Initial state, retrieved from ASP competition input

initially(at(N,X,Y))      :- in0(X,Y,N).
initially(neg(at(N,X,Y))) :- tile(N),coord(X),coord(Y),\+ in0(X,Y,N).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Instance  10 moves                            %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Instance  20 moves                            %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Instance  .init1 -35 moves                    %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

%%%%%%%%%%%%