Tower of Hanoi

 619 total views,  4 views today

The classic Tower of Hanoi code problem. It’s a “must solve” for all beginner programmers but the idea of breaking down a large problem into a smaller base case is a staple of programming!

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. He was inspired by a legend that tells of a Hindu temple where the puzzle was presented to young priests.

Here’s the puzzle:

At the beginning of time, the priests were given three poles and a stack of 64 gold disks, each disk a little smaller than the one beneath it. Their assignment was to transfer all 64 disks from one of the three poles to another, with two important constraints. They could only move one disk at a time, and they could never place a larger disk on top of a smaller one. The priests worked very efficiently, day and night, moving one disk every second. When they finished their work, the legend said, the temple would crumble into dust and the world would vanish.

Don’t worry… the world won’t be ending anytime soon. At least not from gold discs getting moved (maybe in 5 and a half billion years when the sun burns out but most of us won’t make it that long).

The number of moves required to correctly move a tower of 64 disks is 264−1=18,446,744,073,709,551,615264−1=18,446,744,073,709,551,615. At a rate of one move per second, that is 584,942,417,355584,942,417,355 years! Can we use a little code to give us the solution to this puzzle?

Yes! Python to the rescue!

def move(f,t):
    print ('Move from ' + str(f) + ' to ' + string (t))

def tower(n, f, t, x):
    if n ==1:
        move(f, t)
    else:
        tower(n-1, f, x, t)
        tower(1, f, t, x)
        tower(n-1, x, t, f)

Run this with your own number of discs as n and get the solution to the problem!