TOWERS OF HANOI_problemsolutionandexplanationwithalgorithm.pptx

Algorithm.. visual representation and solution to the towers of Hanoi problem

1. Tower Of Hanoi Algorithm There is one history behind Tower Of Hanoi is, It is originated from an ancient legend from Vietnam, according to which a group of monks is moving around a tower of 64 disks of different sizes according to certain rules. The legend says that, when the monks will have finished moving around the disks, the end of the world will come. The Tower of Hanoi is a mathematical Puzzle that consists of three towers(pegs) and multiple disks. Initially, all the disks are placed on one rod. And this disks are arranged on one over the other in ascending order of size. Our Objective is to move all disks from initial tower to another tower without violating the rule.

2. The conditions for moving the disks are: The rules according to which the disks have to be moved in Tower of Hanoi are the following Initially, the disks are placed in Increasing Order in size on Tower 1 from top to bottom. The objective is to move them to tower 2, making also use of an auxiliary tower 3. All disks (except the one to be moved) have to be on one of the three towers. Only one disk is possible to move at a time. The only top disk can be moved i.e. taking from the top of one tower and placing on the top of another tower. A larger disk can never be placed on a smaller disk.

3. Tower of Hanoi mathematical puzzle that has n disks with 3 towers can be solved in minimum 2 n −1  steps For an example A puzzle with 3 disks has taken 2 3  - 1 = 7  steps. Algorithm For Tower of Hanoi Puzzle In Tower Of Hanoi puzzle we have three towers and some disks. We have to move this disk from intial tower to destination tower using aux tower. For an example lets take we have two disks and we want to move it from source to destination tower.

4. So the approach we will follow First, we will move the top disk to aux tower. Then we will move the next disk (which is the bottom one in this case) to the destination tower. And at last, we will move the disk from aux tower to the destination tower. Similarly if we have n number of disk then our aim is to move bottom which is disk n from source to destination. And then put all other (n-1) disks onto it. Steps we will follow is Step 1 − Move n-1 disks from source to aux Step 2 − Move nth disk from source to dest Step 3 − Move n-1 disks from aux to dest

5. Representation of How Tower of Hanoi works Let’s see the below example where we have three disks that have to move in the destination tower which is the middle one with the help of the auxiliary tower.

6. Pseudo code For Tower of Hanoi Puzzle START Procedure TOH(disk, source, dest, aux) IF disk == 1, THEN move disk from source to dest ELSE TOH(disk - 1, source, aux, dest) // Step 1 moveDisk(source to dest) // Step 2 TOH(disk - 1, aux, dest, source) // Step 3 END IF END Procedure STOP

7. C Program to Implement TOH puzzle #include <stdio.h> void hanoi(int n, char from, char to, char via) { if(n == 1) { printf("Move disk 1 from %c to %c\n", from, to); } else { hanoi(n-1, from, via, to); printf("Move disk %d from %c to %c\n", n, from, to); hanoi(n-1, via, to, from); } } int main() { int n = 3; char from = 'A'; char to = 'B'; char via = 'C'; //calling hanoi() method hanoi(n, from, via, to); } OUTPUT: Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C