% -*- Prolog -*-
%
% $Id: 094,v 1.5 2000/08/26 14:02:58 peteg Exp $

main :-
	demo1.

/************************************************************************/
/*                                                                      */
/* XSB System								*/
/* Copyright (C) SUNY at Stony Brook, 1986, 1993; ECRC, 1990		*/
/*                                                                      */
/* Everyone is granted permission to copy, modify and redistribute XSB  */
/* but only under the conditions described in the XSB Licence Agreement.*/
/* A copy of this license is supposed to have been given to you along	*/
/* with XSB so you can know your rights and responsibilities.		*/
/* It should be in a file named LICENSE.				*/
/* Among other things, this notice must be preserved on all copies.	*/
/*									*/
/************************************************************************/

/*======================================================================
  File			:  ham.P
  Author(s)		:  Some ECRC guy
  Modified by		:  Kostis Sagonas
  Last modification	:  April 12, 1993
========================================================================*/

/************************************************************************/
% the problem consists in finding a closed path through a graph such
% that all the nodes of the graph are visited once. (Hamiltonian path)
/************************************************************************/

go :- cputime(T1), go1, cputime(T2), T is T2 - T1,
	write('Time used: '),  write(T), write(' sec'), nl.

demo :- cputime(T1), demo1, cputime(T2), T is T2 - T1,
	write('Time used: '),  write(T), write(' sec'), nl.


go1 :- cycle_ham([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t], _), fail.
go1.

demo1 :- cycle_ham([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t], Sol),
	 write(Sol), nl, fail.
demo1.

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 ).

edge( X, Y ):-
        connect( X, L ), 
        el1( Y, L ).

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

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
connect( 0, [1, 2, 3, 4, 5, 6, 7, 8, 9] ).
connect( 1, [0, 2, 3, 4, 5, 6, 7, 8, 9] ).
connect( 2, [0, 1, 3, 4, 5, 6, 7, 8, 9] ).
connect( 3, [0, 1, 2, 4, 5, 6, 7, 8, 9] ).
connect( 4, [0, 1, 2, 3, 5, 6, 7, 8, 9] ).
connect( 5, [0, 1, 2, 3, 4, 6, 7, 8, 9] ).
connect( 6, [0, 1, 2, 3, 4, 5, 7, 8, 9] ).
connect( 7, [0, 1, 2, 3, 4, 5, 6, 8, 9] ).
connect( 8, [0, 1, 2, 3, 4, 5, 6, 7, 9] ).
connect( 9, [0, 1, 2, 3, 4, 5, 6, 7, 8] ).
-----------------------------------------*/

