Please wait ...

Benchmark(s) have been added to cart.

Tag has been added.

• Login
• Links
• FAQs
• Contact

Navigation

• Instance
  • Show Instances
• Problem
  • Show Problems
• Show Tags
• Search
• Cart

Encoding 15-puzzle_optimization.gringo

Name	15-puzzle_optimization.gringo
Class Tree	[Root]    Unclassified (114)    15-PuzzleCompetition (5)
Submitter	Martin Gebser
Author	Martin Gebser and Roland Kaminski
Description	A Gringo encoding of the 15-Puzzle problem. Moves of tiles are subject to minimization.
Created	2009-03-09 20:08
Modified	2009-03-09 20:10
Languages	Gringo 2.0.2
Language Features	Cardinality constraints Optimization Choice rules
Compatible Instance Classes	15-PuzzleCompetition
Input Predicates	entry/1 in0/3 maxtime/1 pos/1 time/1
Output Predicates	move/3
Encoding Parameter
Standalone	No
Tags	ASP Contest 09 (Martin Gebser)
Attributes
Content	% 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). #minimize { move(T,X,Y) : time(T) : pos(X) : pos(Y) }. #hide. #show move(T,X,Y).