/* Programming example: Towers of Hanoi */

hanoi(N) :- move(N,left,centre,right).

/* Number of discs, source disc, distination disc, spare disc */
move(0,_,_,_):-!.
move(N,A,B,C) :-
        M is N-1,
	move(M,A,C,B),
	inform(A,B),
	move(M,C,B,A).

inform(X,Y) :-
        write(X),write('->'),write(Y),nl.

/* Test run:

| ?- hanoi(3).                  
left->centre
left->right
centre->right
left->centre
right->left
right->centre
left->centre

*/

/* Note: use of cut is easily avoided: */

move1(0,_,_,_).% :-!.
move1(N,A,B,C) :-
        N >= 1,
        M is N-1,
	move1(M,A,C,B),
	inform(A,B),
	move1(M,C,B,A).



/* Programming example: DFS graph search */

/* True if we can go from X to Y. T is list of vertices visited already */

dfsSearch(Source,Destination) :- dfs(Source,Destination,[Source]).

dfs(X,X,_).
dfs(X,Y,T) :-
      edge(X,Z),
      \+member(Z,T),
      dfs(Z,Y,[Z|T]).

edge(a,b).
edge(a,d).
edge(a,c).
edge(b,d).
edge(c,d).
edge(d,c).

/* Test runs:

Is satisfied once for each possible path from a to d:

| ?- dfsSearch(a,d).

true ? ;

true ? ;

true ? ;

no


Can find all paths from a node:

| ?- dfsSearch(a,X).

X = a ? ;

X = b ? ;

X = d ? ;

X = c ? ;

X = d ? ;

X = c ? ;

X = c ? ;

X = d ? ;

no


Even all paths to a node (essentially, the call to edge starts a dfs search
from each edge in graph):

(Note that contents of T will be instantiated due to the sharing between
first and third argument to dfs in the initial call from dfsSearch - this
is important, since member on a list containing uninstantiated variables
will succeed, hence the \+ member would fail.)

| ?- dfsSearch(X,c).

X = c ? ;

X = a ? ;

X = a ? ;

X = a ? ;

X = b ? ;

X = d ? ;

no


Even all paths in the graph:

| ?- dfsSearch(X,Y).            

Y = X ? ;

X = a
Y = b ? ;

X = a
Y = d ? ;

X = a
Y = c ? ;

X = a
Y = d ? ;

X = a
Y = c ? ;

X = a
Y = c ? ;

X = a
Y = d ? ;

X = b
Y = d ? ;

X = b
Y = c ? ;

X = c
Y = d ? ;

X = d
Y = c ? ;



*/