Tower of hanoi Help...

[Rahul.menon]

#include<stdio.h>
#include<conio.h>
#include<math.h>
int a[70]; //src disk array
int b[70];//temp disk array
int c[70];//tar disk array
int val, srcval=1,tempval=0,tarval=0;
int es[3] = {1,1,0}; //array to decide iteration of disks from and to
int et[3] = {1,0,1};
int etr[3]= {0,1,1};
int os[3] = {1,1,0};
int ot[3] = {0,1,1};
int otr[3]= {1,0,1};
void find();//to keep the update of elements on top(srcval,tempval,tarval)
void move(int[],int[]);//to move from src to tar
void main()
{
 int i1 =0;
 long int j1;
 int *src;
 int *temp;
 int *tar;
 printf("Enter The number of disks");
 scanf("%d",&val);

 if(val % 2 == 0) //even no of disk
 {
	src =  es; 
	temp = et;
	tar = etr;
 }
 else   //odd no of disk
  {
	 src = os;
	 temp = ot;
	 tar = otr;
  }
  for(j1 = 1;j1<=val;j1++)
  {
	 a[j1-1]=j1;
	 b[j1-1]=0;
	 c[j1-1]=0;
  }
  for(j1 = 1;j1<=(long)(pow(2.0,val)-1);j1++)
  {
	getch();
	 if(src[i1]==1&&tar[i1]==1)
	  {
		 if(srcval > tarval )
		 {
		  if(tarval == 0)
		  {
		  printf("Source to target");
				  move(a,c);
		  }
		  else{
				  printf("target to source");
				  move(c,a); }
		 }
		 else
		 {

		  if(srcval==0){
			  printf("Target to source");
				  move(c,a);
				  }
				  else{
				  printf("source to target");
				  move(a,c);
				  }
		 }

	  }

	  if(src[i1]==1&&temp[i1]==1)
		  {
			if(srcval>tempval)
			{

			if(tempval==0)
			  {
				  printf("source to temperory");
				  move(a,b);
			  }
				  else
				  {
				  move(b,a);
					printf("temperory to source ");
				  }
			}
				else
				{
				if(srcval == 0)
				{
				  move(b,a);
					printf("temperory to source ");
				}
				  else
				  {
				  move(a,b);
				  printf("source to temperory");
				  }
				}
		  }
		if(temp[i1]==1&&tar[i1]==1)
		  {
				if(tempval>tarval )
				{
				  if(tarval==0)
				  {
				  printf("temperory to target");
				  move(b,c);
				  }
				  else
				  {
				  printf("target to temperory");
				  move(c,b);
				  }
				}
				else
				{
				  if(tempval==0)
				  {
					 printf("target to temperory");
					move(c,b);
				  }
				  else
				  {
					 printf("temperory to target");
				  move(b,c);
				  }

				}

		  }

	  if(i1<2)
	  i1++;
	  else
	  i1=0;

	 // getch();
	  printf("\n");
	  }
}

void find()//find and update values of srcval,tempval,tarval..
{


	int m,n=val+1,n1=0;
	for(m=0;m<=val-1;m++)
	{
		 if(a[m] < n && a[m]!=0)
		 {
			n = a[m];
			n1++;
		 }
	 }
		n = n1<1?0:n;
		srcval = n;
		n=val+1;
		n1=0;
	for(m=0;m<=val-1;m++)
		 {
			if(b[m] < n && b[m]!=0)
			{
			  n1++;
				n = b[m];
				}
		  }
		  n = n1<1?0:n;
		  tempval = n;
		  n=val+1;
		  n1=0;
	for(m=0;m<=val-1;m++ )
		{
		 if(c[m] < n&& c[m]!=0)
		 {
			n = c[m];
			n1++;
		 }
		}
		n = n1<1?0:n;
		tarval = n;
}


