% Numberlink Puzzles

% Input:
% - node(v), v node of the graph
% - edge(e,u,v), {u,v} edge in the graph and e is the name of the edge
% - connection(i,u,v), i is an index number and u and v are node names (u != v).

% Output:
% - link(e), e is an edge name given in the input

% Author: Annamaria Bria


% normalize graph
uedge(Z1,X1,Y1) :- edge(Z1,Y1,X1).
uedge(Z1,X1,Y1) :- edge(Z1,X1,Y1).

% GUESS
% guesses all possible linked adges for a connection N
noLinked(Z,N) :- not linked(Z,N), connection(N,S,A), uedge(Z,X1,X2).
linked(Z,N) :-not noLinked(Z,N), connection(N,S,A), uedge(Z,X1,X2).

% Builds the path of the linked edges
path(N,X1,Y1) :- connection(N,X1,Fv1), uedge(Z1,X1,Y1), linked(Z1,N).
path(N,X1,Y2) :- path(N,X1,Y1), uedge(Z1, Y1, Y2), Y1!=Y2, linked(Z1,N), X1!=Y2.

% CHECK
% For each connection must exists a path
:- connection(N,X1,X2), not path(N,X1,X2).

% Each uedge can linked for exactly one connection
:- linked(Z,N), linked(Z,M), N!=M.

% Each node must belong to exactly one connection
:- linked(Z1,N),linked(Z2,M), N!=M, Z1!=Z2, uedge(Z1,X1,Y1), uedge(Z2,X1,Y2).

% A uedge can belong to exactly one connection
:-  path(N,X1,Y1), path(M,X1,Y2), Y1!=Y2, N!=M.
:-  path(N,X1,Y1), path(M,X2,Y1), X1!=X2, N!=M.

% Each node can have exactly two outgoing edges
:- linked(Z1,N), linked(Z2,N), linked(Z3,N), Z1!=Z2, Z2!=Z3, Z3!=Z1,
   uedge(Z1,X1,Y1), uedge(Z2,X1,Y2), uedge(Z3,X1,Y2).

% Each linked uedge must belong to exactly one path
pippo :- linked(Z,N), uedge(Z,X,Y), not path(N,X1,X), connection(N,X1,Fv1), X1!=Y, X1!=X.


% OUTPUT
link(Z) :- linked(Z,Fv1).



