# 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.

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 –

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