Towers of Hanoi - part 8

In the earlier post, we learned that still, (surprisingly)  there is no mathematical formula for the minimum number of steps needed to solve a Tower of Hanoi puzzle where there can be towers more than 3 and any number of rings. That is no formula exists which gives the number of steps as a function of  rings and towers.

In this post, we will do away with mathematical aspects of this puzzle and focus on what we know better. Yea, the algorithm!

Suppose we have 10 rings (all in the 1st tower) there are 4 towers and you want to move all to the 4th tower.

1) We have to place first 9 rings in the 2 middle towers (tower2 and tower3).
2) Move the 10th towers from tower 1 to tower 4
3) build a tower of 9 in tower4 by using the rings in 2 middle towers.

This will lead to a recursive algorithm. Trick is to get the step 1 above right, how best to distribute the first 9 rings among two middle towers ?

What I did was to write a separate method to determine just that! In that method I will calculate steps needed achieve to each of different distribution of 9 rings. Distributions goes like this :
tower2 have first 8 rings, tower 3 have the ring 9  Or 
tower2 have first 6 rings, tower 3 has 7 to 9
tower2 have first 5, tower 3 has 6 to 9
and so on....

So my method will calculate steps needed to create each of that distribution and then find the distribution which will need the least number of steps to create. Once we know that, we just call our recursion function to build towers. For instance, if the best configuration is 1-6 in tower2 and 7-9 in tower3, our recursive function will look like this.

buildtower4(tower1,tower2,tower3,tower4,6)  // use all 4 towers and build a tower of 1-6 in tower2)
buildtower3(tower1,tower4,tower3,9,7) // use only the give 3 towers and create a tower with rings 9 to 7 in the third tower)
moveRing(tower1, 10, tower4) // ok, we created the optimal distribution of first 9 rings, now move the 10th ring to final destination)
buildTower3(tower3,tower1,tower4,9,7) // build a tower of 9-7 in tower4. don't touch tower2)
buildTower4(tower1,tower4,tower2,tower3,6) // use all 4 towers and build a tower of 1-6 on top of tower4 

Implement something like that in any language and you will have a working code which solves the 4 tower puzzle!

Now, 3 challenges from today's post :
1) Write the algorithm to determine the optimal combination to distribute N rings in the two middle towers.
2) Implement that algorithm in code.
3) implement the given algorithm today to solve the 4 tower puzzle once and for all!

In the next post we will see few sample outputs from my code... and few screen shots to ram in what we discussed today, for those who have already got the message from today's post, good luck with the code!


See you soon.....