C Program to Implement Tower of Hanoi Problem
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 puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
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.
With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2^n – 1, where n is the number of disks.
Solution
The puzzle can be played with any number of disks, although many toy versions have around seven to nine of them. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n – 1, where n is the number of disks.
Iterative solution
A simple solution for the toy puzzle: Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest number of moves.
Simpler statement of iterative solution
Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:
For an even number of disks:
make the legal move between pegs A and B
make the legal move between pegs A and C
make the legal move between pegs B and C
repeat until complete
For an odd number of disks:
make the legal move between pegs A and C
make the legal move between pegs A and B
make the legal move between pegs C and B
repeat until complete
In each case, a total of 2n-1 moves are made.
Equivalent iterative solution
Another way to generate the unique optimal iterative solution:
Number the disks 1(ONE) through n (largest to smallest).
If n is odd, the first move is from the Start to the Finish peg.
If n is even, the first move is from the Start to the Using peg.
Now, add these constraints:
No odd disk may be placed directly on an odd disk.
No even disk may be placed directly on an even disk.
Never undo your previous move (that is, do not move a disk back to its immediate last peg).
Considering those constraints after the first move, there is only one legal move at every subsequent turn.
The sequence of these unique moves is an optimal solution to the problem equivalent to the iterative solution described above.
Recursive solution
A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. For example:
label the pegs A, B, C — these labels may move at different steps
let n be the total number of discs
number the discs from 1 (smallest, topmost) to n (largest, bottommost)
To move n discs from peg A to peg C:
move n−1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n−1 discs from B to C so they sit on disc
The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial. This approach can be given a rigorous mathematical formalism with the theory of dynamic programming,and is often used as an example of recursion when teaching programming.
#include<stdio.h>
#include<math.h>
void hanoi(int x, char from,char to,char aux)
{
if(x==1)
{
printf("Move Disk From %c to %cn",from,to);
}
else
{
hanoi(x-1,from,aux,to);
printf("Move Disk From %c to %cn",from,to);
hanoi(x-1,aux,to,from);
}
}
int main(void)
{
int disk;
printf("Enter the number of disks you want to play with:");
scanf("%d",&disk);
double moves=pow(2,disk)-1;
printf("nThe No of moves required is=%g n",moves);
hanoi(disk,'A','C','B');
}
Recent Comments