Tower of Hanoi

The Tower of Hanoi game is very useful in understanding the Recurrence relation. It is a game of moving N disk between 3 needles. However, there are some rules we must follow before moving a disk from one needle to second needle.

Rule 1: Move only one disk at a time and it must be a top one.

Rule 2. Cannot move a larger disk on top of smaller one.

Rule 3: Number of moves should be minimum.

Let see how this works for 3 disk Tower of Hanoi game and using output of the game we can find solution to Tower of Hanoi game for N disk.

 

Tower of Hanoi - Initial Setup with Pegs
Tower of Hanoi – Initial Setup with Pegs
Initially , our disks stacked in needle 1 and other two remain empty. Each time we move a disk it is counted as 1.
TOH - Disk Move From Needle 1 to Needle 3
TOH – Disk Move From Needle 1 to Needle 3
Move top disk from needle 1 to needle 3.
TOH - Move disk from Needle 1 to Needle 2
TOH – Move disk from Needle 1 to Needle 2
 
Move top disk from needle 1 to needle 2.
 
TOH - Move disk from Needle 3 to Needle 2
TOH – Move disk from Needle 3 to Needle 2
Move top disk from needle 3 to needle 2.
TOH - Move disk from Needle 1 to Needle 3
TOH – Move disk from Needle 1 to Needle 3
Move top disk from needle 1 to needle 3.
 
TOH - Move disk from Needle 2 to Needle 1
TOH – Move disk from Needle 2 to Needle 1
Move top disk from needle 2 to needle 1.
TOH - Move disk from Needle 2 to Needle 3
TOH – Move disk from Needle 2 to Needle 3
 
Move top disk from needle 2 to needle 3.
TOH - Move disk from Needle 1 to Needle 3
TOH – Move disk from Needle 1 to Needle 3
Move top disk from needle 1 to needle 3.
So we took total 7 Moves to shift all 3 disks.

Let the total number of disk move be H.
If we want to compute total count for 4 disk Tower of Hanoi game.

H_{n}=2(H_{n-1}-1) +1

= 2 . 7 + 1

= 14 + 1

=15

There minimum 15 disk move required for 4 disk Tower of Hanoi game.

We can derive a much easier formula for  H_{n}=2(H_{n-1}-1) +1

= 2^n - 1

How we arrived at this solution, we leave it as an exercise for you.

Advertisements