/* 

  Hamiltonian path in Picat.
  
  From XSB's examples/ham.P
  """
  the problem consists in finding a closed path through a graph such
  that all the nodes of the graph are visited once. (Hamiltonian path)
  """

  A little more general approach: Allow different graphs in edge/2
  via the global map.

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

main => go.

%
% 60 solutions: 0.15s
%
go ?=>
   get_global_map().put(graph,connect),
   cycle_ham([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t], Sol),
   println(sol=Sol),
   fail,
   nl.
go => true.

%
% 362880 solutions: 4.5s
%
go2 ?=>
  get_global_map().put(graph,connect2),
  cycle_ham([0,1,2,3,4,5,6,7,8,9], Sol),
  println(sol=Sol),
  fail,
  nl.


cycle_ham([X|Y],[X,T|L]) :-
  chain_ham([X|Y],[],[T|L] ),
  edge(T,X).           %  the last connection

chain_ham([X|Y], K, L) :-
  delete(Z, Y, T),
  edge(X, Z),
  chain_ham([Z|T],[X|K], L).
chain_ham([X],L,[X|L]).

delete(X, [U|Y], [U|Z]) :-
  delete(X,Y,Z).
delete(X,[X|Y],Y).

%
% A little more general:
% Fetch the graph from the global map
%
edge(X, Y) :-
 % connect(X, L), % Original
 Graph = get_global_map().get(graph),
 call(Graph,X,L),
 el1(Y, L).

el1(X,[X|_]).
el1(X,[_|L]) :-
  el1(X,L).

/* The graph */
connect(a, [b, j, k]).
connect(b, [a, c, p]).
connect(c, [b, d, l]).
connect(d, [c, e, q]).
connect(e, [d, f, m]).
connect(f, [e, g, r]).
connect(g, [f, h, n]).
connect(h, [i, g, s]).
connect(i, [j, h, o]).
connect(j, [a, i, t]).
connect(k, [o, l, a]).
connect(l, [k, m, c]).
connect(m, [l, n, e]).
connect(n, [m, o, g]).
connect(o, [n, k, i]).
connect(p, [b, q, t]).
connect(q, [p, r, d]).
connect(r, [q, s, f]).
connect(s, [r, t, h]).
connect(t, [p, s, j]).

/*-----------------------------------------
        this is another graph example
-----------------------------------------*/
connect2(0, [1, 2, 3, 4, 5, 6, 7, 8, 9]).
connect2(1, [0, 2, 3, 4, 5, 6, 7, 8, 9]).
connect2(2, [0, 1, 3, 4, 5, 6, 7, 8, 9]).
connect2(3, [0, 1, 2, 4, 5, 6, 7, 8, 9]).
connect2(4, [0, 1, 2, 3, 5, 6, 7, 8, 9]).
connect2(5, [0, 1, 2, 3, 4, 6, 7, 8, 9]).
connect2(6, [0, 1, 2, 3, 4, 5, 7, 8, 9]).
connect2(7, [0, 1, 2, 3, 4, 5, 6, 8, 9]).
connect2(8, [0, 1, 2, 3, 4, 5, 6, 7, 9]).
connect2(9, [0, 1, 2, 3, 4, 5, 6, 7, 8]).