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!