Tower of Hanoi

TOH is a mathematical puzzle that consists of three pegs named as origin, intermediate and destination and more than one disks. These disks are of different sizes and the smaller one sits over the larger one.

In this problem, we transfer all disks from the origin peg to the destination peg using the intermediate peg for temporary storage and move only one disk at a time.

Algorithm for TOH problem:

Let’s consider move ‘n’ disks from source peg (A) to destination peg (C), using intermediate peg (B) as auxiliary.

1. Assign three pegs A, B & C

2. If n==1

Move the single disk from A to C and stop.

3. If n>1

a) Move the top (n-1) disks from A to B.

b) Move the remaining disks from A to C

c) Move the (n-1) disks from B to C

4. Terminate

Example for 3 disks: 7 moves

 

Recursive solution of tower of Hanoi

#include <stdio.h>

#include <conio.h>

void TOH(int, char, char, char); //Function prototype

void main()

{

int n;

printf(“Enter number of disks”);

scanf(“%d”,&n);

TOH(n,’O’,’D’,’I’);

getch();

}

void TOH(int n, char A, char B, char C)

{

if(n>0)

{

TOH(n-1, A, C, B);

Printf(“Move disk %d from %c to%c\n”, n, A, B);

TOH(n-1, C, B, A);

}

}

Output:

Enter the number of disks: 3
The sequence of moves involved in the Tower of Hanoi is
Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg

Recursion Tree for TOH

1. Move Tower(N-1, BEG, END,AUX)

2. Move Tower(1, BEG, AUX, END) à(BEG à END)

3. Move Tower (N-1, AUX, BEG, END)

Recursion Tree when no. of disks are 4 as: