Tower of Hanoi :
- 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.
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:
- move n−1 discs from A to B. This leaves disc n alone on peg A
- move disc n from A to C
- 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.
C SOURCE CODE:
void toh(int n, char from, char to, char aux)
if (n == 1)
printf("n Move disk 1 from rod %c to rod %c", from, to);
toh(n-1, from, aux, to);
printf("n Move disk %d from rod %c to rod %c", n, from, to);
toh(n-1, aux, to, from);
printf("nEnter the no. of disks :");
printf("nSequence of steps are:n");
toh(n, 'A', 'C', 'B');