Tower of Hanoi without Recursion C Program

By | July 30, 2016

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:

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:

gcc test.c -lm

Also Read: Tower of Hanoi in C using Recursion

C Program To Solve Tower of Hanoi without Recursion

#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

C Program To Solve Tower of Hanoi without Recursion and Iterative For Loop

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.

5 thoughts on “Tower of Hanoi without Recursion C Program

  1. c programmer

    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.

    Reply
  2. Rohan Kush

    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.

    Reply
  3. Rohan Gaikwad

    Tower of Hanoi with Iteration method is much more understandable than the Recursive approach. Thanks!

    Reply

Let's Discuss