Tower of Hanoi

The Tower of Hanoi is a simple puzzle with an interesting pattern as a solution. You have 3 pegs with 3 discs of different sizes set at the first peg in ascending order like this:



The puzzle is to move all the disks one by one to the last peg with the two rules that every disc must be set at a peg and that no disc be placed on a smaller disc. The puzzle is made harder by the addition of more discs.

The minimal number of moves needed to move all 3 discs is 7 as follows:















So how do we know that there is no shorter way to move them all to the other side? Let's ignore the number of discs and just focus on how to reach the goal.

There are three sub goals required to reach the final goal:

1. Move all the discs except the largest one out of the way, allowing the largest disc to be set at the destination peg.
   
   
   
2. Move the largest disc to the destination peg.
   
   
3. Move the rest of the discs on the largest disc.
   
   

The crucial point of this puzzle is that the movement of the smaller discs is independent of the largest disc. This means that the number of steps needed to move the smaller discs to the middle peg is the same as the number of steps needed to solve the Tower of Hanoi with one less disc.

It also doesn't matter which peg is the destination peg since the number of moves would be equivalent regardless of where the pegs need to go. All that matters is that all the discs move from one peg to another with just another peg to move around on.

So the formula for finding the smallest number of steps needed to move "n" discs is

steps(n) = steps(n-1) + 1 + steps(n-1)

where the first "steps(n-1)" is the number of steps to move the smaller discs to the other peg, the "1" is the number of steps to move the largest disc to the destination peg and the last "steps(n-1)" is the number of steps needed to move the smaller discs on top of the largest disc.

Let's see an example.

steps(3) =


The first thing we want to do is to move the 2 smaller discs off the largest disc so the the largest disc can be placed on the destination peg like this:

steps(3-1)


Then we need to move the largest disc to the destination peg like this:

+ 1


Finally we need to move the smaller disc to the destination peg as well like this:

+ steps(3-1)


How many steps will it take to move the smaller discs though? It will take the same number of steps as solving the Tower of Hanoi with 2 discs only like this:

steps(2) =


steps(2-1)


+ 1


+ steps(2-1)


Which is the same as when moving smaller 2 discs in the the 3 disc version, except that the destination peg was the middle rather than the last:

steps(3-1) =


steps(3-1-1)


+ 1


+ steps(3-1-1)


Anything other than this strategy will increase the number of steps needed to reach the goal because it means that at some point a disc was placed at a peg in which a larger disc needs to be placed and hence you will need to bring that smaller disc back to its original place.

So we go back to the proposed formula:

steps(n) = steps(n-1) + 1 + steps(n-1)

The recursion of the formula can keep on going until it turns into the number of steps to move 1 disc which is:

steps(1) = 1

Now the formula can be simplified into:

steps(n) = 2 steps(n-1) + 1

Can we solve the recurrence relation into a simple closed form? Without loss of generalization, let's try to decompose it iteratively for n=4:

steps(4) = 2 steps(3) + 1
steps(4) = 2(2 steps(2) + 1) + 1
steps(4) = 2(2(2 steps(1) + 1) + 1) + 1
steps(4) = 2(2(2(1) + 1) + 1) + 1
steps(4) = 2(2(2 + 1) + 1) + 1

Expanding the expression we get:

steps(4) = 2(2(2 + 1) + 1) + 1
steps(4) = 2(2(2) + 2 + 1) + 1
steps(4) = 2(2(2)) + 2(2) + 2 + 1

So it seems we have a sum of powers of 2, which is:

steps(4) = 2^3 + 2^2 + 2^1 + 2^0

A quick look at binary numbers (or just geometric series) lets you quickly notice that this is equivalent to:

steps(4) = 2^4 - 1

Thus, returning back to "n" instead of "4",

steps(n) = 2^n - 1

So the number of steps needed to move "n" discs is "2^n - 1" which means that in the case of 3 discs that is "2^3 - 1" that is, 7.