Page 1 of 1

TOWERS OF HANOI C RECURSION TUTORIAL PART 3 Rate Topic: -----

#1 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 101
  • View blog
  • Posts: 453
  • Joined: 02-May 09

Posted 20 August 2010 - 10:54 AM

TOWERS OF HANOI
C RECURSION TUTORIAL
PART 3

CONTENTS
• I. INTRODUCTION
• II. TOWERS OF HANOI
• III. ANALYSIS OF EXAMPLE PROGRAM
• IV. EXAMPLE PROGRAM
• V. REFERENCES


I. INTRODUCTION

Hello; nice to meet you. Welcome to the “Towers of Hanoi - C Recursion Tutorial - Part 3.”

II. TOWERS OF HANOI

The Towers of Hanoi is a game or puzzle. It consists of three vertical anchored rods of equal length and diameter, spaced an equal distance apart on a playing board. The puzzle includes a number of disks of different diameters and equal thickness with a hole in their center slightly larger than the diameter of the rods which can slide onto any of the three rods. The puzzle starts with all the disks in a neat conical stack, the smallest disk at the top, in ascending order of size on one rod, the rod to the far left facing the player. The center vertical rod can be used as a temporary resting place for the disks as they are moved back and forth between the three rods. The objective of the puzzle is to eventually move the entire stack of disks from the rod on the far left, to the rod on the far right, obeying the following rules:

A. Only one disk may be moved at a time.

B. Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.

C. No disk may be placed on top of a smaller disk.

There are many variations of the source of this puzzle. One describes an ancient Vietnamese Buddhist temple in Hanoi which contains a large temple room with three time-worn posts surrounded by 64 golden disks. The Buddhist priests of Hanoi, acting out the command of an ancient Buddhist prophecy, have been moving these disks, in accordance with the rules of the puzzle, since the dawn of time. According to the legend, when the last move of the puzzle is completed, the world will end.

III. ANALYSIS OF EXAMPLE PROGRAM

To keep the analysis easy to understand I have hard coded the program to use three disks.

#define DISKS 3  /*  Number of disks.  */



The disks are numbered 1, 2, and 3. The number 1 represents the smallest disk with higher numbers representing progressively larger disks.

The screen prints which show the position of the disks, use a 0 to represent the absence of any disk.

The formula to determine the minimum number of steps required to transfer n disks from rod A to rod C is ((2 to the power of n) minus 1). Therefore; using 3 disks the puzzle can be solved in ((2*2*2) - 1) = 7 moves.

Sorry, the program only accommodates screen printing of single digit disk numbers. However, you can change the number of disks from 3 to any number within the range of positive integers 1 through 9. Based on your programming skill level, with additional coding, you can change the program to screen print disks of any number your system has the memory and speed to accommodate.

The disk position array is initialized as follows:


	/*  Initialize disk positions.  */
	for( i = 0; i < 3; ++i )
	{
		for( j = 0; j < DISKS; ++j )
		{
			if( i == 0 )
			{
				pos[ i ][ j ] = j + 1;
			}else
			{
				pos[ i ][ j ] = EMPTY;
			}
		}
	}



The above creates the following array representation of the disk positions:

…..1…..2…..3
…..0…..0…..0
…..0…..0…..0



The initial disk positions are screen printed as follows:

	/*  Print initial disk positions.  */
	printf( "\n\n          A B C\n" );
	printf( "          - - -\n" );

	for( j = 0; j < DISKS; ++j )
	{
		printf( "%11.1d %d %d\n", pos[ 0 ][ j ], pos[ 1 ][ j ], pos[ 2 ][ j ] );
	}
	printf( "\n" );



The above creates the following screen printed output:

…..1…..0…..0
…..2…..0…..0
…..3…..0…..0



After the above initial position of the disks is printed, the following recursive call is made to begin the solution to the puzzle. The towers() function parameter list starts off with DISKS = number of disks to move = 3, source = 0, temporary = 1, and destination = 2. It will be easier for you to understand the puzzle solution algorithm if you play computer using pencil and paper and visualize the nesting of the recursive calls.

	towers( DISKS, 0, 1, 2 );



A common algorithm development strategy is divide and conquer.

After playing computer you will see the following pattern:


Step 1; make a legal move, moving the smallest disk clockwise.

Step 2; make a legal move; however, do not move the smallest disk.

