The Tower of Hanoi puzzle is attributed to the French mathematician Edouard Lucas, who came up with it in 1883. His formulation involved three pegs and eight distinctly-sized disks stacked on one of the pegs from the biggest on the bottom to the smallest on the top.
Given a stack of n disks arranged from largest on the bottom to smallest on top placed on a rod A, together with two empty rods B and C. The objective is to move the n disks from rod A to rod C using rod B.
Example: The solution for 3 disks takes 7 steps:
If we observe, to move the bottom disk, we need to move all the disks above it to another rod first. Then we can move the bottom disk to the remaining empty rod and move the n − 1 smaller disks back on top of it. In other words, one way to move the stack of rod A to rod C is:
In the above procedure, we are solving the problem using the solution of smaller sub-problems i.e. using recursion. How? Let’s think! Initial problem was to move n disks from rod A to rod C. Now it gets reduced to moving 2 smaller subproblems of size n - 1:
Suppose we use the method towerHanoi(n, A, C, B) to move n rings from rod A to C using rod B. The base case is a situation when we have more disks to move i.e. n = 0. Think!
void towerHanoi(int n, String A, String C, String B)
{
if(n > 0)
{
towerHanoi(n - 1, A, B, C)
move(n, A, C)
towerHanoi(n - 1, B, C, A)
}
}
So first recursive call moves n - 1 disks from A to B using C. So after that call n - 1 disks are in rod B in order of size and rod A contains the nth disk i.e, the largest one. So, now move the nth disk from A to C using method move(n, A, C). Then again by the 2nd recursive call move n-1 disk from B to C using A. So, after this, C contains all disks in order of size.
Let the time complexity for moving n disks is T(n). There are 2 recursive calls for n-1 disks and one move operation to move a disk from A to C. If n = 1, we simply move the single disk directly.
For n > 1, T(n) = 2 T(n — 1) + 1, where T(0) = 0 and T(1) = 1
We can solve this equation using the substitution method. Here are the steps:
=> T(n) = 2 * [2 * T(n - 2) + 1] + 1 = 4 * T(n - 2) + 3
=> T(n) = 4 * [2 * T(n - 3) + 1] + 3c = 8 * T(n - 3) + 7
... and so on ....
=> T(n) = 2^i * T(n - i) + (2^i - 1)
When i = n, It will reach the base case i.e. T(0).
=> T(n) = 2^n * T(0) + (2^n- 1)
=> T(n) = 2^n * 0 + (2^n - 1)
=> T(n) = 2^n - 1
=> T(n) = O(2^n)
So it has exponential time complexity which is computationally very expensive! For a single increase in problem size, the time required is double the previous one. This is not due to the fact that this particular algorithm is poor; in fact, it is not difficult to prove that this is the most efficient algorithm possible for this problem.
Analysis of tower of Hanoi using recursion tree method:
An interesting story: In the original version of the Tower of Hanoi puzzle, as published by its inventor, the French mathematician Édouard Lucas, in the 1880s, the world will end after 64 disks have been moved by monks from a mystical Tower of Brahma. Assuming that the monks do not eat, sleep, or die and move one disk per minute, the world will end after about 3 ·10^13 years, which is more than one thousand times longer than the estimated age of the universe.
The total space used is dominated by the space for the recursion stack. Let c denote the space used by a copy of the local variables. Since the space used by the first call is released when it returns, the recurrence relation for the space used: S(n) = c (If n =1), S(n) = S(n −1) + c (If n > 1).
The solution to this recurrence relation is O(n). From another analogy, the space used by the call stack is equal to the depth of the recursion tree, which is equal to n. So space complexity = n*c = O(n).
Enjoy learning, Enjoy algorithms!
There is a stack of n boxes. Now in each move, we divide one stack of boxes into 2 non-empty stacks. The game ends when we have n stacks of a single box. We earn points for each move i.e. for dividing a stack of heights A + B into 2 stacks of heights A and B, we will score AB points for that move. Overall score is the sum of points that we earn for each move. How can we maximize the total score?
You’ve got someone working for you for seven days and a gold bar to pay him. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. What is the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?
There are n+1 people at a party. They might or might not know each other names. There is one celebrity in the group, and the celebrity does not know anyone by their name. However, all the n people know that celebrity by name. You are given the list of people present at the party. And we can ask only one question from each one of them. “Do you know this name”? How many maximum numbers of questions do you need to ask to identify the actual celebrity?