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:
In terms of complexity, for
n disks, we have to make
- 1 movements. So, if we have 4 disks, we have to make 15 movements to achieve the required formation.
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:
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.