Tower of Hanoi

Tower of Hanoi
The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks (initially four in the applet below), initially stacked in increasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs (the rightmost one in the applet below), moving only one disk at a time and never a larger one onto a smaller.

The puzzle is well known to students of Computer Science since it appears in virtually any introductory text on data structures or algorithms. Its solution touches on two important topics discussed later on:

* recursive functions and stacks
* recurrence relations

def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print a, '->', c
        hanoi(n-1, b, a, c)

for n in (2, 3, 5):
        print 'hanoi:', n
        hanoi(n, 'a', 'b', 'c')

hanoi: 2
a -> b
a -> c
b -> c
hanoi: 3
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
hanoi: 5
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
a -> b
c -> b
c -> a
b -> a
c -> b
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
b -> a
c -> b
c -> a
b -> a
b -> c
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c