The Tower of Hanoi

The famous Tower of Hanoi problem involves three poles, one of which (pole A) is stacked with $n$ differently-sized, circular discs, in decreasing order of height with the largest at the bottom. The task is to move the stack to the third pole (pole C) by moving one disc at a time in such a way that a larger disc is never placed on a smaller one. It is necessary to use the second pole (pole B) as an intermediate resting place for the discs.

The problem can be solved using the following recursive algorithm. Label the discs $D_i$ with $D_1$ the smallest disc and $D_n$ the largest.

• Move discs $D_1, D_2, \cdots, D_{n-1}$ from A to B;
• Move disc $D_n$ from A to C;
• Move discs $D_1, D_2, \cdots, D_{n-1}$ from B to C.

The second step is a single move, but the first and last require the movement of a stack of $n-1$ discs from one peg to another - which is exactly what the algorithm itself solves!

In the following code, we identify the discs by the integers $1,2,3,\cdots$ stored in one of three lists, A, B and C. The initial state of the system, with all discs on pole A is denoted by, for example, A = [5,4,3,2,1] where the first indexed item is the "bottom" of the pole and the last indexed item is the "top". The rules of the problem require that these lists must always be decreasing sequences.

def hanoi(n, P1, P2, P3):
    """ Move n discs from pole P1 to pole P3. """
    if n == 0:
        # No more discs to move in this step
        return

    global count
    count += 1

    # move n-1 discs from P1 to P2
    hanoi(n-1, P1, P3, P2)

    if P1:
        # move disc from P1 to P3
        P3.append(P1.pop())
        print(A, B, C)

    # move n-1 discs from P2 to P3
    hanoi(n-1, P2, P1, P3)

# Initialize the poles: all n discs are on pole A.
n = 3
A = list(range(n,0,-1))
B, C = [], []

print(A, B, C)
count = 0
hanoi(n, A, B, C)
print(count)

Note that the hanoi function just moves a stack of discs from one pole to another: lists (reperesenting the poles) are passed in to it in some order and it moves the discs from the pole represented by the first list, known locally as P1, to that represented by the third (P3). It does not need to know which list is A, B or C.