%%  Hamilton cycle problem 
%%  The graph is given as facts "vtx(X)." and "edge(X,Y)."
%%  One vertex v is given as initial vertex "initialvtx(v)." 
%%  The key predicate is "hc". Atom "hc(X,Y)" represents the fact 
%%  that edge (X,Y) is in the Hamiltonian cycle to be constructed. 

% Select edges for the cycle
{ hc(X,Y) } :- edge(X,Y).

% Each vertex has at most one incoming edge in a cycle
:- 2 { hc(X,Y):edge(X,Y) }, vtx(Y).

% Each vertex has at most one outgoing edge in a cycle
:- 2 { hc(X,Y):edge(X,Y) }, vtx(X).

% Every vertex must be reachable from the initial vertex through chosen
% hc(v,u) edges
:- vtx(X), not r(X).

r(Y) :- hc(X,Y), edge(X,Y), initialvtx(X).
r(Y) :- hc(X,Y), edge(X,Y), r(X), not initialvtx(X).

initialvtx(1).

[ hc(X,Y) : vtx(X;Y) = weight(edgewt(X,Y)) ] w.