C Program To Solve Tower of Hanoi without Recursion
Learn How To Solve Tower of Hanoi without Recursion in C Programming Language. This Non Recursive C Program makes use of an Iterative method using For Loop to solve Tower of Hanoi Problem. The Tower of Hanoi Algorithm in Data Structures is a very famous Interview Question for Beginners. The C Program For Tower of Hanoi Program using Iteration can be solved by using For, While and Do While Loop.
To know more about Tower of Hanoi, you can read this guide: Tower of Hanoi Problem in C Programming
If you try to compile this C Program for Tower of Hanoi without using Recursion in Linux, you will get the following error:
1 2 3 | tmp/cc0zu8gQ.o: In function `tower_of_hanoi': test.c:(.text+0x2cd): undefined reference to `pow' collect2: error: ld returned 1 exit status |
This is because the pow() method cannot be found in the library files. To overcome this error, you will have to explicitly include the math.h header file. Compile the program using the following command:
1 | gcc test.c -lm |
Also Read: Tower of Hanoi in C using Recursion
C Program To Solve Tower of Hanoi without Recursion
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | #include <stdio.h> #include <limits.h> #include <stdlib.h> #include <math.h> struct Stack_Structure { int top; int *array; int max; }; struct Stack_Structure* createStack(int max) { struct Stack_Structure* stack_object = (struct Stack_Structure*)malloc(sizeof(struct Stack_Structure)); stack_object -> max = max; stack_object -> top = -1; stack_object -> array = (int*)malloc(stack_object -> max*sizeof(int)); return stack_object; } int isEmpty(struct Stack_Structure* stack_object) { return (stack_object->top == -1); } int isFull(struct Stack_Structure* stack_object) { return (stack_object->top == stack_object->max - 1); } void display_shift(char fromTower, char toTower, int disk) { printf("Move Disk %d from \'%c\' to \'%c\'\n", disk, fromTower, toTower); } void add_element(struct Stack_Structure *stack_object, int item) { if(isFull(stack_object)) { return; } stack_object -> array[++stack_object -> top] = item; } int remove_element(struct Stack_Structure* stack_object) { if(isEmpty(stack_object)) { return INT_MIN; } return stack_object -> array[stack_object -> top--]; } void shift_Disks(struct Stack_Structure *source_tower, struct Stack_Structure *destination_tower, char source, char destination) { int tower1 = remove_element(source_tower); int tower2 = remove_element(destination_tower); if(tower1 == INT_MIN) { add_element(source_tower, tower2); display_shift(destination, source, tower2); } else if(tower2 == INT_MIN) { add_element(destination_tower, tower1); display_shift(source, destination, tower1); } else if(tower1 > tower2) { add_element(source_tower, tower1); add_element(source_tower, tower2); display_shift(destination, source, tower2); } else { add_element(destination_tower, tower2); add_element(destination_tower, tower1); display_shift(source, destination, tower1); } } void tower_of_hanoi(int limit, struct Stack_Structure *source_tower, struct Stack_Structure *temporary_tower, struct Stack_Structure *destination_tower) { int count, shift; char destination = 'D', source = 'S', temporary = 'A'; if(limit % 2 == 0) { char x = destination; destination = temporary; temporary = x; } shift = pow(2, limit) - 1; for(count = limit; count >= 1; count--) { add_element(source_tower, count); } for(count = 1; count <= shift; count++) { if(count%3 == 1) { shift_Disks(source_tower, destination_tower, source, destination); } else if(count%3 == 2) { shift_Disks(source_tower, temporary_tower, source, temporary); } else if(count%3 == 0) { shift_Disks(temporary_tower, destination_tower, temporary, destination); } } } int main() { int limit; struct Stack_Structure *source_tower, *destination_tower, *temporary_tower; printf("\nEnter The Number of Disks:\t"); scanf("%d", &limit); printf("\nSequence of Disk Moves:\n\n"); source_tower = createStack(limit); temporary_tower = createStack(limit); destination_tower = createStack(limit); tower_of_hanoi(limit, source_tower, temporary_tower, destination_tower); printf("\n"); return 0; } |
Must Read: C Program For FCFS Algorithm
Output
If you have any compilation errors or doubts in this C Program for Tower of Hanoi without Recursion, let us know about in the Comment Section below.
Here’s another method to solve the Tower of Hanoi puzzle.
It’s a mechanical solution which doesn’t use recursion. Try it out using
3 or 4 coins of different sizes.
Arrange the three rods to form a triangle.
Starting position (where X, Y and Z are different size coins):
empty rod
Z
YYY
XXXXX
starting rod destination rod
Finished position:
empty rod
Z
YYY
XXXXX
starting rod destination rod
Move the smallest disk on every other turn — always in the same
direction. On the remaining turns make the only valid move that does
not involve the smallest disk.
The following rule will make sure that the tower of disks end up on the
third rod: If the number of disks in the puzzle is an odd number then
always move the smallest disk counter-clockwise around the triangle; if
the number of disks in the puzzle is an even number then always move the
smallest disk clockwise around the triangle.
With this solution the even numbered disks move around the triangle in
one direction while the odd numbered disks move around the triangle in
the opposite direction.
Thanks a lot for providing us a different angle to Tower of Hanoi Problem in C Language.
I think Recursion is much better instead of iterations since the recursive tower of hanoi algorithm is much simple to understand and looks efficient as well.
Tower of Hanoi with Iteration method is much more understandable than the Recursive approach. Thanks!
Thanks for the code iterative code for Tower of Hanoi. Thanks