% hanoi.pl

% Towers of Hanoi puzzle solver in Prolog.

 

% Goal is to move, say, 4 disks from left peg

% to right peg, using the middle as a buffer.

% This version displays the state of the pegs after each move.

 

 

go :-

  P1 = [1,2,3,4],

  show(P1,[],[]),

  solve(4, left, middle, right, P1,[],[],NP1,NP2,NP3).

 

% The main predicate is solve.

% N is the number of disks to move.

% They are to be moved from peg A to peg C, using B as a buffer.

% P1,P2,P3 give the state of the pegs before moving the disks.

% NNP1, NNP2, NNP3 give the new state after the disks have been moved.

 

solve(N,A,B,C,P1,P2,P3,P1,P2,P3) :- N == 0.

solve(N,A,B,C,P1,P2,P3,NNP1,NNP2,NNP3) :-

  M is N - 1,

  solve(M, A, C, B, P1, P2, P3,NP1,NP2,NP3),

%  move(A, C),

  update(A,C, NP1,NP2,NP3,NewP1,NewP2,NewP3),

  solve(M, B, A, C, NewP1, NewP2, NewP3, NNP1,NNP2,NNP3).

 

%move(A, B) :- write('Move disk from '),write(A),write(' to '),write(B),nl.

 

update(A,B,P1,P2,P3,NewNewP1,NewNewP2,NewNewP3) :-

  pop(A,X,P1,P2,P3,NewP1,NewP2,NewP3),

  push(B,X,NewP1,NewP2,NewP3,NewNewP1,NewNewP2,NewNewP3),

  show(NewNewP1, NewNewP2, NewNewP3).

 

% Note, the following pop and push operations work on any one

% of the three pegs. The Name argument tells what peg to manipulate.

 

pop(Name,H,P1,P2,P3,NP1,NP2,NP3) :-

  Name == left,   P1 = [H|T], NP1 = T, NP2 = P2, NP3 = P3.

pop(Name,H,P1,P2,P3,NP1,NP2,NP3) :-

  Name == middle, P2 = [H|T], NP1 = P1, NP2 = T, NP3 = P3.

pop(Name,H,P1,P2,P3,NP1,NP2,NP3) :-

  Name == right,  P3 = [H|T], NP1 = P1, NP2 = P2, NP3 = T.

 

push(Name,Elt,P1,P2,P3,NP1,NP2,NP3) :-

  Name == left, NP1 = [Elt|P1], NP2 = P2, NP3 = P3.

push(Name,Elt,P1,P2,P3,NP1,NP2,NP3) :-

  Name == middle, NP1 = P1, NP2 = [Elt|P2], NP3 = P3.

push(Name,Elt,P1,P2,P3,NP1,NP2,NP3) :-

  Name == right, NP1 = P1, NP2 = P2, NP3 = [Elt|P3].

 

show(P1,P2,P3) :-

  write('left:  '),write(P1),nl,

  write('middle:'),write(P2),nl,

  write('right: '),write(P3),nl, nl.