Tuesday, February 22, 2011
Bringing Down Towers of Hanoi - part1
Hope this post will not bring as much destruction as it's title suggests. In fact, we are not interested in bringing down any single tower in Hanoi, not even in any where else for that matter. What we would be doing is to brining down the problem of Towers of Hanoi into the levels we can understand it. Of course, if that was the title, we wouldn't probably be in here reading this right now would we ?
Towers of Hanoi is a popular puzzle, first introduced by the French mathematician Édouard Lucas in 1883. (However, some do maintain that the puzzle is much older than that) Those who are not familiar with the puzzle can learn all about it from here. There is a particular interest on this puzzle by the hacker (programmer, developer, coder) community mainly due to the fact that it has been taught in many 1st year CS courses throughout the world. The puzzle is a great example to demonstrate the power of recursion.
However, Towers of Hanoi is a deep enough problem that one can do it for a PhD. It could go many levels in depth and complexity. The most simplest version, I guess most of our readers have already studied in first year. Let's approach the problem step by step. If you are not a programmer and/or haven't done this problem before consider yourself lucky! you got an opportunity to have a fresh look at a very interesting problem and reap all the satisfaction of finding the solution on your own! Oh boy, this series gonna be a bit longer one....
Ready to jump in ? Ok, let's bring them down then!
Problem is to move all the rings from first tower into the third tower, one buy one. Here's the catch : you can not ever put a bigger ring on top of a smaller ring. That's why you have been provided with a middle tower, to transit.
Can you solve this your self ? of course you can. (animation at top of the page) All it need is some patience...
Now can we design a computer program to solve this. let's give it a try ....
1) Solve it by hand for fewer number of rings and think recursively.
2) Consider three towers as three arrays. One has digits 0 to 9 in that order at start. At the end of the program execution, we need to have all digits in the 3rd array in the proper order.
We will see the answer to this basic version of the problem in the next article by the form of a peace of small, executable code. Remember, we would be upping the ante a bit in the next article and things would get more and more challenging and fun as we go on.....
So, do try it! give it a shot if you haven't already wrote a program to solve this by your self!