Search code examples
prologtowers-of-hanoi

tower of hanoi prolog

Hello i have a problem with my implementation of the tower of hanoi. I need to print a list of list with the necessary moves, but my algorithm just work when the numbers of discs is N=1. This is my code

move(1,X,Y,_,L) :-  
    append([X],[Y],L).
move(N,X,Y,Z) :- 
    N>1, 
    M is N-1, 
    move(M,X,Z,Y),
    move(1,X,Y,_), 
    move(M,Z,Y,X).

And this is the result when N= 1.

?- move(1,left,right,_,L).

L = [left,right]

(16 ms) yes

i need something like this

    L = [[left,center],[left,right],[center,right],[left,center],[right,left],
      [right,center],[left,center],[left,right],[center,right],[center,left],
[right,left],[center,right],[left,center],[left,right],[center,right]]

When N=4

please if someone could help me i will be gratefull.

Solution

  • With some small changes you could write:

    move(1,X,Y,_,[[X,Y]]).

move(N,X,Y,Z,L) :- 
    N>1, 
    M is N-1, 
    move(M,X,Z,Y,L1),
    move(1,X,Y,_,L2), 
    move(M,Z,Y,X,L3),
    append(L1,L2,L4),
    append(L4,L3,L).

    Example:

    ?- move(4,left,right,center,L).
L = [[left, center], [left, right], [center, right], [left, center], [right, left], [right, center], [left, center], [left, right], [center, right], [center, left], [right, left], [center, right], [left, center], [left, right], [center, right]] ;
false.