# Encoding 15-puzzle.dlv

Name 15-puzzle.dlv [Root]    Puzzles (51) Martin Gebser 2009-03-30 13:03 2008-11-29 00:10 No % 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). #maxint=10000. okmove(X0,Y,X1,Y) :- pos(X0), pos(X1), pos(Y), #succ(X0,X1). okmove(X0,Y,X1,Y) :- pos(X0), pos(X1), pos(Y), #succ(X1,X0). okmove(X,Y0,X,Y1) :- pos(X), pos(Y0), pos(Y1), #succ(Y0,Y1). okmove(X,Y0,X,Y1) :- pos(X), pos(Y0), pos(Y1), #succ(Y1,Y0). movetime(T) :- time(T), maxtime(T1), T < T1. % Select where to move tile move(T,X,Y) v nmove(T,X,Y) :- movetime(T), okmove(_,_,X,Y). moved(T) :- move(T,X,Y). :- not moved(T), movetime(T). :- move(T,X,Y), move(T,X0,Y0), X < X0. :- move(T,X,Y), move(T,X0,Y0), Y < Y0. :- movetime(T), not okmove(X0,Y0,X1,Y1), in(T,X0,Y0,0), move(T,X1,Y1). % No immediate moving back :- time(T), time(T1), in(T,X,Y,0), move(T1,X,Y), #succ(T,T1). % Effects of a move % Define the moving tile for each time T moving(T,A) :- move(T,X,Y), in(T,X,Y,A). % The moving tile A is moved to the location of tile 0 in(T1,X,Y,A) :- movetime(T), #succ(T,T1), moving(T,A), in(T,X,Y,0). % Tile 0 is moved to the location (X,Y) when doing move(T,X,Y) in(T1,X,Y,0) :- movetime(T), #succ(T,T1), move(T,X,Y). % Frame axiom in(T1,X,Y,A) :- movetime(T), #succ(T,T1), A != 0, in(T,X,Y,A), not moving(T,A). % 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 :- maxtime(T), in(T,X,Y,A), not in_t(X,Y,A). :- maxtime(T), not in(T,X,Y,A), in_t(X,Y,A). % Initial configuration in(0,X,Y,A) :- in0(X,Y,A).