Tower of Hanoi
In this game problem, there are n different sized disks. Each disk has a hole in the center so that it can be stacked on any of the 3 pegs say x, y and z. At the beginning of the game, disks are stacked on peg x in such a way that largest sized disk is at the bottom and smallest sized disk is on top. All these disks should be transferred from peg x to peg z using peg y.
Rule of the game:
First, only one disk may be moved at a time. Second, only topmost disk can be moved. Third, while transforming disks from source peg to the destination peg, no larger disk should be placed on the smaller one. Fourth, each disk must be stacked on any one of the pegs.
To solve Tower of Hanoi problem while following the above rules, following logic has to be applied recursively---
Move top (n-1) disks from peg x to peg y.
Move the nth disk from peg x to peg z.
Move (n-1) disks from peg y to peg z.
Example- If n=3, then there are 3 disks-disk 1 (smallest), disk2 and disk3 (largest), which are stacked on peg x in this sequence. [Disk3 is at the bottom and disk1 is at the top.]
Following movements of disks should occur---
1. Move disk1 from peg x to peg z [X -> Z].
2. Move disk2 from peg x to peg y [X -> Y].
3. Move disk1 from peg z to peg y [Z -> Y].
4. Move disk3 from peg x to peg z [X -> Z].
5. Move disk1 from peg y to peg x [Y -> X].
6. Move disk2 from peg y to peg z [Y -> Z].
7. Move disk1 from peg x to peg z [X -> Z].
Recursive definition of Tower of Hanoi in C language:
void t_o_h (char from, char to, char other, int n)
{
if (n = = 1)
printf ( " Move from %c to %c " , from, to);
else {
t_o_h (from, other, to, n-1);
t_o_h (from, to, other, 1);
t_o_h (other, to, from, n-1);
}
}
This coding can be explained below point wise.
Values of formal parameters are stored in runtime stack in the form of activation records. With every function call, an activation of the function is created. This activation is implemented as 2 parts - a static code segment containing the executable code and constants and an activation record (which is the dynamic part) containing local data, parameters, function result data and various other data items. It is this activation record which is pushed in system-defined stack (runtime stack), each time function is called. When function returns, popping of activation record occurs. During function execution, contents of activation record constantly change due to assignments made to local variables (formal parameters also behave as local variables). Hence, it is dynamic (details not discussed here). Tower of Hanoi shown here is recursive function which makes repeated calls to itself using modified parameter list for each call. The process pushes a series of activation records on the stack until the stopping condition (base criteria) is reached. The subsequent popping of activation records gives the recursive solution.
In the following points, F stands for from (source peg). T stands for to (destination peg). O stands for other (intermediate peg). n stands for number of disks. Each point represents function call/return. Points 1, 2, 4, 6, 9, 11, 12, 14 and 16 represent function call (push operation in runtime stack) and 3, 5, 7, 8, 10, 13, 15, 17 and 18 represent function return (pop operation in runtime stack). Pegs written in bold signify the output movements.
Start:
Initial values of F, T, O and n are X, Z, Y and 3 respectively.
1. Values of F, T, O and n are X, Y, Z and 2 respectively by function call t_o_h (from, other, to, n-1).
2. Values of F, T, O and n are X, Z, Y and 1 respectively by function call t_o_h (from, other, to, n-1).
3. Values of F, T, O and n are X, Y, Z and 2 respectively.
4. Values of F, T, O and n are X, Y, Z and 1 respectively by function call t_o_h (from, to, other, 1).
5. Values of F, T, O and n are X, Y, Z and 2 respectively.
6. Values of F, T, O and n are Z, Y, X and 1 respectively by function call t_o_h (other, to, from, n-1).
7. Values of F, T, O and n are X, Y, Z and 2 respectively.
8. Values of F, T, O and n are X, Z, Y and 3 respectively.
9. Values of F, T, O and n are X, Z, Y and 1 respectively by function call t_o_h (from, to, other, 1).
10. Values of F, T, O and n are X, Z, Y and 3 respectively.
11. Values of F, T, O and n are Y, Z, X and 2 respectively by function call t_o_h (other, to, from, n-1).
12. Values of F, T, O and n are Y, X, Z and 1 respectively by function call t_o_h (from, other, to, n-1).
13. Values of F, T, O and n are Y, Z, X and 2 respectively.
14. Values of F, T, O and n are Y, Z, X and 1 respectively by function call t_o_h (from, to, other, 1).
15. Values of F, T, O and n are Y, Z, X and 2 respectively.
16. Values of F, T, O and n are X, Z, Y and 1 respectively by function call t_o_h (other, to, from, n-1).
17. Values of F, T, O and n are Y, Z, X and 2 respectively.
18. Values of F, T, O and n are X, Z, Y and 3 respectively.
Stop
Khushbu Arora
D/o Dr. Bimal K. Arora
BSc (Ewing Christian College, Allahabad), A-Level (s/w) from DOEACC, India and, OCP (Oracle Forms Developer Certified Professional).
Currently doing MCA (Master of Computer Application) from Ewing Christian Institute of Management and Technology, Allahabad.
AP - A popular local TV anchorwoman who had a small part in the Bush biopic "W" was in critical condition Monday after being beaten in her home. Police questioned whether she could have been targeted.
