Encoding 15-puzzle_decision.gringo

Name 15-puzzle_decision.gringo [Root]    Unclassified (114) Martin Gebser Martin Gebser and Roland Kaminski A Gringo encoding of the 15-Puzzle problem. 2009-03-09 19:01 2009-03-09 20:04 15-PuzzleCompetition entry/1in0/3maxtime/1pos/1time/1 move/3 No ASP Contest 09 (Martin Gebser) % 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(X,Y,X+1,Y) :- pos(X), pos(Y), pos(X+1). neighbor(X,Y,X-1,Y) :- pos(X), pos(Y), pos(X-1). neighbor(X,Y,X,Y+1) :- pos(X), pos(Y), pos(Y+1). neighbor(X,Y,X,Y-1) :- pos(X), pos(Y), pos(Y-1). in(0,X,Y,A) :- in0(X,Y,A). goal(T) :- in(T,X,Y,A) : in_t(X,Y,A), time(T). goal(T+1) :- goal(T), time(T), maxtime(M), T < M. :- not goal(M), maxtime(M). 1 { move(T,X,Y) : pos(X) : pos(Y) } 1 :- time(T), maxtime(M), T < M, not goal(T). :- move(T,X,Y), { in(T,XX,YY,0) : neighbor(XX,YY,X,Y) } 0. in(T+1,X,Y,0) :- move(T,X,Y). in(T+1,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. in(T+1,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). % 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). #hide. #show move(T,X,Y).