Bringing Down Towers of Hanoi - part2

Ok, Here we would discuss the solution and the code to implement it for our little tower puzzle. Those who are new to the series or those who like to give one last try at the puzzle before looking at the answer. Can do so by going back to part1.

Let's imagine we have a simple tower of 5 rings.

To move the rings in first tower to 3rd tower, we need to move the larger ring to 3rd tower first since we can not place it above any other rings. (remember the rule : there can never be a larger ring on top of a smaller one) However, to move the largest ring from tower 1, we need to move all the other out of it first so that we can lift it. At the same time we have to keep the tower1 empty so that we can put the largest ring there. That means we need to have this position.
Aha! now we can move the largest ring to tower3, then we will have to build a tower from 1-4 on top of tower 3 to complete the puzzle.

In other words, to build a tower of height N on tower3 (from tower1), we need to :

1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)

Let's go back to the diagram where we have cleared tower1 to lift the largest ring (5th ring) :
To lift that, we had to create a tower of 1-4 on tower2, but to do that we need to move the ring 4 into tower2, this means we need to remove rings 1-3 from tower 1 first so that we can move ring4 into the middle one...


Hmm, so we needed to build a tower 1-3 on tower3 in order to move 4 into tower2! (in order to move ring 5 to the ultimate goal, tower3) Similarly, we would first have to build a tower 1-2 on tower2 to move the ring3 to tower3. To do that, we need to move 1 into tower3 so that we can move 2 into tower 2. So our first move should be :


Thus, moving the smallest ring to tower2 as the first move will be wrong! ring1 has to be on tower 3 because : (hold your breadth now, see whether you can follow this in your head till the end)

We needed to move 2 into tower2 (to build 1-2 on tower2), that was because
We needed to move 3 into tower3 (to build 1-3 on tower3), that was because
We needed to move 4 into tower2 (to build 1-4 on tower2), that was because
We needed to move 5 into tower3 (to build1-5 on tower3), that was because
It was the end goal of the puzzle!

Simple isn't it ? Solving the case of 10 rings would have the exact same logic. There we will have to move ring 1 into tower2 as our first move. (follow the same logic in your mind for 10 steps and you will see why)

Now to the code. Earlier we deduced that,

Building a tower of height N on tower3 (from tower1), is as same as saying :
1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)

that included building a tower of N-1 on tower2, but in the same logic, we can define building a tower of N-1 as :
1) build a tower of height N-2 on tower3 (from tower1)
2) move the ring N-1 from tower1 into tower2
3) build a tower of height N-2 (again) but this time on top of tower2 (from tower3)

and so on until we build a tower of 1. Now, can write the small little recursive function to solve the entire puzzle?

Hint : it has only 3 lines.

In the next post, we will see the code and we will also investigate why that it always take 2ⁿ - 1 steps to solve a Tower of Hanoi problem with N rings.

Challenge 1 : write the code to solve Towers of Hanoi puzzle for a given N.

Challenge 2 : in the above solving algorithm, prove that it always takes exactly 2ⁿ - 1 steps to solve the puzzle.