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!

Bringing Down Towers of Hanoi - part4

In last post, we wondered what on earth the number 2^n-1 doing (regardless of how many N rings we used!) in our little towers problem, for all the values of N.

We need to look at the recursion little deep to answer that question. As discussed earlier, solving N rings is exactly equal to do the following :

1) make a tower N-1 on the transit tower
2) move ring N from source to the final destination
3) make a tower N-1 on final destination

That involved 2 towers with height N-1 and moving of one ring. Similarly making a tower of N-1 will be equal to making 2 towers of N-2 and moving a ring. if we expand this for 3 ring case:

tower of 3 = 2 * (tower of 2) + 1 = 2 * (2*(tower of 1) +1) + 1 = 2 * (2*(1) +1) + 1 = 7 = 2³ - 1
(since making a tower of 1 always takes one move)

so, making a tower of 3 involved making 2 towers of 2 and 1 move.
that is, 4 towers of 1 and 2 + 1 moves.
that is, 2^(3-1) towers of 1 and 2¹ + 2⁰ moves. (making a tower of 1 takes just 1 move)
that is, 2^n-1 + (2^{n-2 +} 2^n-3 + 2^n-4 + ... + 2⁰⁾

Total Steps = 2^n-1 + (2^{n-2 +} 2^n-3 + 2^n-4 + ... + 1)

but the sum of sequence (2^{n-2 +} 2^n-3 + 2^n-4 + ... + 1) = 2^n-1 - 1

Hence total steps = 2^n-1 + 2^n-1 - 1 = 2 * (2^n-1 ) - 1 = 2ⁿ-1 !!

Wow, now we know why it has to be 2ⁿ-1 always !!

Our series is only just starting to get interesting! Now to the today's challenge :

We can now write a nice recursive function to solve the puzzle. However, what we are solving is actually a subset of the problem. We have so far considered cases where all the rings are in tower 1. How about we removing that restriction, how about letting the rings to be anywhere on 3 towers (as long as a bigger ring is not upon a smaller). Can we come up with the code to resolve that ?

In fact, this can be considered as the general case in Towers of Hanoi. What we have discussed in earlier posts was just a specific subset of it. In the next post, we will come with few more hits on how to approach that.

Meanwhile, try it out yoursef!