Tower of Hanoi Problem

The Tower of Hanoi is a mathematical puzzle consisting of three rods and n disks of different sizes which can slide onto any rod.

 
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  • Only one disk can be moved at a time.
     
  • Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
     
  • No disk may be placed on top of a smaller disk.
     

The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n-1, where n is the number of disks.

 
tower-of-hanoi

An animated solution of the Tower of Hanoi puzzle for N = 4 can be seen here.

Below are the steps taken by the proposed solution –

  1. Move disk 1 from 1->2
  2. Move disk 2 from 1->3
  3. Move disk 1 from 2->3
  4. Move disk 3 from 1->2
  5. Move disk 1 from 3->1
  6. Move disk 2 from 3->2
  7. Move disk 1 from 1->2
  8. Move disk 4 from 1->3
  9. Move disk 1 from 2->3
  10. Move disk 2 from 2->1
  11. Move disk 1 from 3->1
  12. Move disk 3 from 2->3
  13. Move disk 1 from 1->2
  14. Move disk 2 from 1->3
  15. Move disk 1 from 2->3

 


 

We can easily solve Tower of Hanoi problem using recursion. A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached.

To move n discs from pole 1 to pole 3:

  • move n-1 discs from 1 to 2. This leaves disc n alone on pole 1
  • move disc n from 1 to 3
  • move n-1 discs from 2 to 3 so they sit on disc n

C++ implementation –
 

Download   Run Code

Output:

Move disk 1 from 1->3
Move disk 2 from 1->2
Move disk 1 from 3->2
Move disk 3 from 1->3
Move disk 1 from 2->1
Move disk 2 from 2->3
Move disk 1 from 1->3

 
Time complexity of above solution is O(2n) where n is number of disks. If n = 64 and one disk is moved per second, then even by using the smallest number of moves available, it would take 264-1 seconds or roughly 585 billion years to finish the game.
 

References: https://en.wikipedia.org/wiki/Tower_of_Hanoi

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of