void move(int grt[], int sml[])//move from target to src
{
	int i=0,j=0;
	int m,n=val+1,n1=0;

	for(m=0;m<=val-1;m++)
	{
		 if(grt[m] < n && grt[m]!=0)
		 {
			n = grt[m];
			i=m;
			n1++;

		 }
	}

	 n = n1<1?0:n;
	 grt[i]=0;
	for(m=0;m<=val-1;m++)
	 {
		if(sml[m]==0)
		{
		  sml[m]=n;
			break;
		}
	 }
	 find();
}

Could any one please help with the iterative soln of hanoi tower.
without using printf("Move disk %d from tower%d to tower%d\n",i,d=(d+(i&1?dir:1-dir))%3+1,d) like abstract algorithm. i have manually iterated array. is there any better way out.

[Adak]

The key to the game is that if you are at any time, needing to move a stack or substack, you will use the following:

1) if the stack/sub stack has an odd number of disks, you'll move the disk in question to the goal needle

2) otherwise, you'll move the disk to the non-goal needle

This IS a classic recursive program example, but it can be done iteratively, of course. Step through your code with say, two disks, and make sure that's working right. Then, step up to three disks, and go from there.

Find out exactly where it's failing - and what logic is causing it.

[Rahul.menon]

The key to the game is that if you are at any time, needing to move a stack or substack, you will use the following:

1) if the stack/sub stack has an odd number of disks, you'll move the disk in question to the goal needle

2) otherwise, you'll move the disk to the non-goal needle

This IS a classic recursive program example, but it can be done iteratively, of course. Step through your code with say, two disks, and make sure that's working right. Then, step up to three disks, and go from there.

Find out exactly where it's failing - and what logic is causing it.

The Code is working but i want to really shorten it either by better logic other than the abstract code or recursive code..

[Adak]

Well it shouldn't be hard to shorten it with a recursive program. ;)

This, from a guy with perhaps the longest iterative program (very visual despite just a text window).

The thing you have to know is that the recursive function uses a "dance". The "from" needle, and the "to" needle, move back and forth, like crazy.

Then there is the number 6. Six shoe horns beautifully into this function, because the needles have numbers of 1, 2, or 3. So six minus the from needle, minus the to needle of the last move -- Well, hot damn! it gives you the number of the new "from" needle. << and that's some shit! >>

Since this "dance" works, it means that every call to the (I'll call it Hanoi function), has a double recursive call to itself.

Now you know why I wrote my version, iteratively. ;)

In pseudo code it looks like this:

i=1, j=2
Hanoi(number of disks, i, j, and moveNum) { //all int's
  moveNum++
  Hanoi(n - 1, i, 6 - i - j, moveNum)
  print moveNum. move i to j
  if(moveNum mod 4 == 0) 
    print newline
  Hanoi(n - 1, 6 - i - j, j, moveNum)
}

Get the number of disks it's to start with, in main(), and call Hanoi() and off you go.

My caveats to you are:

1) The recursive version I have, is in another language, so I'm interpreting this a bit. I just ran it however, and it appears to be Ok.

2) Last time I worked with this, the game was called Tower of Brahmam, before Hanoi was made popular for it's name. Yeah, decades ago.

But it is undeniably short! ;)

[Pavan_Sharma]

I m not agree with such complexity.....

[Pavan_Sharma]

I will make modification after some hour

[Rahul.menon]

I will make modification after some hour

Great if u could come up with short and simple one

[Shift-Stop]

Also a few decades ago, I too wrote this program, but was on a team to write a new Language - so I added a few 'extras' to get me thru.

It was Tower of Hanoi, and Carter was our Leader.

Adax is Right to use pseudo code first as this WILL get a little tricky as you get into it.

I still use RATFOR; "a Fortran preprocessor, by its author, Brian W. Kernighan"
but any pseudo language will work fine for this.

Mine is still in 'Test' phase, but I'm expecting it to finish it's first run-thru soon.

My point is this:
Write it in Pseudo code FIRST -
and make sure you 'cover your bases'
THEN code it.

--
Shift-Stop