Tower of Hanoi
The tower of Hanoi is a mathematical game invented by French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs.
The objective is to transfer entire tower A to the peg B, moving only one disk at a time and never moving a larger one onto a smaller one.
The algorithm to transfer n disks from A to B in general: We first transfer n - 1 smallest disks to peg C, then move the largest one to the peg B and finally transfer the n - 1 smallest back onto largest (peg B).
The number of necessary moves to transfer n disks can be found by
Tn = 2^n - 1
Here is the sample solution in C:
void hanoi(int n_disks, char source, char destination, char temp)
{
static n_move = 0;
if (n_disks == 1) {
printf("%d - Move disk 1 from %c to %c\n", ++n_move, source, destination);
} else {
hanoi(n_disks - 1, source, temp, destination);
printf("%d - Move disk %d from %c to %c\n", ++n_move, n_disks, source, destination);
hanoi(n_disks -1, temp, destination, source);
}
}
int main(int argc, char *argv)
{
int n_disk = 8;
char source = 'A';
char destination = 'B';
char temp = 'C';
hanoi(n_disk, source, destination, temp);
return 0;
}