Posts /

Algo #1: Tower of Hanoi

2 mins read ●
Twitter Facebook Google+
31 Aug 2017

Tower of Hanoi

Tower of Hanoi is widely used as a brain teaser in algorithmic coding problems. It is actually a mathematical puzzle game. Read more about Tower of Hanoi here.
The setting of the original puzzle game involves disks and three stands to stack them on. Disks from one stand are to be shifted to the third stand through the second stand. The movement of disks obeys following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
  3. No disk may be placed on top of a smaller disk.

In terms of complexity, for n disks, we have to make 2n - 1 movements. So, if we have 4 disks, we have to make 15 movements to achieve the required formation.

Tower of Hanoi Animated  
Animated representation of Tower of Hanoi puzzle.

Code

Now, to solve this problem programmatically, one has to see the operations it involves. Obviously, only disks are moved over and over again, hence, one can say that movement of disk is done recursively. The best way to solve a problem this complex, is to use recursion.
The code given below moves the disks recursively and prints out the movement of the top disk: from to to while the stands are named right, left, and middle.

def hanoi(height, fro='left', to='right', through='middle'):
    if height:
            hanoi(height - 1, fro, through, to )
            print ('%-7s => %s' % (fro, to))
            hanoi(height -1, through, to, fro)

See some example runs here.


You may also like...


Twitter Facebook Google+