Bringing Down Towers of Hanoi - part 5

In the last post, I promised you to give more hints on how to solve (find the algorithm that is) general case of towers of Hanoi. Those who are new to this Hanoi business, can get up to date from earlier parts of the series.

part1
part2
part3

Let's consider the following scenario we have a tower of height 5, instead of having all stacked up neatly in the 1st tower, we have the largest ring already in tower3.






Here's what a run of my code produced.

Step 0 -> 3,2,1,0, : : 4,

Step 1 -> 3,2,1, : 0, : 4,
Step 2 -> 3,2, : 0, : 4,1,
Step 3 -> 3,2, : : 4,1,0,
Step 4 -> 3, : 2, : 4,1,0,
Step 5 -> 3,0, : 2, : 4,1,
Step 6 -> 3,0, : 2,1, : 4,
Step 7 -> 3, : 2,1,0, : 4,
Step 8 -> : 2,1,0, : 4,3,
Step 9 -> : 2,1, : 4,3,0,
Step 10 -> 1, : 2, : 4,3,0,
Step 11 -> 1,0, : 2, : 4,3,
Step 12 -> 1,0, : : 4,3,2,
Step 13 -> 1, : 0, : 4,3,2,
Step 14 -> : 0, : 4,3,2,1,
Step 15 -> : : 4,3,2,1,0,

wow! it found the biggest ring is already in where it wanted to be so finished off with the optimal solution. How do we know that was the optimal ? well, because it took exactly 15 steps, which isthe expected to solve a tower with height 4. Since 5th tile is already there for us, it is like solving a tower of height 4!

Now, then, let's make it little difficult for the computer and see. we pit the biggest ring in the MIDDLE tower at start and let's see what will happen.






Step 0 -> 3,2,1,0, : 4, :

Step 1 -> 3,2,1,0, : : 4,
Step 2 -> 3,2,1, : 0, : 4,
Step 3 -> 3,2, : 0, : 4,1,
Step 4 -> 3,2, : : 4,1,0,
Step 5 -> 3, : 2, : 4,1,0,
Step 6 -> 3,0, : 2, : 4,1,
Step 7 -> 3,0, : 2,1, : 4,
Step 8 -> 3, : 2,1,0, : 4,
Step 9 -> : 2,1,0, : 4,3,
Step 10 -> : 2,1, : 4,3,0,
Step 11 -> 1, : 2, : 4,3,0,
Step 12 -> 1,0, : 2, : 4,3,
Step 13 -> 1,0, : : 4,3,2,
Step 14 -> 1, : 0, : 4,3,2,
Step 15 -> : 0, : 4,3,2,1,
Step 16 -> : : 4,3,2,1,0,

aha! not so difficult again. Code was smart enough to know it should just move the biggest ring to the 3rd tower and it was exactly as the earlier problem.

What if we make things seriously wrong and ask it to solve ? In the normal solution path, after first 3 moves, we should be having the two smallest rings stacked in the middle tower. Let's put them on tower 3 and see.






Step 0 -> 4,3,2, : : 1,0,

Step 1 -> 4,3,2,0, : : 1,
Step 2 -> 4,3,2,0, : 1, :
Step 3 -> 4,3,2, : 1,0, :
Step 4 -> 4,3, : 1,0, : 2,
Step 5 -> 4,3,0, : 1, : 2,
Step 6 -> 4,3,0, : : 2,1,
Step 7 -> 4,3, : : 2,1,0,
Step 8 -> 4, : 3, : 2,1,0,
Step 9 -> 4, : 3,0, : 2,1,
Step 10 -> 4,1, : 3,0, : 2,
Step 11 -> 4,1,0, : 3, : 2,
Step 12 -> 4,1,0, : 3,2, :
Step 13 -> 4,1, : 3,2, : 0,
Step 14 -> 4, : 3,2,1, : 0,
Step 15 -> 4, : 3,2,1,0, :
Step 16 -> : 3,2,1,0, : 4,
Step 17 -> 0, : 3,2,1, : 4,
Step 18 -> 0, : 3,2, : 4,1,
Step 19 -> : 3,2, : 4,1,0,
Step 20 -> 2, : 3, : 4,1,0,
Step 21 -> 2, : 3,0, : 4,1,
Step 22 -> 2,1, : 3,0, : 4,
Step 23 -> 2,1,0, : 3, : 4,
Step 24 -> 2,1,0, : : 4,3,
Step 25 -> 2,1, : : 4,3,0,
Step 26 -> 2, : 1, : 4,3,0,
Step 27 -> 2, : 1,0, : 4,3,
Step 28 -> : 1,0, : 4,3,2,
Step 29 -> 0, : 1, : 4,3,2,
Step 30 -> 0, : : 4,3,2,1,
Step 31 -> : : 4,3,2,1,0,

great! it didn't exceed 31 steps.

Now, can you come up with the code to produce this ? give it a try.... I have a one last hint. Solving is not so difficult. it will only add just few extra lines to the earlier code we have discussed.

Meanwhile, for those who have already come up with the code (but shy to post it to us on comments), we have the next stage of the challenge!

What about 4 Towers ? Solving this is easy when we do it manually and takes lesser number of steps. How about coming up with an algorithm to do that ?

This is a very interesting challenge to contemplate on......