Great Classic: Hanoi Tower – Mattia Giuri's bizarre blog

Tower of Hanoi consists of three pegs or towers with n disks placed one over the other. The objective of the puzzle is to move the stack to another peg following these simple rules. Only one disk can be moved at a time. No disk can be placed on top of the smaller disk.

In this article I’ll show how to calculate the minimum number of moves needed to move a tower of height n and I’ll show you how to write a program that solves it recursively.

Hanoi Tower Recursive Law

Obviously, to move a tower of height 1 from a peg to another it takes one move, so $a_1 = 1$ .

Now, notice that, in order to move a tower of height n to another peg, you have to first move a tower of height n-1, then move the biggest disk to the final peg, and finally move again the tower of height n-1.

So the recursive law is:

$a_n = 2a_{n-1} + 1$

The nth term of the recursion is $2^n - 1$ , let’s prove it by induction.

$a_1 = 2 - 1 = 1$

$a_n = 2(2^{n-1}-1)+1 = 2^n - 1$

A Program That Solves It

The program implementation is incredibly elegant and simple, and uses recursion techniques.

def move(x, y):
    print(str(x) + ' to ' + str(y))


def hanoi_solver(n, a, b, c):
    if n == 0:
        pass
    else:
        hanoi_solver(n-1, a, c, b)
        move(a, c)
        hanoi_solver(n-1, b, a, c)


hanoi_solver(4, 1, 2, 3)

So, the move function is the single step that will be applied each time and indicates to move from peg x to peg y. The program will send the tower from peg a to peg c with the help of peg b.

The recursive function says: if n equals 0, do nothing, and that stops the function from going infinitely backwards (the algorithm does not know that towers of negative height don’t exist). In all the other cases, it says to move a n-1 tower from peg a to peg b with the help of peg c, then move the biggest disk to peg c and finally move a n-1 tower from peg b to peg c with the help of peg a.

Obviously, while moving a tower, it calls itself until it arrives to n = 0 and then goes on.

The output of the program looks like that:

1 to 2
1 to 3
2 to 3
1 to 2
3 to 1
3 to 2
1 to 2
1 to 3
2 to 3
2 to 1
3 to 1
2 to 3
1 to 2
1 to 3
2 to 3

Process finished with exit code 0

If you want to check the sequence of moves, you’re free to do it (remember peg 1 is the one on the left of the figure above, peg 2 is the one in the middle and peg 3 is the one on the right).