I know that more formally it may be proved with induction but it is enough to get an idea. So after every three moves, we can go with the other three moves and so on till we exhaust all our moves. To make space we must have a legal movement b/w auxiliary and destination pole.Īfter these three trivial steps, if we run through the algorithm we will notice that after every three moves, the destination pole is in a state that it can accept a new disk. We can think of them by starting the trivial cases when i = 1, 2 and 3.įor i = 1, since we have appropriately decided the sense of movement in step 2 of algorithm, we can safely make a legal movement b/w source and destination.įor i = 2, since the auxiliary pole is empty we can shift the disk to it and have a legal movement b/w source and auxiliary pole.įor i = 3, we need to make space for the remaining disks of source so that they could be shifted to the destination. Why the sub cases a, b, c of step 3 of the algorithm work? Then move the Nth disc from source tower to destination tower then again recursively move N 1 disc from intermediate tower to destination tower. We recursively move N 1 disc from the source tower to the intermediate tower. When the top disk of one pole is smaller than the other we move the smaller of two disks to the pole with larger disk. How do you solve the Tower Of Hanoi Puzzle In programming, we solve this puzzle with the help of recursion. When one of the two poles is empty we must move the disk from non empty pole to the empty pole. no larger disk should be placed on smaller disk and we must move only the top disk at a time. The legal movement must respect the constraints of the TOH problem i.e. The next problem, however, is to solve the Hanoi puzzle without recursion. Legal movement of top disk b/w auxiliary pole and destination pole. For n 3, for instance, the solution is just: 1 to 3, 1 to 2, 3 to 2, 1 to 3, 2 to 1, 2 to 3, 1 to 3 where a to b indicates moving the top disk on peg a to peg b. I guess it is not correct as the number of moves are not 2n - 1, for eg, for 3 disks to be moved, it has to generate 7 moves. Legal movement of top disk b/w source pole and auxiliary pole. I have written the following code for Towers of Hanoi problem using non recursive approach. Legal movement of top disk b/w source pole and destination pole. for i = 1 to number of moves calculate in step 1: It is used to demonstrate the simple rules to solve a. (This is to ensure that moves are in clockwise for even disks and anticlockwise for odd disks)ģ. Tower Of Hanoi (TOH) is a mathematical puzzle which can be easily solved by recursive algorithm. If numDisks is even then interchange the destination pole with the auxiliary pole. With the help of above two observations we can devise the algorithm as: TowerOfHanoi(source, destination, auxiliary, numDisks)ġ. Then for the even number of disks the movement of disks will start in clockwise direction and if the number of disks is odd then the movement will start in anticlockwise direction. This can be evaluated by the recurrence of the recursive solution. of moves required are $2^n - 1$ where n is the number of disks. ![]() The iterative solution can be figured out analyzing the recursive solution.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |