% http://www.cs.kuleuven.be/~dtai/events/ASP-competition/Benchmarks/GenShitherlink.shtml
% by Neng-Fa Zhou, April 17, 2009
solve(As):-
    new_hashtable(EdgesTable),
    get_inputs(As,AList,Cells,Bs,EdgesTable),
    degree(AList,EdgesTable),
    clue(Cells,EdgesTable),
    labeling([ffc],Bs),
    check_sub_circle(AList),!,
    output(As,EdgesTable).
solve(_):-
    format("UNSATISFIABLE~n").

get_inputs([],AList,Cells,[],_):-
     close_tails(AList),
     close_tails(Cells).
get_inputs([edge(I,J)|As],AList,Cells,[B|Bs],EdgesTable):-
    member(node(I,ReachedI,SCCI,NeighborsI),AList), member(edge(I,J),NeighborsI),
    member(node(J,ReachedJ,SCCJ,NeighborsJ),AList), member(edge(J,I),NeighborsJ),!,
    [B,ReachedI,ReachedJ] :: 0..1,   % (I,J) is in the subgraph iff B=1
    B#=1 #=> (ReachedI#=1 #/\ ReachedJ#=1 #/\ SCCI#=SCCJ),
    hashtable_put(EdgesTable,edge(I,J),B),
    hashtable_put(EdgesTable,edge(J,I),B),
    get_inputs(As,AList,Cells,Bs,EdgesTable).
get_inputs([cell_contains(Id,I,J)|As],AList,Cells,Bs,EdgesTable):-
    member(cell(Id,_,Edges),Cells),
    member(edge(I,J),Edges),!,
    get_inputs(As,AList,Cells,Bs,EdgesTable).
get_inputs([clue(Id,Clue)|As],AList,Cells,Bs,EdgesTable):-
    member(cell(Id,Clue,_),Cells),!,
    get_inputs(As,AList,Cells,Bs,EdgesTable).

close_tails(AList):-var(AList),!,AList=[].
close_tails([node(_,_,_,L)|AList]):-
    closetail(L),
    close_tails(AList).
close_tails([cell(_,_,L)|AList]):-
    closetail(L),
    close_tails(AList).

% if a node is connected, it's degree must be 2
degree([],_).
degree([node(_,Reached,_,Edges)|AList],EdgesTable):-
    retrieve_labels(Edges,EdgesTable,Labels),
    Reached#=1 #=> sum(Labels) #= 2,
    degree(AList,EdgesTable).

retrieve_labels([],_,[]).
retrieve_labels([Edge|Edges],EdgesTable,[B|Bs]):-
    hashtable_get(EdgesTable,Edge,B),
    retrieve_labels(Edges,EdgesTable,Bs).

% |E|=f(E) 
clue([],_).
clue([cell(_,Clue,Edges)|Cells],EdgesTable):-
    retrieve_labels(Edges,EdgesTable,Bs),
    sum(Bs) #= Clue,
    clue(Cells,EdgesTable).

% no sub-circle is allowed
check_sub_circle([]).
check_sub_circle([node(_,Reached,SCC,_)|Nodes]):-Reached==1,!,
    check_sub_circle(Nodes,SCC).
check_sub_circle([_|Nodes]):-
    check_sub_circle(Nodes).

check_sub_circle([],_).
check_sub_circle([node(_,Reached,SCC,_)|Nodes],SCC0):-Reached==1,!,
    SCC==SCC0,
    check_sub_circle(Nodes,SCC0).
check_sub_circle([_|Nodes],SCC0):-
    check_sub_circle(Nodes,SCC0).

output([],_):-nl.
output([edge(I,J)|As],EdgesTable):-
    hashtable_get(EdgesTable,edge(I,J),B),
    B==1,!,
    format("link(~w,~w). ",[I,J]),
    output(As,EdgesTable).
output([_|As],EdgesTable):-
    output(As,EdgesTable).

