Neat little puzzle
The tower fo hanoi was invednted by the 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 the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller.
Recurrence relation
Let's say that T(n) is the minimum number of moves that will transfer n disks from one peg to another under Lucas's rules:
T(0) = 0
T(n) = 2T(n-1) + 1, for n > 0
Source code
/**
* hanoi - solve little puzzle called the Tower of Hanoi
* @disks - disks stacked in decreasing size on 'from_peg' peg
* @from_peg - peg which disks stacked in decreasing size fristly
* @to_peg - transfer the entire tower(disks) to 'to_peg' peg last
* @tmp_peg - relay peg
*
*/
void hanoi(int disks, int from_peg, int to_peg, int tmp_peg)
{
if(disks == 0)
{
printf("No need to move!!/n");
return;
}
if(disks == 1)
{
printf("%d: %d --> %d/n", disks, from_peg, to_peg);
return ;
}
hanoi(disks-1, from_peg, tmp_peg, to_peg);
printf("%d: %d --> %d/n", disks, from_peg, to_peg);
hanoi(disks-1, tmp_peg, to_peg, from_peg);
}