### Tower Of Hanoi – Algorithm And Implementation

Tower Of Hanoi or TOH in short, is a game containing three pegs A, B, C and A contains disks of different diameters in such a way that larger disk is always below a smaller disk. The objective is to move the disks from peg A to peg B, using peg C as auxiliary following following rules :-

- 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 GIF image represents the solving of Tower Of Hanoi with three disks.

Tower of Hanoi puzzle with n disks can be solved in minimum **2 ^{n}−1** steps. This presentation shows that a puzzle with 3 disks has taken

**2**steps.

^{3}– 1 = 7### Algorithm Of Tower Of Hanoi Puzzle

A = source peg, B = destination peg, C = auxiliary peg

- If n = 1, move the single disk from A to B and stop.
- Move the top n-1 disks from A to C(auxiliary peg).
- Move the remaining nth disk from A to B.
- Move the n-1 disk from C to B using A as auxiliary.

### Pseudo code of Tower Of Hanoi

```
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest // Step 1
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 2
move disk from source to dest // Step 3
Hanoi(disk - 1, aux, dest, source) // Step 4
END IF
END Procedure
STOP
```

### C function to solve Tower Of Hanoi Puzzle

```
// C function to solve tower of hanoi puzzle recursively
void towerOfHanoi(int n, char from, char to, char aux)
{
if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c", from, to);
return;
}
towerOfHanoi(n-1, from, aux, to);
printf("\n Move disk %d from rod %c to rod %c", n, from, to);
towerOfHanoi(n-1, aux, to, from);
}
```