Towers of Hanoi- Non Recursive Approach

Rating 4.46 out of 5
[?]

In the second year of my engineering our Data Structure teacher gave some of us the task to develop a program that solves the Towers of Hanoi puzzle, without the use of recursion in the final semester lab exam. Well no one (except me :P) could develop the program, not because its tough but because many people do not have the concept of recursion clear in their minds and how it is actually handled by the computer itself; even if the concept is clear they’ll not know how to convert it because of the sheer complexity of the puzzle.

If you stumbled across this link searching for the “recursive” algorithm, I can help you guys too, even though you can find the solution to this everywhere. Just a little heads up, “A” – Auxiliary Peg, “B” – Beginning Peg, “E” – End Peg

#include<iostream>
#include<stdlib.h>
using namespace std;
void tower(int num,char Beg,char Aux,char End)
{

if(num>=1)
{
tower(num-1,Beg,End,Aux);
cout<<"Move disk "<<num<<" from "<<Beg<<" to "<<End<<endl;
tower(num-1,Aux,Beg,End);
}
}
int main()
{

int N;
cout<<"Enter the number of disk: ";
cin>>N;
tower(N,'B','A','E');
}

Taking the same nomenclature and developing the Non-recursive version of the same. We’ll be requiring a stack and a couple of functions like PUSH and POPANDTEST to handle the push and pop operations that we’ll take up. If you are attempting to find the solution of this problem you must be aware that recursion can be simulated best using a STACK. The code is very simple and if you read it, two times maximum, you’ll get hold of it.

#define MAXSTACK 100
struct details{
int number;
char beg;
char end;
char aux;
};
struct stack{
int top;
struct details item [MAXSTACK];
};
void push(struct stack *s, struct details *current)
{
if(s->top==MAXSTACK-1)
{cout<<"Overflow";
exit(1);}
else
s->item[++(s->top)]= *current;
return;
}
void popandtest(struct stack *s, struct details *current,int *flag)
{
if(s->top==-1){
*flag=1;
return;}
*flag=0;
*current= s->item[s->top--];
return;
}

//towers of hanoi without recursion
void towers(int n, char begpeg, char endpeg, char auxpeg)
{
struct stack s;
struct details current;
int flag;
char temp;
s.top=-1;
current.number=n;
current.end=endpeg;
current.beg=begpeg;
current.aux=auxpeg;
while(1){
while(current.number!=1)
{
push(&s,&current);
--current.number;
temp=current.end;
current.end=current.aux;
current.aux=temp;
}
cout<<"Move Disc 1 from "<<current.beg<<" to "<<current.end<<endl;
popandtest(&s,&current,&flag);
if(flag==1)
return;
cout<<"Move Disc "<<current.number<<" from "<<current.beg<<" to "<<current.end<<endl;
--current.number;
temp=current.beg;
current.beg=current.aux;
current.aux=temp;
}
}
int main()
{
int N;
cout<<"Enter the number of disk: ";
cin>>N;
towers(N,'B','E','A');
return 0;
}

This will do it, as you can see the code is very simple, all it requires is a little bit of awareness of the concept and patience. As you must have noticed that the program is written in C++, just because there is the ease of inputing and outputting. The program can be made in C with a little bit of change. You are free to use the code I have written but I’ll advise you to write one yourself. In case of doubts and clarifications do not hesitate to ask.

Cheers 😀

Anshuman

About Anshuman

Computer Engineer ... MBA .. Endurance Runner ... Physics Geek ... Genius
Bookmark the permalink.

7 Comments


  1. Thanks buddy … you are genious ….


  2. Hi Anshuman. I’m clear with the concept of recursion but still I find it difficult to understand tower of Hanoi problem. I don’t know why, but somehow I’m unable to visualize the picture. To understand a program, I always need to get the step-by-step picture of every program-instruction motioning in my mind which I’m unable to so, in this case. Can you refer me to a source where I can fix this, or can you produce out a post, video or something on this? See if you can help me out.


  3. Wow, this is amazing


  4. dude!!you wrote the main() function twice. ;p.great coding though 😀

Liked it? Share Your Thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.