Subj : Re: Towers Of Hanoi
To   : comp.programming
From : buda
Date : Tue Sep 27 2005 01:50 pm

"Kokil" <dot_tee@yahoo.com> wrote in message 
news:1127812164.565961.103960@z14g2000cwz.googlegroups.com...
> Refering to the classic solution of the Towers Of Hanoi problem-- could
> anyone here explain to me the logic behind it? It is still beyond me...
>

Try to look at the problem from the top down. You have n rings on stick A, 
and need to put them on stick B using stick C (only moving one ring at a 
time, and never putting a larger ring onto a smaller ring). Now, consider 
the final situation: stick B will look the same as stick A looks at the 
beginning, namely, it will have the biggest ring on the bottom. The only way 
to get the largest ring to the bottom of stick B is to have all other rings 
on stick C, and the largest ring on stick A. Then you simply move the 
largest ring from A to B. Now, you have much the same problem to solve as 
before: you need to figure out how to get n-1 rings from stick A to stick C, 
using B. Similarly, when you move the biggest ring (A is empty, B has only 
the largest ring, n-1 rings on C), you need to move the remaining n-1 from C 
to B using A. So you have found a pattern!
hanoi(n, A, B, C) = hanoi(n-1, A, C, B) + 1 + hanoi(n-1, C, B, A);
All that is left is to examine the starting cases: when n=0, there are no 
rings to move, so hanoi(0, whatever, whatever, whatever) = 0. When n=1, 
there is only the largest ring to move from A to B, and that takes one move 
so hanoi(1, whatever, whatever, whatever) = 1;
Pluck this into a simple recursive function, and you can easily get a 
solution. Beware however that the runtime of this approach is exponential, 
so you shouldn't try it for n bigger then, say, 10-20. Also note that it 
requires 2^n-1 moves to move n rings in this way. You can provide some 
output inside the function to get the exact order of the moves required.
This is a solution, but you should also prove that this is the optimal 
solution. This is easy, given a certain level of mathematical maturity, and 
you can find the proof itself in a lot of places.

Hope this helps,
Ivan

.