Tower of Hanoi recursion game algorithm explained

Tower of Hanoi game is a puzzle invented by French mathematician Édouard Lucas in 1883.

History of Tower of Hanoi

There is a story about an ancient temple in India (Some say it's in Vietnam - hence the name Hanoi) has a large room with three towers surrounded by 64 golden disks. These disks are continuously moved by priests in the temple. According to a prophecy, when the last move of the puzzle is completed the world will end. These priests acting on the prophecy, follow the immutable rule by lord Brahma of moving these disk one at a time. Hence this puzzle is often called Tower of Brahma puzzle.

Tower of Hanoi is one of the classic problems to look at if you want to learn recursion. It is good to understand how recursive solutions are arrived at and how parameters for this recursion are implemented.

What is the game of Tower of Hanoi ?

Tower of Hanoi consists of three pegs or towers with n disks placed one over the other. The objective of the puzzle is to move the stack to another peg following these simple rules.

  1. Only one disk can be moved at a time.
  2. No disk can be placed on top of the smaller disk.

Before we proceed, let's understand Recursion -

What is Recursion?

Tower of Hanoi

When a function calls itself, it's called Recursion. It will be easier for those who have seen the movie Inception. Leonardo had a dream, in that dream he had another dream, in that dream he had yet another dream, and that goes on. So it's like there is a function called dream()dream(), and we are just calling it in itself.

Recursion is useful in solving problems which can be broken down into smaller problems of the same kind. But when it comes to solving problems using Recursion there are several things to be taken care of. Let's take a simple example and try to understand those. Following is the pseudo code of finding the factorial of a given number XX using recursion.

Detailed explanation to Recursion can be found - Here

Tower of Hanoi algorithm explained

Let’s try to solve a puzzle - Tower of Hanoi using recursion.

Take an example with 2 disks: Disk 1 on top of Disk 2 at peg A. The target is to move both these disks to peg B.

Tower of hanoi algorithm explained

Looks simple, Right!

Move Disk 1 from peg A to peg C. Then move disk 2 from peg A to peg B and, finally, move disk 1 from peg C to peg B. This solution takes 3 steps. You can easily move this stack from peg B to any other peg using these 3 steps.

But what if we have 3 disks - 1,2, and 3 stacked in peg A.

To move the stack to peg B you would have to expose disk 3, and to do that disk 1 and 2 have to be moved to peg C. So by ensuring that you do not break the rules, using the above subsets of 3 steps in the previous case, you would move disk 1 and 2 to peg C, leaving disk 3 exposed with no disk above it.

http://blog.hackerearth.com/become-better-developer

Now to solve the problem, recursively move disk 3 from peg A to peg B. Then disk 1 from peg C to peg A. After which disk 2 can be moved above disk 3 at peg B. The puzzle is finally completed by moving disk 1 from peg A over disk 2 and 3 at peg B.

What if you have 4 disks?

  • Recursively solve problem of moving disk 1,2, and 3 from peg A to peg C
  • Move disk 4 from A to C
  • Recursively solve problem of moving disk 1,2 and 3 from peg C to peg B

Eventually, you figure out that there is some pattern to the puzzle and with each increment in disks, the pattern could be followed recursively.

While 3-disk puzzle required 7 steps. 4-disk requires 7+1+7 = 15 steps to be solved.

Check the GIF here for 4 disks

via GIPHY

  • Create a function Tower with int 'a' - for number of disks, char 'from' - for from peg, char 'aux' - for secondary peg, char 'to' - for destination peg
  • Put 'if' loop
  • If (a=1) i.e. if number of disk = 1, move it from 'initial peg' to the 'destination peg'
  • Else, call function tower for 'a-1' i.e. number of disk -1, recall function tower for n-1 disk and move it 'from' to 'to'
  • Recall function again using recursion until an or number of the disk is 1.

Call the function 'tower' in the main program

Tower of Hanoi maths explained - 

By now, you might have identified that to move N disks from one peg to another, you need 2^{N}-1. So, the number of steps almost double every time you insert another disk in the stack.
Let us prove that the number of steps in 2^{N}-1
The question is what is the minimum number of moves(a_N) required to move all the N-disks to another peg. Let's look at a recursive solution
One can already see that a_1=1, a_2=3, a_3)=7 and so on.
For a given N number of disks, the way to accomplish the task in a minimum number of steps is:

  1. Move the top N-1 disks to an intermediate peg.
  2. Move the bottom disk to the destination peg.
  3. Finally, move the N-1 disks from the intermediate peg to the destination peg.

Therefore, the recurrence relation for this puzzle would become:

\displaystyle a_1=1, a_2=3; a_N=2a_{N-1}+1; N\geq2

Tower of hanoi, recursion, algorithm , explained, Tower of hanoi explained, Recursion explained

Now one can solve this relation in iteration as follows-

Tower of hanoi recursion explained, Tower of Hanoi, Tower of Hanoi recursion, Recursion explained, Tower of Hanoi explain

 

But what about the prophecy for the tower of Hanoi where the priests are using 64 disks?

Suppose that these priests are highly powerful and can move these massive disks at a speed of 1 per second per hour every day. At this speed, they would need 2^64 -1 moves to complete the task. That is, 18,446,744,073,709,551,615 moves to complete, which would take about 580 billion years. Considering our Milky Way is about 13.21 billion years old and our planet is only 5 billion years old, that is a lot of time for the prophecy to be true (worry about.)

Tower of Hanoi recursion sample problem in C++ -

Tower of Hanoi is a common dynamic programming problem used in various competitive programming challenges. Here is one such question from HackerEarth Challenge

Q. Bob and Alice like to play the game Tower of Hanoi. One day Alice challenges Bob to build the tallest tower from a set of disks of different height and radius. The Tower of Hanoi can be built by stacking disks on top of each other. To put disk A on top of disk B, the radius and height of A must be strictly smaller than those of B. Help Bob win the challenge.

Here is Tower of Hanoi program using C++

Time to end the world on a doomsday or by Tower of Hanoi all can be calculated by mathematics.

Mathematics holds the solution for most of the complex problems, from football betting to banking.

Practice and learn more such algorithms and on CodeMonk and participate in HackerEarth challenges.

Subscribe now for more such article on Algorithms.

About the Author

Arpit Mishra
Data structure & algorithm enthusiast. Wannabe motorcycle aficionado. Avid book reading advocate. Hardcore travel nerd. Technology freak.
10