Towers of Hanoi:

Suppose 3 pegs, labelled A, B and C, are given, and suppose on peg A there are placed a finite number of N of disks with decreasing size.  The objective of the game is to move the disk from Peg A to Peg C using Peg B as an auxiliary.

The rules of the game are as follows:

1. Only one disk may be moved at a time, specifically,  only top disks on any peg may be moved to any other peg.
2. At no time a larger disks placed on smaller disks.

 

Initial Setup of Towers of Hanoi with n=6

 Sometimes we will write X->Y  to denote the instruction “ Move top disk from peg X to Peg Y”  where X and Y may be any of the three pegs.

The solution of the Tower of Hanoi problem for n = 3 shown in figure.

n=3 :               Move top disc from peg A to Peg C

Move top disc from peg A to Peg B

Move top disc from peg C to Peg B

Move top disc from peg A to Peg C

Move top disc from peg B to Peg A

Move top disc from peg B to Peg C

Move top disc from peg A to Peg C

In other words,

n=3,   

A->C,              A->B,              C->B,              A->C,             B->A,                         B->C,              A->C

We also give the solution to the Tower of Hanoi problem for n=1 and n=2.

n=1                 A->C

n=2                 A->B,              A->C,              B->C

 

Rather than finding a separate solution for each n,   we use the technique of recursion to develop a general solution.  first we observed that the solution of the Tower of Hanoi problem for n >1  disk may be reduced to the following some sub problem.

1. Move the top n-1 disks from peg A to peg B
2. Move the top n disks from peg A to peg C : A->C
3. Move the top n-1 disks from peg B to peg 

Let us now introduce a general solution

                               TOWER (N, BEG, AUX, END)

To denote a procedure which moves the top n disks from the initial peg BEG to final peg END using the AUX as an auxiliary.  When n = 1 we have a following solution:

TOWER (1, BEG, AUX, END) Consist of the single instruction BEG->END

When n>1, the solution may be reduced to the solution of the following three sub problems:

TOWER(N-1, BEG, END, AUX)

1. TOWER(1, BEG, AUX, END) or BEG->END
2. TOWER(N-1, AUX, BEG, END)
3. TOWER(N-1, AUX, BEG, END)

TOWER (4, A, B, C)

Procedure: TOWER (N, BEG, END, AUX)

This procedure gives a recursive solution of the Tower of Hanoi problem for N disks.

 1.         If N=1, then :

1. Write BEG->END
2. Return.

[End of if Structure]

2.            [Move N-1 disks from peg BEG to peg AUX]    

Call TOWER (N-1, BEG, END, AUX)

3.            Write: BEG-> END

4.            [Move N-1 disks from peg AUX to peg END]

Call TOWER (N-1, AUX, BEG, END)

5.            Return.