home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / lang / SBProlog-1.zoo / SBProlog / hanoi.P < prev    next >
Encoding:
Text File  |  1988-06-23  |  1.8 KB  |  48 lines
  1. % hanoi.P
  2. % This is an example program
  3. % To load it, type consult('hanoi.P').
  4. % Note the single quotes.  This is necessary as SBProlog
  5. %     considers the '.' character to be the termination character
  6. %    for a clause.
  7.  
  8. % This program is an implementation of the Towers of Hanoi problem.
  9. % Supposedly in Tibet, there is a tower of 64 golden disks.  Each
  10. % disk is of a different radius, and the disks are placed on a pole
  11. % such that the largest is at the bottom and the smallest at the
  12. % top.
  13.  
  14. % The monks job was to move all the disks from one tower to a
  15. % second one (they could also use a third or auxilary tower)
  16. % with the following restrictions:
  17. %    Only one disk can be moved at a time
  18. %    A disk may never have a large one placed above it
  19.  
  20. % To use the program, you need to determine how many
  21. % disks you want and the names of the three towers.
  22. % As an example, try:
  23. %    hanoi(3,start,aux,end, Solution).
  24. % This will solve the tower of hanoi for 3 disks.
  25. % The solution is a list of moves.
  26.  
  27. % You can also compile the program for greater speed.
  28. % Type the following:
  29. %    compile('hanoi.P','hanoi').
  30. %    load(hanoi).
  31. % The first line compiles the program into a file named hanoi.
  32. % Surprisingly enough, load -- well, it loads the byte code
  33. % (compiled) file hanoi.  Once it is loaded, it can be executed
  34. % just as if you had consulted it.
  35.  
  36. % append(A,B,C) - True when list C is the concatenation of lists A & B
  37. append([],List,List).
  38. append( [H|T], List, [H | Outlist]) :- append(T, List, Outlist).
  39.  
  40. % hanoi(N, From, Aux, To, Solution_list) - True when Solution_list
  41. % is the solution to the Towers of Hanoi problem of N disks.
  42. hanoi(1,From,Aux,To,[move(From,To)]).
  43. hanoi(N,From,Aux,To,Moves) :-
  44.     Nminus1 is N - 1,
  45.     hanoi(Nminus1,From,To,Aux,Offmvs),
  46.     hanoi(Nminus1,Aux,From,To,Onmvs),
  47.     append(Offmvs,[mv(From,To)|Onmvs],Moves).
  48.