The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
No disk may be placed on top of a smaller disk.

Recursive solution

The key to solving a problem recursively is to recognize that it can be broken down into a collection of smaller sub-problems to each of which the same general procedure applies, and the total solution is then found in some simple way from those sub-problems' solutions. Each of thus created sub-problems being "smaller" guarantees the base case(s) will eventually be reached.

1. label the pegs A, B, C
2. let n be the total number of discs
3. number the discs from 1 (smallest, topmost) to n (largest, bottom-most)

Assuming all n disks are distributed in valid arrangements among the pegs; assuming there are m top disks on a source peg, and all the rest of the disks are larger than m so can be safely ignored; to move m discs from a source peg to a target peg using a spare peg, without violating the rules:

1. move m−1 discs from the source to the spare peg, by the same general procedure. Rules are not violated, by assumption. This leaves the disk m as a top disk on the source peg
2. move the disc m from the source to the target peg, which is guaranteed to be a valid move, by the assumptions — a simple step
3. move the m−1 discs that we've just placed on the spare, from the spare to the target peg by the same general procedure, so they are placed on top of the disc m without violating the rules
4. the base case being, to move 0 disks, do nothing.

/*
Description: 
	Hanoi Tower 
			
Author:  Liutong Xu
Date: 2016/11/20
*/

#include<stdio.h>

void hanoi(int n,char from,char to,char temp);
int main()
{
	int n;
	char from = 'A';
	char to = 'C';
	char temp ='B';
	
	n = 3;
	//scanf("%d",&n);
	
	hanoi(n,from,to,temp);	
	
	return 0;
}

void hanoi(int n,char from,char to,char temp)
{
	if (n == 1)
		printf("move disk from %c to %c\n", from, to);
	else
	{
		hanoi(n-1,from,temp,to);
		printf("move disk from %c to %c\n", from, to);
		hanoi(n-1,temp,to,from);		
	}
}

stdout

move disk from A to C
move disk from A to B
move disk from C to B
move disk from A to C
move disk from B to A
move disk from B to C
move disk from A to C

Iterative solution

You have no rights to post comments