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.

CC BY-SA 3.0, 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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz