% hanoi.P
% This is an example program
% To load it, type consult('hanoi.P').
% Note the single quotes.  This is necessary as SBProlog
% 	considers the '.' character to be the termination character
%	for a clause.

% This program is an implementation of the Towers of Hanoi problem.
% Supposedly in Tibet, there is a tower of 64 golden disks.  Each
% disk is of a different radius, and the disks are placed on a pole
% such that the largest is at the bottom and the smallest at the
% top.

% The monks job was to move all the disks from one tower to a
% second one (they could also use a third or auxilary tower)
% with the following restrictions:
%	Only one disk can be moved at a time
%	A disk may never have a large one placed above it

% To use the program, you need to determine how many
% disks you want and the names of the three towers.
% As an example, try:
%	hanoi(3,start,aux,end, Solution).
% This will solve the tower of hanoi for 3 disks.
% The solution is a list of moves.

% You can also compile the program for greater speed.
% Type the following:
%	compile('hanoi.P','hanoi').
%	load(hanoi).
% The first line compiles the program into a file named hanoi.
% Surprisingly enough, load -- well, it loads the byte code
% (compiled) file hanoi.  Once it is loaded, it can be executed
% just as if you had consulted it.

% append(A,B,C) - True when list C is the concatenation of lists A & B
append([],List,List).
append( [H|T], List, [H | Outlist]) :- append(T, List, Outlist).

% hanoi(N, From, Aux, To, Solution_list) - True when Solution_list
% is the solution to the Towers of Hanoi problem of N disks.
hanoi(1,From,Aux,To,[move(From,To)]).
hanoi(N,From,Aux,To,Moves) :-
	Nminus1 is N - 1,
	hanoi(Nminus1,From,To,Aux,Offmvs),
	hanoi(Nminus1,Aux,From,To,Onmvs),
	append(Offmvs,[mv(From,To)|Onmvs],Moves).