Maudlin ruminations of a mind bit by wanderlust.

These are the towers of Hanoi :



The story goes that a bunch of monks in Vietnam were given 3 pegs and 64 golden discs, and had to move all of them from one peg to another, using the third as storage. However, they could never place a larger disc on top of a smaller one. The day they finished their task would be the end of the world, says the legend. That's quite ok with the most of us though, because if we assume that the monks can move one disc in one second, we can show that it will take them 584542046.09062564 millenia or thereabouts to finish the task. So unless they started a reeeally long time ago, the end of the world isn't going to happen any time soon. But that's assuming they know how to go about doing it. We can do better.

Recursion is a great tool for the lazy programmer. If it is easy to state the problem at hand in terms of the problem itself, then recursion is the way forward. Consider, that to solve the problem of hanoi,

-- We want to move all the discs from one peg to another (source to destination, with the other being called storage).
-- We can do this as follows :
-- If there are no discs on a peg, do nothing.
-- Move all but the last disc from the source peg to the storage peg using the destination as storage.
-- Move the last peg from source to destination.
-- Move all the discs you moved earlier to the destination, now that the largest disc is there.

Using this description, we can write :

def transfer(discs, source, destination, storage) :
    # If there is nothing to transfer, do nothing.
    if discs == 0 :
        return

    # Transfer all but the last disc to the temporary storage location
    transfer(discs - 1, source, storage, destination)

    # Transfer the last disc to the destination
    print "Moving disc %d from %s to %s" % (discs, source, destination)

    # Transfer all but the last disc from the temporary storage to the
    # destination
    transfer(discs - 1, storage, destination, source)

def main() :
    n = int(raw_input("Enter the number of discs : "))
    source = 'A'
    destination = 'B'
    storage = 'C'
    transfer(n, source, destination, storage)

Note that we start the process for n discs by calling,

transfer(n, source, destination, storage)

For 3, 4 & 5 discs, the moves are as follows :

(sykora@nexus)(pts/3 | 0 job(s))(Thursday June 14, 2007 : 22:08:54)
(%:python)- python2.5 hanoi.py
Enter the number of discs : 3
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B

Enter the number of discs : 4
Moving disc 1 from A to C
Moving disc 2 from A to B
Moving disc 1 from C to B
Moving disc 3 from A to C
Moving disc 1 from B to A
Moving disc 2 from B to C
Moving disc 1 from A to C
Moving disc 4 from A to B
Moving disc 1 from C to B
Moving disc 2 from C to A
Moving disc 1 from B to A
Moving disc 3 from C to B
Moving disc 1 from A to C
Moving disc 2 from A to B
Moving disc 1 from C to B

Enter the number of discs : 5
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B
Moving disc 4 from A to C
Moving disc 1 from B to C
Moving disc 2 from B to A
Moving disc 1 from C to A
Moving disc 3 from B to C
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 5 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B
Moving disc 3 from C to A
Moving disc 1 from B to C
Moving disc 2 from B to A
Moving disc 1 from C to A
Moving disc 4 from C to B
Moving disc 1 from A to B
Moving disc 2 from A to C
Moving disc 1 from B to C
Moving disc 3 from A to B
Moving disc 1 from C to A
Moving disc 2 from C to B
Moving disc 1 from A to B

Forgetting for the moment about the actual moves, and concentrating on the number of moves, we find :

3 : 7
4 : 15
5 : 31
...

Notice a pattern? For 64 discs, the number of steps would be 2**64 - 1, which is 18446744073709551615. Taking this as a number of seconds we get the above mentioned number of millenia if the monks moved a disc a second.

What's the use? I'm told that a major use of this problem is to evalutate the pyschological stability of patients. Yes, that's apart from predicting the end of the world, and teaching recursion.