Copy, past, build, and debug the example program and you will see the Step 1, Step 2 algorithm described above works great with 3 disks.

#define DISKS 3  /*  Number of disks.  */



Change the number of disks in the above code from 3 to any number within the range of positive integers 1 through 9 and see if the Step 1, Step 2 algorithm continues to work.

You can amaze your friends by using the Step 1, Step 2 algorithm to manually play and win the Towers of Hanoi puzzle!


IV. EXAMPLE PROGRAM

/*
	TOWERS OF HANOI
	C RECURSION TUTORIAL
	PART 3
*/

#include<ctype.h>     /*  Character Class Tests  */
#include<stdio.h>     /*  Standard I/O.          */
#include<stdlib.h>    /*  Utility Functions.     */

/*
	DECLARATIONS
*/

#define EMPTY 0  /*  Empty disk position.  */
#define DISKS 3  /*  Number of disks.  */

#define HEADER \
    "\n\n  TOWERS OF HANOI\n" \
	"  C RECURSION TUTORIAL\n" \
	"  PART 3\n\n" \
	"  \n"

/*
	GLOBAL VARIABLES
*/

int pos[3][DISKS];  /*  Disk position array, [rows][columns].  */

char code[3] = {'A', 'B', 'C'};  /*  Tower names.  */

/*
	FUNCTION PROTOTYPES
*/

void towers( int n, int source, int temporary, int destination );

void moveDisk( int source, int destination );

int main( int argc, char *argv[] )
{
	int i = 0;
	int j = 0;
	int hold = 0;

	printf( HEADER );

	printf( "\n\n  The Towers of Hanoi: %d Disks\n\n", DISKS );

	/*  Initialize disk positions.  */
	for( i = 0; i < 3; ++i )
	{
		for( j = 0; j < DISKS; ++j )
		{
			if( i == 0 )
			{
				pos[ i ][ j ] = j + 1;
			}else
			{
				pos[ i ][ j ] = EMPTY;
			}
		}
	}

	/*  Print initial disk positions.  */
	printf( "\n\n          A B C\n" );
	printf( "          - - -\n" );

	for( j = 0; j < DISKS; ++j )
	{
		printf( "%11.1d %d %d\n", pos[ 0 ][ j ], pos[ 1 ][ j ], pos[ 2 ][ j ] );
	}
	printf( "\n" );

	towers( DISKS, 0, 1, 2 );

	printf( "\n\n  To EXIT type 9 then press Enter:  " );
	scanf( "%d", &hold );

	return 0;
}
	
/*
	FUNCTION DEFINITIONS
*/

void towers( int n, int source, int temporary, int destination )
{
	if ( n == 1 )  /*  Base case.  */
	{
		moveDisk( source, destination );
	}else  
	{
		towers( n - 1, source, destination, temporary );
		moveDisk( source, destination );
		towers( n - 1, temporary, source, destination );
	}

	return;
}

void moveDisk( int source, int destination )
{
	int i = 0;
	int j = 0;

	/*  Determine source location.  */
	while( pos[ source ][ i ] == EMPTY )
	{
		i++;
	}

	/*  Determine destination location.  */
	while(( pos[ destination ][ j ] == EMPTY ) && ( j < DISKS ))
	{
		j++;
	}

	j -= 1;

	/*  Move disk.  */
	printf( "\n  Move disk #%d from %c to %c:\n\n",
		pos[ source ][ i ], code[ source ], code[ destination ] );
	pos[ destination ][ j ] = pos[ source ][ i ];
	pos[ source ][ i ] = EMPTY;

	/*  Print disk positions after move.  */
	printf( "\n\n          A B C\n" );
	printf( "          - - -\n" );

	for( j = 0; j < DISKS; ++j )
	{
		printf( "%11.1d %d %d\n", pos[ 0 ][ j ], pos[ 1 ][ j ], pos[ 2 ][ j ] );
	}
	printf( "\n" );

	return;
}



V. REFERENCES

The C Programming Language by Brian Kernighan and Dennis Ritchie (Englewood Cliffs, N.J.: Prentice-Hall, 1978).

The C Programming Language Second Edition by Brian Kernighan and Dennis Ritchie (Upper Saddle River, N.J.: Prentice-Hall PTR, 1988).


Is This A Good Question/Topic? 1
  • +

Page 1 of 1