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 2^{n}-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 –

- Move disk 1 from 1->2
- Move disk 2 from 1->3
- Move disk 1 from 2->3
- Move disk 3 from 1->2
- Move disk 1 from 3->1
- Move disk 2 from 3->2
- Move disk 1 from 1->2
- Move disk 4 from 1->3
- Move disk 1 from 2->3
- Move disk 2 from 2->1
- Move disk 1 from 3->1
- Move disk 3 from 2->3
- Move disk 1 from 1->2
- Move disk 2 from 1->3
- 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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> using namespace std; void move(int disks, int source, int auxiliary, int target) { if (disks > 0) { // move N-1 discs from source to auxiliary using target // as intermediate pole move(disks - 1, source, target, auxiliary); // move one disc from source to target cout << "Move disk " << disks << " from " << source << "->" << target << endl; // move N-1 discs from auxiliary to target using source // as intermediate pole move(disks - 1, auxiliary, source, target); } } // main function int main() { int N = 3; move(N, 1, 2, 3); return 0; } |

**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(2^{n}) 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 2^{64}-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