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 simple rules:

Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted 

                         

These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one.

There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.

Rules

The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are −

  • Only one disk can be moved among the towers at any given time.
  • Only the "top" disk can be removed.
  • No large disk can sit over a small disk.

Following example solving a Tower of Hanoi puzzle with three disks.

Take an example for 2 disks:

Let rod 1 = 'A', rod 2 = 'B', rod 3 = 'C'.

Step 1: Shift first disk from 'A' to 'B'. Step 2: Shift second disk from 'A' to 'C'. Step 3: Shift first disk from 'B' to 'C'.

The pattern here is:

Shift 'n-1' disks from 'A' to 'B'. Shift last disk from 'A' to 'C'.

Shift 'n-1' disks from 'B' to 'C'. Image illustration for 3 disks: