Towers of Hanoi

Illustration of the Towers of Hanoi problem.

You have three stands, called source, destination and auxilliary stands. You have a number of disks (plates with a hole in the centre), arranged one on top of the other on the source stand in order of size such that the largest is at the bottom and the smallest is on top. The problem is to move the disks to the destination stand, such that at the end, they are stacked the same way, with the largest at the bottom and the smallest at the top. Sounds easy, but you have to move the disks one at a time, and at no time can a larger disk sit on top of a smaller disk. You can of course use the auxilliary disk.

The beauty of the solution lies in the fact that you can write a program to do this without knowing how it is to be done, and it will work for any number of disks! Just express the problem in terms of a smaller problem, and keep doing this till you have just one disk to move.

If I have to move 'n' disks from stand A to stand B and can use stand C, then my problem is solved if I can somehow move (n-1) disks from A to C, move the n'th disk from A to B, then (somehow) move the (n-1) disks from C to B.

Oh, great! But how do I move (n-1) disks from A to C in the first place? Easy. If I can (somehow) move (n-2) disks from A to B, then move the (n-1)'th disk from A to C, then move the (n-2) disks from B to C, then I'm done.

Oh, yeah? How do I move (n-2) disks...?

You get the picture. You simply define the problem in terms of something smaller. Finally, the problem reduces to moving a single disk, which you know how to do.

I've written a C program to do it using recursion:

#include 

main()
{
	int n;
	int source = 1;
	int destination = 2;
	int auxilliary = 3;

	n = 4; /* say */

	/*
	Call a function to move the disks. (Never mind how it's done!)
	*/
	move( n, source, destination, auxilliary );
}

move( int n, int s, int d, int a )
{
	/*
	This is the function that moves the disks.
	Note the order of the parameters - n, s, d and a.
	First check how many disks have to be moved.
	*/
	if ( n == 1 )
	{
		/* 
		Only one disk - trivial move from source to destination.
		*/
		printf( "Move from %d to %d\n", s, d );
	}
	else
	{
		/* 
		More than 1 disk. Express in terms of one less disk 
		*/

		/*
		"Somehow", move (n-1) disks from source to auxilliary.
		See how we switch the order of a and d when calling
		ourselves. Our next incarnation won't even know!
		It will move (n-1) disks from source to auxilliary
		thinking that it is moving them from source to destination,
		because we have switched the positions of destination
		and auxilliary.
		*/
		move( n-1, s, a, d ); 

		/*
		Now that we have moved (n-1) disks somehow from
		source to auxilliary, we only have the n'th disk
		to be moved from source to destination. 
		This is trivial.
		*/
		printf( "Move from %d to %d\n", s, d );

		/*
		Now we have to move (n-1) disks back from the
		auxilliary to the destination. No problem,
		we'll call ourselves as before and cleverly
		switch source and auxilliary.
		Our next incarnation won't know.
		*/
		move( n-1, a, d, s );
	}
}

Hits so far:

This page hosted by Get your own Free Home Page