Trying to implement recursive Tower of Hanoi algorithm with arrays

Question

Even though there's plenty of questions about this problem here, none of them have helped me clear this up. I understand what recursion is and I can easily solve Towers of Hanoi by myself in 2^n-1 moves, but I'm having trouble writing an algorithm for it in Python. The base case works but I can't seem to find a way to translate "move n-1 disks to the auxiliary peg and then the largest disk to the target peg" into array operations, and I don't understand why the last element isn't getting removed from the array when I pop it in the recursive call.

This is the programme:

peg_a = [1,0]
peg_b = []
peg_c = []

def hanoi(start,aux,target):
    print(start,aux,target)
    if len(start) == 1:
        target.append(start.pop())
        print(start,aux,target)
    else:
        hanoi(start[1:],target,aux)
        target.append(start.pop())
        print(start,aux,target)

hanoi(peg_a, peg_b, peg_c)

And this is what gets printed:

[1, 0] [] []
[0] [] []
[] [] [0]
[1] [0] [0]

Any help?

Answer 1

I think one problem is that your function does not return anything. You use lists to hold the contents of the bigs, which are modifyable objects, so you could see the function arguments as pointers to those objects. This might work, but the problem is that by making a slice with start[1:], you create a new list, so it is no longer a 'pointer' to the original list.

One workaround might be to still use the input arguments as pointers to the lists, but than add some extra integer function arguments, which indicate how many disks to move.

This is how I would do it:

def hanoi(pegs, start, target, n):
    assert len(pegs[start]) >= n, 'not enough disks on peg'
    if n == 1:
        pegs[target].append(pegs[start].pop())
        print '%i -> %i: %s' % (start, target, pegs)
    else:
        aux = 3 - start - target  # start + target + aux = 3
        hanoi(pegs, start, aux, n-1)
        hanoi(pegs, start, target, 1)
        hanoi(pegs, aux, target, n-1)

I do not use 3 different lists, since in your code they get swapped around, so it is hard to visualize what is happening. Instead, I have a single pegs variable, which is a list of lists. In my case, start and target are the indices of the pegs, which I swap around. The nice thing is that you can now print the individual steps. Quick demonstration:

pegs = [[4, 3, 2, 1], [], []]
hanoi(pegs, 0, 1, 4)    

with result

0 -> 2: [[4, 3, 2], [], [1]]
0 -> 1: [[4, 3], [2], [1]]
2 -> 1: [[4, 3], [2, 1], []]
0 -> 2: [[4], [2, 1], [3]]
1 -> 0: [[4, 1], [2], [3]]
1 -> 2: [[4, 1], [], [3, 2]]
0 -> 2: [[4], [], [3, 2, 1]]
0 -> 1: [[], [4], [3, 2, 1]]
2 -> 1: [[], [4, 1], [3, 2]]
2 -> 0: [[2], [4, 1], [3]]
1 -> 0: [[2, 1], [4], [3]]
2 -> 1: [[2, 1], [4, 3], []]
0 -> 2: [[2], [4, 3], [1]]
0 -> 1: [[], [4, 3, 2], [1]]
2 -> 1: [[], [4, 3, 2, 1], []]

Answer 2

There are two problems with your code:

• While it seems like a clever idea at first, using start[1:] does not work, as you are creating a copy of the list and thus not modifying the original list any more (see Bas' answer).
• You are missing the second recursive call in the else part, stacking the discs from the aux peg to the target peg.

To fix the first problem, the easiest way would be to add an aditional parameter, indicating the number of discs to relocate from start to target:

def hanoi(n, start, aux, target):
    if n == 1:
        target.append(start.pop())
    else:
        hanoi(n - 1, start, target, aux)
        target.append(start.pop())
        hanoi(n - 1, aux, start, target)

Or shorter:

def hanoi(n, start, aux, target):
    if n > 0:
        hanoi(n - 1, start, target, aux)
        target.append(start.pop())
        hanoi(n - 1, aux, start, target)