# Encoding wire-routing_chk.lp

Name wire-routing_chk.lp [Root]    Miscellaneous (45)    ASP Contest 09 (45) Martin Gebser Martin Gebser and Roland Kaminski 2009-03-13 21:35 2009-05-25 15:21 No #hide. #show path/3. %#show edge/5. :- path(X,Y,W), not wire(W). :- path(X,Y,W), not pt(X). :- path(X,Y,W), not pt(Y). :- path(X,Y,W), block(X,Y). :- 2 { path(X,Y,W) : wire(W) }, pt(X;Y), not allow(X,Y). :- 3 { path(X,Y,W) : wire(W) }, allow(X,Y). % :- path(X1,Y1,W1;W2), path(X2,Y2,W1;W2), W1 < W2, neighbor(X1,Y1,X2,Y2). % neighboring grid points neighbor(X,Y,X+1,Y) :- pt(X;Y;X+1), not block(X,Y), not block(X+1,Y). neighbor(X,Y,X-1,Y) :- pt(X;Y;X-1), not block(X,Y), not block(X-1,Y). neighbor(X,Y,X,Y+1) :- pt(X;Y;Y+1), not block(X,Y), not block(X,Y+1). neighbor(X,Y,X,Y-1) :- pt(X;Y;Y-1), not block(X,Y), not block(X,Y-1). { edge(X1,Y1,X2,Y2,W) } :- path(X1,Y1,W), path(X2,Y2,W), neighbor(X1,Y1,X2,Y2). edge(X1,Y1,X2,Y2,W) :- path(X1,Y1,W), path(X2,Y2,W), neighbor(X1,Y1,X2,Y2), { path(X3,Y3,W) : neighbor(X1,Y1,X3,Y3) } 1. edge(X1,Y1,X2,Y2,W) :- path(X1,Y1,W), path(X2,Y2,W), neighbor(X1,Y1,X2,Y2), not wire(WW) : path(X1,Y1,WW) : path(X2,Y2,WW) : WW != W. edge(X2,Y2,X1,Y1,W) :- path(X1,Y1,W), path(X2,Y2,W), edge(X1,Y1,X2,Y2,W). :- edge(X1,Y1,X2,Y2,W;WW), W < WW. % get ending point t2(X1,Y1,W) :- terminal(X1,Y1,W), terminal(X1,Y2,W), Y1 > Y2. t2(X1,Y1,W) :- terminal(X1,Y1,W), terminal(X2,Y2,W), X1 > X2. % get starting point t1(X,Y,W) :- terminal(X,Y,W), not t2(X,Y,W). % reachable grid points reach(X,Y,W) :- t1(X,Y,W), path(X,Y,W). reach(X,Y,W) :- reach(XX,YY,W), path(X,Y,W), edge(XX,YY,X,Y,W). :- path(X,Y,W), not reach(X,Y,W). % terminal points must be reached :- terminal(X,Y,W), not reach(X,Y,W).