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

ArrayList

if (height < 0) {

return;

}

if (target.contains(Integer.valueOf(height))) {

buildTower(height -1, source, target, middle);

} else {

if (middle.contains(Integer.valueOf(height))) {

ArrayList

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!

## No comments:

## Post a Comment