The tower of Hanoi

There are a few stuffs that just get stuck in our mind and make us think about it all the time…

A few days back, when I was watching the movie “rise of the planet of the apes”, something interesting stuck in my mind … Most of us would have noticed the ape (Bright Eyes) playing with the “the tower of Hanoi” (well… ya, that’s what it is called). The above animation might help you remember the scenes from the movie. The ape was able to solve the puzzle in 20 moves while the perfect score was 15… hmm… that’s quite interesting, is it? Well, not yet. The interesting part is the puzzle itself. The TOWER OF HANOI, also known as the tower of “BRAHMA”, was invented by a French mathematician, Édouard Lucas.
The main objective of the puzzle is to move the entire stack of disks to another rod, obeying the following rules:
1. Only one disk can be moved at a time.
2. At any point of time, the larger disk should not be placed above the smaller one.

Édouard Lucas was inspired by a legend that tells of a Hindu temple. At the beginning of this world, Lord Brahma, gave the priests in the temple 64 gold disks, each one a little smaller than the one beneath it. Their assignment was to transfer the 64 disks from one of the three poles to another; with one important provisional large disk could never be placed on top of a smaller one. The priests worked very efficiently, day and night. When they finished their work, the myth said, the temple would crumble into dust and the world would vanish.

So, the doomsday clock is in the hands of those priests… really???

Well, if the legend is true, and assuming that the priests are fast enough to move each disk in 1 sec and considering the priests to be smart enough to do the whole process in the least number of moves, it would take (2^64)-1  moves, that would be 18,446,744,073,709,551,615s or 585 billion years to finish. This is, more than 40 times the age of Universe itself. Well, this might let some of us down, who are so damn hopeful of the apocalypse this year… bear it.

Advertisements

6 thoughts on “The tower of Hanoi”

1. Even I’m fascinated by this problem. But even more interesting than the problem itself is the short recursive solution to it.

The following is a procedure for moving a tower of h disks from a peg A onto a peg C, with B being the remaining third peg:

Step 1: If h>1 then first use this procedure to move the h-1 smaller disks from peg A to peg B.
Step 2: Now the largest disk, i.e. disk h-1 can be moved from peg A to peg C.
Step 3: If h>1 then again use this procedure to move the h-1 smaller disks from peg B to peg C.

(Source: Wikipedia)

This was my first taste of recursion 2 years ago. Recursion helps solve a lot of problems in Computer Science. It’s somewhat magical. 🙂

1. kushal30 says:

actually i didn’t realise the importence of recursion while studying my computer science related subjects.. It was just a 4-5 marks question.. mug it up with an example:)

1. I feel recursion is one of the best concepts I’ve come across….With Recursion, you can write programs that solve Sudoku, solve Mazes, generate permutations and combinations of characters, and a whole lot more. Maybe it’s not the most efficient sometimes, but it still is beautiful. Check out this article: http://stevelosh.com/blog/2008/08/beauty-in-computer-science-recursion/ – Read the sections titled “What’s Recursion?”, “Why is it beautiful?”, “So What?”.

Maybe Prism of Life could feature an article on Recursion in the future. 🙂

2. kushal30 says:

sure:) and we would like to see it written by jinkchak

3. Coming soon, in the not too distant future. 🙂

4. kushal30 says:

I ll ask rana to send you author request. But will you be writing under same name “jinkchak”? I wanted to send you author request on “novelvibes”(name subject to change). or do you use different writing name?