03.16.08

Tower of Hanoi

Posted in C/C++, Programming at 5:24 pm by Alper

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

T_n = 2ⁿ - 1.

Here is the sample solution in C:

#include <stdio.h>

void hanoi(int n_disks, char source, char destination, char temp)
{
	static n_move = 0;

	if (n_disks == 1) {
		printf("%d - Move the disk 1 from %c to %cn", ++n_move, source, destination);
	} else {
		hanoi(n_disks - 1, source, temp, destination);
		printf("%d - Move the disk %d from %c to %cn", ++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;
}

Permalink