Bringing Down Towers of Hanoi - part7

In last post, we planned to discuss more about the problem of multi towers in hanoi and give some hints on the algorithm.

Interestingly, for multiple towers, no one has still come up with a general formula to express the number of steps as a function of number of towers and number of rings. Some general cases have been figured out though. For instance, we don't need to be mathematicians to say whats the number of steps would be for a problem with more towers than there are rings. Say, 11 towers and only 10 rings! what would be the number of steps to solve this ?

Of course, it would take 9 steps to remove top 9 rings into 9 different towers. Then 10 steps to put all rings in the target tower. 19 steps in all. In other words, 2n-1 ! However, people have found that coming up with a general formula when the number of rings are greater than number of towers (which is greater than 3) is little bit harder than that.

In an earlier post we have seen it takes exactly 2n-1 to solve the 3 tower case (worse case) for n rings.

We have just saw that it takes 2n-1 to solve the m tower case for n rings where m > n (best case)

What happens when m =n, Here is my result. I will intentionally leave out the explanations so you can arrive at that independently.

When m = n, it takes (n-1) + 1 + (n-2) + 3 = 2n+1 steps to solve the puzzle!

Similarly, when m = n-1, it becomes 2n+3

It appears like we could express number of steps as (2n-1) + 2*(n-(m+1)) = 4n - 2m + 1

However, these are true only when number of towers are closer to number of rings. When number of towers become less compared to number of rigs, it get complicated. Say, 10 rings in 4 towers. However, solving such a puzzle manually is much easier (in terms of number of steps needed) than solving a similar number of rings with 3 towers. Problem is when we try to find the optimal strategy.

I could display few graphical outputs from the program I currently have but before that, wouldn't you want to give it a try yourself ? Remember, number of steps needed is drastically reduced now. We will still need a recursive solution as the nature of the problem commands....