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....

Bringing Down Towers of Hanoi - part6

Today, we are going to see the magic code which solves Towers of Hanoi General Problem. Those who still (bravely) want to give it an own try before looking at the code. Can go through these hints and do so.

Before going to the code, I have something else to show you. This mathematical proof I found from web, which basically gives a formula for the average number of steps for the general case.



wow, that's some formula for you!

Anyway, as you can see, the code below is the simplicity itself! The solution we propose is bounded by 2n-1, and never exceeds that, also when we present a half done problem, it actually solves it optimally. When you look at the code you get the intuitive feeling that this has to be the optimal solution, wish we could device a mathematical proof too for that fact!

private static void buildTower(int height, ArrayList source,
ArrayList target, ArrayList middle) {
if (height < 0) {
return;
}

if (target.contains(Integer.valueOf(height))) {
buildTower(height -1, source, target, middle);
} else {
if (middle.contains(Integer.valueOf(height))) {
ArrayList temp = middle;
middle = source;
source = temp;
}
buildTower(height-1, source, middle, target);
move(source, target);
print();
buildTower(height-1, middle, target, source);
}
}

Bolded are the lines we added to the last solution. (specific case where all rings are in first tower at the beginning.) Now, isn't this simple ?

One more thing : I havn't yet seen this code (or the algorithm) anywhere in the internet. If some one come across this in anywhere else, please post a comment with the link.

In next post, we will discuss few hints on how to solve the 4 tower case.

Have a nice day!