% http://www.cs.kuleuven.be/~dtai/events/ASP-competition/Benchmarks/WireRouting.shtml % by Neng-Fa Zhou, April 14, 2009, revised May 1, 2009 :-include(base). % use foreach/3 in base.pl solve(As):- get_largest_atom(As,pt(N)), get_largest_atom(As,wire(W)), a2_new(Grid,N,N), % a N*N array init_grid(Grid,N,As,W), post_block_terminal(As,Grid), constrain_neighbors(Grid,N), terminals_connectable(W,As,Grid), compute_dists(Grid,N), array_to_list(Grid,Points), sort(Points,SortedPoints), % sorted by distance to a closest terminal extract_variables(SortedPoints,Vars), labeling(Vars),!, output(Grid,N,W). solve(_):- format("UNSATISFIABLE~n"). % Up to two wires can go through a point if it is allowed; otherwise, % only one wire can go through it. init_grid(Grid,N,As,W):- foreach((I in 1..N, J in 1..N), [Cij,V1,V2,Dist], (a2_get(Grid,I,J,Cij), (member(allow(I,J),As)-> Cij=allowed2(Dist,V1,V2), %Dist -- shortest distance from a terminal [V1,V2] :: 0..W, ((V1#=0 #/\ V2#=0) #\/ V1 #\= V2); Cij=allowed1(Dist,V1), V1 :: 0..W))). extract_variables([],[]). extract_variables([allowed2(_,V1,V2)|Points],[V1,V2|Vars]):-!, extract_variables(Points,Vars). extract_variables([allowed1(_,V)|Points],[V|Vars]):-!, extract_variables(Points,Vars). % If a point is a terminal for wire W, only W can go through it. post_block_terminal([],_). post_block_terminal([block(I,J)|As],Grid):- a2_get(Grid,I,J,Cij), (Cij=allowed2(_,0,0);Cij=allowed1(_,0)),!, post_block_terminal(As,Grid). post_block_terminal([terminal(I,J,W)|As],Grid):-!, a2_get(Grid,I,J,Cij),Cij=allowed1(0,W), % Dist is 0 if the point is a terminal post_block_terminal(As,Grid). post_block_terminal([_|As],Grid):- post_block_terminal(As,Grid). % If a point is occupied by wire W, one of its neighbors must be occupied by W too. constrain_neighbors(Grid,N):- foreach((I in 1..N, J in 1..N), [Cij,Neibs], (a2_get(Grid,I,J,Cij), get_neighbors(Grid,N,I,J,Neibs), constrain_neighbors_aux(Cij,Neibs))). get_neighbors(Grid,N,I,J,Neibs):- Iu is I-1, % up (Iu>0->get_neighbor(Grid,Iu,J,[],Neibs1);Neibs1=[]), Jr is J+1, % right (Jr=get_neighbor(Grid,I,Jr,Neibs1,Neibs2);Neibs2=Neibs1), Id is I+1, % down (Id=get_neighbor(Grid,Id,J,Neibs2,Neibs3);Neibs3=Neibs2), Jl is J-1, % left (Jl>0->get_neighbor(Grid,I,Jl,Neibs3,Neibs);Neibs=Neibs3). get_neighbor(Grid,I,J,Neibs0,Neibs):- a2_get(Grid,I,J,Cij), (Cij=allowed2(_,V1,V2)->Neibs=[V1,V2|Neibs0]; Cij=allowed1(_,V1),Neibs=[V1|Neibs0]). %%%% constrain_neighbors_aux(allowed2(_,V1,V2),Neibs):-!, my_reify_count(V1,Neibs,Bs1), my_reify_count(V2,Neibs,Bs2), V1 #\= 0 #=> sum(Bs1)#=2, V2 #\= 0 #=> sum(Bs2)#=2. constrain_neighbors_aux(allowed1(_,V),_):-V==0,!. % this point is blocked constrain_neighbors_aux(allowed1(Dist,V),Neibs):- my_reify_count(V,Neibs,Bs), (Dist==0 -> % this point is a terminal sum(Bs) #= 1 ; V#\=0 #=> sum(Bs)#=2). % one in and one out my_reify_count(_,[],[]). my_reify_count(X,[Y|Ys],[B|Bs]):- B #<=> (X #= Y), my_reify_count(X,Ys,Bs). % for two terminals terminal(I1,J1,W) and terminal(I2,J2,W) % at least one point in each row in min(I1,I2)+1..max(I1,I2)-1, and % at least one point in each column in min(J1,J2)+1..max(J1,J2)-1 must % be occupied by W terminals_connectable(MaxW,As,Grid):- Grid^rows @= Rows, % built-ins in B-Prolog Grid^columns @= Cols, terminals_connectable(MaxW,As,Rows,Cols). terminals_connectable(0,_,_,_):-!. terminals_connectable(W,As,Rows,Cols):- member(terminal(I1,J1,W),As), member(terminal(I2,J2,W),As), (I1\==I2;J1\==J2),!, foreach(I in min(I1,I2)+1..max(I1,I2)-1, [Row,RowVars], (nth(I,Rows,Row), points_to_vars(Row,RowVars), count(W,RowVars,#>=,1))), foreach(J in min(J1,J2)+1..max(J1,J2)-1, [Col,ColVars], (nth(J,Cols,Col), points_to_vars(Col,ColVars), count(W,ColVars,#>=,1))), W1 is W-1, terminals_connectable(W1,As,Rows,Cols). points_to_vars([],[]). points_to_vars([allowed1(_,Var)|Points],[Var|Vars]):-!, points_to_vars(Points,Vars). points_to_vars([allowed2(_,Var1,Var2)|Points],[Var1,Var2|Vars]):-!, points_to_vars(Points,Vars). % the shortest distance of each point to the nearest terminal compute_dists(Grid,N):- foreach((_ in 1..N, I in 1..N, J in 1..N), [Cij,Dist], (a2_get(Grid,I,J,Cij), arg(1,Cij,Dist), (integer(Dist)->update_neighbors_dists(Grid,N,I,J,Dist);true))). update_neighbors_dists(Grid,N,I,J,Dist):- Dist1 is Dist+1, Iu is I-1, % up (Iu>0->update_neighbor_dist(Grid,Iu,J,Dist1);true), Jr is J+1, % right (Jr=update_neighbor_dist(Grid,I,Jr,Dist1);true), Id is I+1, % down (Id=update_neighbor_dist(Grid,Id,J,Dist1);true), Jl is J-1, % left (Jl>0->update_neighbor_dist(Grid,I,Jl,Dist1);true). update_neighbor_dist(Grid,I,J,Dist):- a2_get(Grid,I,J,Cij), arg(1,Cij,CurDist), (var(CurDist)->CurDist is Dist; CurDist>Dist->setarg(1,Cij,Dist);true). output(Grid,N,W):- foreach((K in 1..W, I in 1..N, J in 1..N), [Cij,V1,V2,Dist], % Dist must be declared local even through it is not used (a2_get(Grid,I,J,Cij), ((Cij=allowed2(Dist,V1,V2),(V1==K;V2==K);Cij=allowed1(Dist,V1),V1==K) -> format("path(~w,~w,~w). ",[I,J,K]);true))), nl. test:- solve([wire(1),wire(2),pt(1),pt(2),pt(3),pt(4),pt(5),terminal(3,1,1),terminal(2,1,2),terminal(2,5,1),terminal(3,5,2),block(1,5),block(4,5),allow(2,3),allow(5,4),allow(1,4),allow(3,3),allow(3,2)]). test:- solve([wire(1), wire(2), wire(3), wire(4), wire(5), pt(1), pt(2), pt(3), pt(4), pt(5), pt(6), pt(7), pt(8), pt(9), pt(10), terminal(7,1,1), terminal(1,1,2), terminal(8,1,3), terminal(6,1,4), terminal(2,1,5), terminal(10,10,1), terminal(6,10,2), terminal(2,10,3), terminal(4,10,4), terminal(5,10,5), block(5,6), block(8,9), block(6,4), block(8,6), block(4,6), allow(9,6), allow(3,10), allow(6,3), allow(7,6), allow(5,4), allow(4,3), allow(9,8), allow(8,7), allow(4,2), allow(10,9), allow(6,5), allow(5,3), allow(8,10), allow(6,2), allow(1,6), allow(3,5), allow(7,4), allow(8,4), allow(5,1), allow(3,9), allow(10,1), allow(10,4), allow(10,8), allow(7,8), allow(7,2)]).