Tower of Hanoi

Tower of Hanoi :

Tower of Hanoi is puzzle in which there are 3 rods and discs if various sizes. In this we have to move  discs of different sizes from one rod to another using following rules:

    1. Only one disk can be moved at a time.
    2. 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.
    3. No disk may be placed on top of a smaller disk.

When there are n no. of discs then max no.of steps involved to solve the problem is  2n – 1.

e.g. 4 discs involve  24 – 1 = 15 steps

tower of hanoi


To move n discs from peg A to peg C:

    1. move n−1 discs from A to B. This leaves disc n alone on peg A
    2. move disc n from A to C
    3. move n−1 discs from B to C so they sit on disc n

The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg C, is trivial.


Leave a Reply

Your email address will not be published. Required fields are marked *