Towers of Hanoi puzzle using Recursion
In this puzzle, the player begins with 'n' disks of decreasing diameter. The player must move the disks from peg to peg, using each of the three pegs, until the entire tower is moved from the starting peg to one of the others. The only rule governing the movement of the disks is that in each move a disk of a larger diameter must never be placed on the top of one of a smaller diameter and another condition is that only one disk can be moved at a time from peg to peg.
A solution to the problem of moving a tower of size 'n', from the source peg to the destination peg, using the intermediate peg is found by moving a tower of size n - 1 from the source peg to the intermediate peg, moving the bottom disk from the source peg to the destination peg and finally moving a tower of size n - 1 from the intermediate peg to the destination peg.
Towers of Hanoi problem using recursion
Algorithm for the Towers of Hanoi problem using recursion:
TOH(n, S, D, I) // Move n disks from S to D using I
{
if (n = 1) /I base case
Move(1, S, D)
else
{
TOH(n-1, S, I, D) II Move top n-1 disks from S to I using D
Move(n, S, D) // Move disk n from S to D, now S is empty
TOH(n-1, I, D, S) II Move the n-1 disks which are now on Ito D using S
}
}
#include <stdio.h>
void TOH(int, char, char, char);
void TOH(int n, char S, char D, char I)
{
if(n == 1) // If only 1 disk, make the move and return
{
printf("\n Move disk 1 from S %c to D %c", S, D);
return;
}
TOH(n-1, S, I, D); // Move top n-1 disks from S to I, using D
printf("\n Move disk %d S %c to D %c", n, S, D); // Move nth disk from S to D
TOH(n-1, I, D, S); // Move n-1 disks from Ito D using S
}
main()
{
int n;
printf("Enter the number of disks: ");
scanf("%d", &n);
printf("The TOH involves the moves:\n\n");
TOH(n, '5', 'D', 'I');
return 0;
}
OUTPUT
Enter the number of disks you want to play with: 3
The TOH involves the moves:
Move Diskl from S to D
Move Disk2 from S to I
Move Diskl from D to I
Move Disk3 from S to D
