## The story about Towers of Hanoi

In this article, we are going to take you through the famous puzzle game, Tower of Hanoi, step by step and perform a complete analysis of it.The creator of Tower of Hanoi puzzle, Edouard Lucas, French mathematician, actually got this entire concept from a legend of a Hindu Temple wherein if the priests could solve this puzzle containing 64 disks, the entire world would vanish. Read on to know more about this puzzle.

## The puzzle

In this game, there are 3 towers of Hanoi and N number of disks are placed one over the other in the decreasing order of their size. The objective of this game is to move the disks one by one from the source (first tower on the left) to the destination (the last tower). And the condition is that that we cannot place a bigger disk on top of a smaller disk. We are going to achieve this by using an intermediate tower and using the concept of recursion.(1)

Consider the given figure, there are three towers namely A, B, C (from left to right) and there are three disks placed in increasing size from top to bottom. The objective is to move the disks from tower A to tower C in such a way that they are in the same order – red, green and blue, similar to what’s given in tower A.

## Algorithm

1. Initially, all the disks remain at tower A.

2. Now, move n-1 disks from the source tower to destination tower. Here, n=3, hence the first 2 disks will be moved from the tower A to B.

3. Move the nth disk from source to destination tower. So, the third disk will move from the tower A to B.

4. Finally, move the n-1 disks from auxiliary tower to destination tower. The objective of transferring the disks from tower A to B is fulfilled and we can solve it with any number of disks with the same recursive algorithm.

### Total movement of disks

If there are n disks, then we can solve it by using a minimum of 2^{n} – 1 moves.

Example: If n=3, then we require 2^{3} – 1= 7 moves

## Code

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 |
package com.algorithm; import java.util.Scanner; // importing scanner class public class TowerOfHanoi { public void towerofhanoi(int disk, String src, String aux, String dest) { if (disk == 1) // If the number of disk is 1, move and return { System.out.println(src + " --> " + dest); // Printing where the disk has to be moved return; } towerofhanoi(disk - 1, src, dest, aux); // Move top n-1 disks from A to B using C as auxiliary. towerofhanoi(1, src, aux, dest); // Move remaining disks from A to C System.out.println(src + " --> " + dest); // printing the source and destination towerofhanoi(disk - 1, aux, src, dest); // Move n-1 disks from B to C using A as auxiliary } public static void main(String args[]) // main function { TowerOfHanoi towerofhanoiobj = new TowerOfHanoi(); // object creation System.out.println("Enter number of disks :- "); // Asking the user to enter the number of disks Scanner scanner = new Scanner(System.in); // creating a new scanner object int n = scanner.nextInt(); // scanning the next integer scanner.close(); // closing it System.out.println("Move disks in the following manner"); // printing this statement towerofhanoiobj.towerofhanoi(n, "A", "B", "C"); // giving the input and calling the function } } |

On execution of the above code, it queries for the number of disks. Once entered, it automatically presents you with the order in which you should move the disks as shown below.

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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
Enter number of disks :- 5 Move disks in the following manner A --> C A --> B A --> B C --> B A --> C A --> C B --> A B --> C B --> C A --> C A --> B A --> B C --> B C --> A C --> A B --> A C --> B C --> B A --> C A --> B A --> B C --> B A --> C A --> C B --> A B --> C B --> C A --> C B --> A B --> A C --> B C --> A C --> A B --> A B --> C B --> C A --> C A --> B A --> B C --> B A --> C A --> C B --> A B --> C B --> C A --> C |

## Time Complexity

Time Complexity equation would be:

T(n) = 2T(n-1) + 1 – equation 1

Solving it by substitution,

T(n-1) = 2T(n-2) + 1 – equation 2

T(n-2) = 2T(n-3) + 1- equation 3

Putting the value of T(n-2) in equation 2 through equation 3:

T(n-1) = 2(2T(n-3)+1) + 1 àequation 4

Putting the value of T(n-1) in equation 1 through equation 4

T(n)= 2(2(2T(n-3)+1)+1)+1

After generalisation you get :

T(n) = 2^{k}T(n-k)+ 2^{(k-1) }+ 2^{(k-2)} +….+2^{2} + 2^{1} +1

Base condition T(0) == 1

n – k = 0

n = k;

put, k = n

T(n) = 2^{n}T(n-k)+ 2^{(n-1) }+ 2^{(n-2)} +….+2^{2} + 2^{1} +1

Solving this, you get O(2^{n}) which is exponential.

So, for the fact that we mentioned earlier, if the priests did actually succeed to, it would take them a minimum of 264 years, approximately 5.8 billion years. Who knows, it still could happen!

## More to Read