test:-
   solve([edge(0,1),
          edge(1,2),
          edge(2,3),
          edge(3,0),
          edge(0,5),
          edge(5,6),
          edge(6,1),
          edge(8,3),
          edge(2,11),
          edge(11,8),
          edge(8,13),
          edge(13,0),
          edge(11,17),
          edge(17,18),
          edge(18,19),
          edge(19,11),
          edge(2,22),
          edge(22,17),
          edge(11,26),
          edge(26,27),
          edge(27,8),
          edge(28,27),
          edge(26,31),
          edge(31,28),
          edge(28,33),
          edge(33,8),
          edge(36,31),
          edge(26,39),
          edge(39,36),
          edge(36,41),
          edge(41,28),
          edge(39,19),
          edge(18,47),
          edge(47,39),
          edge(39,54),
          edge(54,55),
          edge(55,36),
          edge(56,55),
          edge(54,59),
          edge(59,56),
          edge(56,61),
          edge(61,36),
          edge(64,59),
          edge(54,67),
          edge(67,64),
          edge(64,69),
          edge(69,56),
          edge(67,47),
          edge(18,75),
          edge(75,67),
          edge(67,82),
          edge(82,83),
          edge(83,64),
          edge(84,83),
          edge(82,87),
          edge(87,84),
          edge(84,89),
          edge(89,64),
          edge(92,87),
          edge(82,95),
          edge(95,92),
          edge(92,97),
          edge(97,84),
          edge(95,75),
          edge(18,103),
          edge(103,95),
          edge(95,110),
          edge(110,111),
          edge(111,92),
          edge(112,111),
          edge(110,115),
          edge(115,112),
          edge(112,117),
          edge(117,92),
          edge(6,115),
          edge(110,22),
          edge(22,6),
          edge(6,125),
          edge(125,112),
          edge(22,103),
          clue(c0,1),
          clue(c2,0),
          clue(c4,3),
          clue(c5,2),
          clue(c7,2),
          clue(c10,1),
          clue(c11,2),
          clue(c13,3),
          clue(c14,1),
          clue(c15,3),
          clue(c19,1),
          clue(c20,1),
          clue(c24,1),
          clue(c25,1),
          clue(c27,1),
          clue(c28,2),
          clue(c31,1),
          clue(c32,1),
          cell_contains(c0,0,1),
          cell_contains(c0,1,2),
          cell_contains(c0,2,3),
          cell_contains(c0,3,0),
          cell_contains(c1,0,5),
          cell_contains(c1,5,6),
          cell_contains(c1,6,1),
          cell_contains(c1,0,1),
          cell_contains(c2,8,3),
          cell_contains(c2,2,3),
          cell_contains(c2,2,11),
          cell_contains(c2,11,8),
          cell_contains(c3,8,13),
          cell_contains(c3,13,0),
          cell_contains(c3,3,0),
          cell_contains(c3,8,3),
          cell_contains(c4,11,17),
          cell_contains(c4,17,18),
          cell_contains(c4,18,19),
          cell_contains(c4,19,11),
          cell_contains(c5,2,11),
          cell_contains(c5,2,22),
          cell_contains(c5,22,17),
          cell_contains(c5,11,17),
          cell_contains(c6,11,8),
          cell_contains(c6,11,26),
          cell_contains(c6,26,27),
          cell_contains(c6,27,8),
          cell_contains(c7,28,27),
          cell_contains(c7,26,27),
          cell_contains(c7,26,31),
          cell_contains(c7,31,28),
          cell_contains(c8,28,33),
          cell_contains(c8,33,8),
          cell_contains(c8,27,8),
          cell_contains(c8,28,27),
          cell_contains(c9,36,31),
          cell_contains(c9,26,31),
          cell_contains(c9,26,39),
          cell_contains(c9,39,36),
          cell_contains(c10,36,41),
          cell_contains(c10,41,28),
          cell_contains(c10,31,28),
          cell_contains(c10,36,31),
          cell_contains(c11,39,19),
          cell_contains(c11,18,19),
          cell_contains(c11,18,47),
          cell_contains(c11,47,39),
          cell_contains(c12,26,39),
          cell_contains(c12,11,26),
          cell_contains(c12,19,11),
          cell_contains(c12,39,19),
          cell_contains(c13,39,36),
          cell_contains(c13,39,54),
          cell_contains(c13,54,55),
          cell_contains(c13,55,36),
          cell_contains(c14,56,55),
          cell_contains(c14,54,55),
          cell_contains(c14,54,59),
          cell_contains(c14,59,56),
          cell_contains(c15,56,61),
          cell_contains(c15,61,36),
          cell_contains(c15,55,36),
          cell_contains(c15,56,55),
          cell_contains(c16,64,59),
          cell_contains(c16,54,59),
          cell_contains(c16,54,67),
          cell_contains(c16,67,64),
          cell_contains(c17,64,69),
          cell_contains(c17,69,56),
          cell_contains(c17,59,56),
          cell_contains(c17,64,59),
          cell_contains(c18,67,47),
          cell_contains(c18,18,47),
          cell_contains(c18,18,75),
          cell_contains(c18,75,67),
          cell_contains(c19,54,67),
          cell_contains(c19,39,54),
          cell_contains(c19,47,39),
          cell_contains(c19,67,47),
          cell_contains(c20,67,64),
          cell_contains(c20,67,82),
          cell_contains(c20,82,83),
          cell_contains(c20,83,64),
          cell_contains(c21,84,83),
          cell_contains(c21,82,83),
          cell_contains(c21,82,87),
          cell_contains(c21,87,84),
          cell_contains(c22,84,89),
          cell_contains(c22,89,64),
          cell_contains(c22,83,64),
          cell_contains(c22,84,83),
          cell_contains(c23,92,87),
          cell_contains(c23,82,87),
          cell_contains(c23,82,95),
          cell_contains(c23,95,92),
          cell_contains(c24,92,97),
          cell_contains(c24,97,84),
          cell_contains(c24,87,84),
          cell_contains(c24,92,87),
          cell_contains(c25,95,75),
          cell_contains(c25,18,75),
          cell_contains(c25,18,103),
          cell_contains(c25,103,95),
          cell_contains(c26,82,95),
          cell_contains(c26,67,82),
          cell_contains(c26,75,67),
          cell_contains(c26,95,75),
          cell_contains(c27,95,92),
          cell_contains(c27,95,110),
          cell_contains(c27,110,111),
          cell_contains(c27,111,92),
          cell_contains(c28,112,111),
          cell_contains(c28,110,111),
          cell_contains(c28,110,115),
          cell_contains(c28,115,112),
          cell_contains(c29,112,117),
          cell_contains(c29,117,92),
          cell_contains(c29,111,92),
          cell_contains(c29,112,111),
          cell_contains(c30,6,115),
          cell_contains(c30,110,115),
          cell_contains(c30,110,22),
          cell_contains(c30,22,6),
          cell_contains(c31,6,125),
          cell_contains(c31,125,112),
          cell_contains(c31,115,112),
          cell_contains(c31,6,115),
          cell_contains(c32,22,103),
          cell_contains(c32,18,103),
          cell_contains(c32,17,18),
          cell_contains(c32,22,17),
          cell_contains(c33,110,22),
          cell_contains(c33,95,110),
          cell_contains(c33,103,95),
          cell_contains(c33,22,103),
          cell_contains(c34,22,6),
          cell_contains(c34,2,22),
          cell_contains(c34,1,2),
          cell_contains(c34,6,1)]).