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 labyrinth_step_decision.gringo

Name	labyrinth_step_decision.gringo
Class Tree	[Root]    Puzzles (51)    Grid (17)    Labyrinth (4)    Single Cell Move (1)
Submitter	Martin Gebser
Author	Martin Gebser
Description	One time step consists of shifting one row or column of the labyrinth and a move from the current to a neighboring field. The latter do not belong to the projected output, viz., instances of "push/3."
Created	2009-01-16 15:18
Modified	2009-03-09 16:36
Languages	Gringo 2.0.2
Language Features	Cardinality constraints Choice rules Weight constraints
Compatible Instance Classes	Random Group M1
Input Predicates	connect/2 field/1 goal_on/1 init_at/3 init_on/1 steps/1
Output Predicates	push/3
Encoding Parameter
Standalone	No
Tags
Attributes
Content	%% Domains dir(e;w;n;s). inverse(e,w). inverse(w,e). inverse(n,s). inverse(s,n). step(1..S) :- steps(S). num_rows(M) :- M = max[init_at(F,X,Y) : init_at(F,X,Y) = X]. num_cols(N) :- N = max[init_at(F,X,Y) : init_at(F,X,Y) = Y]. field(1..M,1..N) :- num_rows(M), num_cols(N). %% All neighboring fields in horizontal direction D neighbor(e,X,Y,X,Y+1) :- field(X,Y;(Y+1)). neighbor(e,X,Y,X, 1) :- field(X,Y), num_cols(Y). neighbor(w,X,Y,X,Y-1) :- field(X,Y;(Y-1)). neighbor(w,X,1,X, Y) :- field(X,Y), num_cols(Y). %% All neighboring fields in vertical direction D neighbor(n,X,Y,X+1,Y) :- field(X;(X+1),Y). neighbor(n,X,Y,1, Y) :- field(X,Y), num_rows(X). neighbor(s,X,Y,X-1,Y) :- field(X;(X-1),Y). neighbor(s,1,Y,X, Y) :- field(X,Y), num_rows(X). %% Initial state goal(X,Y,0) :- init_at(F,X,Y), goal_on(F). connect(X,Y,D,0) :- init_at(F,X,Y), connect(F,D). on(X,Y,0) :- init_at(F,X,Y), init_on(F). %% Moves %% Select a row or column to push 1 { push(X,e;w,S) : X=1..M, push(Y,n;s,S) : Y=1..N } 1 :- num_rows(M), num_cols(N), step(S). %% Determine new position of a (pushed) field shift(XX,YY,X,Y,S) :- neighbor(e,XX,YY,X,Y), push(XX,e,S), step(S). shift(XX,YY,X,Y,S) :- neighbor(w,XX,YY,X,Y), push(XX,w,S), step(S). shift(XX,YY,X,Y,S) :- neighbor(n,XX,YY,X,Y), push(YY,n,S), step(S). shift(XX,YY,X,Y,S) :- neighbor(s,XX,YY,X,Y), push(YY,s,S), step(S). shift(X, Y, X,Y,S) :- field(X,Y), not push(X,e;w,S), not push(Y,n;s,S), step(S). %% Move connections around connect(X,Y,D,S) :- connect(XX,YY,D,S-1), dir(D), shift(XX,YY,X,Y,S), step(S). %% Location of goal after pushing goal(X,Y,S) :- goal(XX,YY,S-1), shift(XX,YY,X,Y,S), step(S). %% Make some move 1 { move(D,S) : dir(D) } 1 :- step(S). %% Update position loc(XX,YY,S) :- on(XXX,YYY,S-1), shift(XXX,YYY,XX,YY,S), step(S). on(X,Y,S) :- loc(XX,YY,S), move(D,S), neighbor(D,XX,YY,X,Y), connect(XX,YY,D,S), connect(X,Y,E,S), inverse(D,E), step(S). %% Goal %% Goal must be reachable in steps :- goal(X,Y,S), not on(X,Y,S), steps(S). %% Output PROJECTION to pushes #hide. #show push/3.