Tower of Hanoi is a mathematical puzzle where we have three rods and N disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
- No disk may be placed on top of a smaller disk.
The aim is to try and complete the transfer using the smallest number of moves possible. For example if you have three disks, the minimum number of moves is 7. If you have four disks, the minimum number of moves is 15.
If you only have one disk it will take only one move to acheive the objective. It is also easy to show that if you have 2 disks the minimum number of moves is 3. After this, it is possible to show the minimum number of moves using a recursive pattern. Imagine you know the minimum number of moves for N-1 disks, let us call it M.
For N disks, first of all move N-1 disks to rod B using the minimum M moves.
Then move the biggest disk from rod A to rod C using 1 move.
Then move N-1 disks from rod B to rod C using the minimum M moves.
In total you have used 2M+1 moves to solve the problem for N disks. In general for N disk, number of moves is 2^N – 1.
Our ultimate aim is to move disk N from source to destination and then put all other (N -1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks. The steps to follow are:-
- Move N-1 disks from rod A to rod B.
- Move Nth disk from rod A to rod C.
- Move N-1 disks from rod B to rod C
For N =3, below steps is required
- Disk 1 moved from A to C
- Disk 2 moved from A to B
- Disk 1 moved from C to B
- Disk 3 moved from A to C
- Disk 1 moved from B to A
- Disk 2 moved from B to C
- Disk 1 moved from A to C