# Encoding lparse encoding

Name lparse encoding [Root]    Puzzles (51) Martin Gebser lparse encoding of 15 puzzle 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). % Select where to move tile 0 move(T,X,Y) :- time(T), maxtime(T1), T < T1, pos(X), pos(Y), pos(X1), pos(Y1), in(T,X1,Y1,0), abs(X-X1) + abs(Y-Y1) == 1, not someothermove(T,X,Y). someothermove(T,X,Y) :- time(T), maxtime(T1), T < T1, pos(X), pos(Y), pos(X1), movex(T,X1), X!=X1. someothermove(T,X,Y) :- time(T), maxtime(T1), T < T1, pos(X), pos(Y), pos(Y1), movey(T,Y1), Y!=Y1. movex(T,X) :- time(T), maxtime(T1), T < T1, pos(X), pos(Y), move(T,X,Y). movey(T,Y) :- time(T), maxtime(T1), T < T1, pos(X), pos(Y), move(T,X,Y). % Effects of a move % Define the moving tile for each time T moving(T,A) :- time(T), maxtime(T1), T < T1, pos(X), pos(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), maxtime(T1), T < T1, pos(X), pos(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), maxtime(T1), T < T1, pos(X), pos(Y), move(T,X,Y). % Frame axiom in(T+1,X,Y,A) :- time(T), maxtime(T1), T < T1, entry(A), pos(X), pos(Y), 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 :- entry(A), pos(X), pos(Y), maxtime(T), in(T,X,Y,A), not in_t(X,Y,A). :- entry(A), pos(X), pos(Y), maxtime(T), not in(T,X,Y,A), in_t(X,Y,A). % Initial configuration in(0,X,Y,A) :- in0(X,Y,A). %hide in(T,X,Y,A). %hide moving(T,A). %hide someothermove(_,_,_). %hide movex(_,_). %hide movey(_,_).