dev-cpp-users

RE: [Dev-C++] reg-Knight's tour problem

[Santiago P. C. <San...@yd...>]

Hi to *,

There's NO compiler defect (with this issue), so... Don't panic! ;o)

The variables 'i' & 'j' are class' members, defined on line:

>      int row_loc,pos,i,j;

Just my 2 cents, regards
Santy

-----Original Message-----
From: Ioannis Vranos [mailto:no...@ya...] 
Sent: Thursday, March 07, 2002 2:21 PM
To: Dev-C++
Subject: RE: [Dev-C++] reg-Knight's tour problem


> -----Original Message-----
> From: dev...@li...
> [mailto:dev...@li...] On Behalf 
> Of Mohammed Riyaz
> Sent: Thursday, March 07, 2002 2:00 PM
> To: dev...@li...
> Subject: [Dev-C++] reg-Knight's tour problem
> 
> 
> hey,
> I had a look at the code sent in. Am new to programming, my
> code sux when 
> compared to that. :D .If any one of you cud fix this code 
> ,help me out. -Riyaz
> 
> #include <iostream.h>
> #include <stdlib.h>

Useless
> #include <process.h>

Pre-ANSI header file declaration


> class knight
>      {
>      int chess[8][8],location[65][10],denied[64];
>      int row_loc,pos,i,j;
>      public:
>      knight();
>      void assignment(void);
>      int value(int);
>      void refresh(void);
>      int append(int ,int);
>      };
> knight::knight(void)
>      {
>      row_loc=-1;
>      i=j=0;
>      for(int m=0;m<8;m++)
>           for(int n=0;n<8;n++)
>                chess[m][n]=0;
>      for(int m=0;m<65;m++)
>           for(int n=0;n<10;n++)
>                location[m][n]=0;
>      for(int m=0;m<64;m++)
>           denied[m]=99;
>      assignment();
>      }
> void knight::assignment(void)
>      {
>      chess[i][j]=1;


Where are i, j defined? Strangely it compiles in MINGW32!!!! (compiler
defect).


>      refresh();
>      pos=value(j+(8*i));
>      i=pos/8;
>      j=pos%8;

>      assignment();


// Recursion never ends!


>      }
> int knight::value(int val)
>      {
>      row_loc++;
>      int temp=1;
>      int lock,ii,jj;
>      location[row_loc][0]=val;
>      ii=val/8;
>      jj=val%8;
>      if(jj==0)
>           {
>           if(ii>=1)
>                {
>                if(ii>=2)
>                     {lock=append(val-15,temp);if(lock==0) {temp++;}}
>                lock=append(val-6,temp);if(lock==0) {temp++;}
>                }
>           if(ii<=6)
>                {
>                if(ii<=5)
>                     {lock=append(val+17,temp);if(lock==0) {temp++;}}
>                lock=append(val+10,temp);if(lock==0) {temp++;}
>                }
>           }
>      if(jj==7)
>           {
>           if(ii>=1)
>                {
>                if(ii>=2)
>                     {lock=append(val-17,temp);if(lock==0) {temp++;}}
>                lock=append(val-10,temp);if(lock==0) {temp++;}
>                }
>           if(ii<=6)
>                {
>                if(ii<=5)
>                     {lock=append(val+15,temp);if(lock==0) {temp++;}}
>                lock=append(val+6,temp);if(lock==0) {temp++;}
>                }
>           }
>      if(jj==1)
>           {
>           if(ii>=1)
>                {
>                if(ii>=2)
>                     {
>                     lock=append(val-15,temp);if(lock==0) {temp++;}
>                     lock=append(val-17,temp);if(lock==0) {temp++;}
>                     }
>                lock=append(val-6,temp);if(lock==0) {temp++;}
>                }
>           if(ii<=6)
>                {
>                if(ii<=5)
>                     {
>                     lock=append(val+17,temp);if(lock==0) {temp++;}
>                     lock=append(val+15,temp);if(lock==0) {temp++;}
>                     }
>                lock=append(val+10,temp);if(lock==0) {temp++;}
>                }
>           }
>      if(jj==6)
>           {
>           if(ii>=1)
>                {
>                if(ii>=2)
>                     {
>                     lock=append(val-15,temp);if(lock==0) {temp++;}
>                     lock=append(val-17,temp);if(lock==0) {temp++;}
>                     }
>                lock=append(val-10,temp);if(lock==0) {temp++;}
>                }
>           if(ii<=6)
>                {
>                if(ii<=5)
>                     {
>                     lock=append(val+17,temp);if(lock==0) {temp++;}
>                     lock=append(val+15,temp);if(lock==0) {temp++;}
>                     }
>                lock=append(val+6,temp);if(lock==0) {temp++;}
>                }
>           }
>      if(jj>1 && jj<6)
>           {
>           if(ii>=1)
>                {
>                if(ii>=2)
>                     {
>                     lock=append(val-17,temp);if(lock==0) {temp++;}
>                     lock=append(val-15,temp);if(lock==0) {temp++;}
>                     }
>                lock=append(val-10,temp);if(lock==0) {temp++;}
>                lock=append(val-6,temp);if(lock==0) {temp++;}
>                }
>           if(ii<=6)
>                {
>                if(ii<=5)
>                     {
>                     lock=append(val+15,temp);if(lock==0) {temp++;}
>                     lock=append(val+17,temp);if(lock==0) {temp++;}
>                     }
>                lock=append(val+6,temp);if(lock==0) {temp++;}
>                lock=append(val+10,temp);if(lock==0) {temp++;}
>                }
>           }
>           lock=append(-1,temp);
>           code:
>           if(location[row_loc][1]==-1)
>                {
>                ii=location[row_loc][0]/8;
>                jj=location[row_loc][0]%8;
>                chess[ii][jj]=0;
>                row_loc--;
>                if(row_loc<0) {cout<<"NO 
> SOLUTION";system("pause");exit(0);}
>                for(int m=1;m<9;m++)
>                     location[row_loc][m]=location[row_loc][m+1];
>                goto code;
>                }
>           return location[row_loc][1];
>      }
> void knight::refresh(void)
>      {
>      int l,tot;
>      l=tot=0;
>      for(int m=0;m<64;m++)
>           denied[m]=99;
>      for(int m=0;m<8;m++)
>           {
>           for(int n=0;n<8;n++)
>                {
>                if(chess[m][n]==1)
>                     {
>                     if(l==63)
>                          {
>                          cout<<"RESULT :"<<endl;
>                          for(int k=0;k<64;k++)
>                               cout<<denied[k]<<" ";
>                          system("pause");
>                          }
>                     tot=n+(8*m);
>                     denied[l]=tot;
>                     l++;
>                     }
>                }
>           }
>      }
> int knight::append(int val1,int temp1)
>      {
>      int lock=0;
>      for(int m=0;m<64;m++)
>           if(denied[m]==val1)
>                {lock=1;break;}
>      if(!lock)
>           location[row_loc][temp1]=val1;
>      return lock;
>      }
> void main()
>      {knight k;}

int main()


Ioannis
 
* Ioannis Vranos
* Programming pages: http://www.noicys.d2g.com
* Alternative URL: http://run.to/noicys


_______________________________________________
Dev-cpp-users mailing list
Dev...@li...
https://lists.sourceforge.net/lists/listinfo/dev-cpp-users

--------------------------------------------------------------------------------------
This message and any files transmitted with it are confidential and intended solely 
for the use of the individual or entity to whom they are addressed. No confidentiality 
or privilege is waived or lost by any wrong transmission. 
If you have received this message in error, please immediately destroy it and kindly 
notify the sender by reply email.
You must not, directly or indirectly, use, disclose, distribute, print, or copy any 
part of this message if you are not the intended recipient. Opinions, conclusions and 
other information in this message that do not relate to the official business of 
People Communications S.A. shall be understood as neither given nor endorsed by it. 
--------------------------------------------------------------------------------------

RE: [Dev-C++] reg-Knight's tour problem

[Mohammed R. <p_m...@ho...>]

hey ioannis;
The variables i,j are members of the class. Why do you say recursion never 
end. The function assignment calls the other functions 'refresh', 'value'
in the line

refresh();
pos=value(j+(8*i));

hence when the this situation (given below)arises in the function value, the 
program wil hald and hence the recursion ends there.

if(row_loc<0) {cout<<"NO SOLUTION";system("pause");exit(0);}

(or)

when the situation
if(l==63)
                          {
                          cout<<"RESULT :"<<endl;
                          for(int k=0;k<64;k++)
                               cout<<denied[k]<<" ";
                          system("pause");
                          exit(0);
                          }
in refresh function is encountered the recursion ends.
-Riyaz


>From: "Ioannis Vranos" <no...@ya...>
>To: "Dev-C++" <dev...@li...>
>Subject: RE: [Dev-C++] reg-Knight's tour problem
>Date: Thu, 7 Mar 2002 15:20:47 +0200
>
> > -----Original Message-----
> > From: dev...@li...
> > [mailto:dev...@li...] On Behalf
> > Of Mohammed Riyaz
> > Sent: Thursday, March 07, 2002 2:00 PM
> > To: dev...@li...
> > Subject: [Dev-C++] reg-Knight's tour problem
> >
> >
> > hey,
> > I had a look at the code sent in. Am new to programming, my
> > code sux when
> > compared to that. :D .If any one of you cud fix this code
> > ,help me out. -Riyaz
> >
> > #include <iostream.h>
> > #include <stdlib.h>
>
>Useless
> > #include <process.h>
>
>Pre-ANSI header file declaration
>
>
> > class knight
> >      {
> >      int chess[8][8],location[65][10],denied[64];
> >      int row_loc,pos,i,j;
> >      public:
> >      knight();
> >      void assignment(void);
> >      int value(int);
> >      void refresh(void);
> >      int append(int ,int);
> >      };
> > knight::knight(void)
> >      {
> >      row_loc=-1;
> >      i=j=0;
> >      for(int m=0;m<8;m++)
> >           for(int n=0;n<8;n++)
> >                chess[m][n]=0;
> >      for(int m=0;m<65;m++)
> >           for(int n=0;n<10;n++)
> >                location[m][n]=0;
> >      for(int m=0;m<64;m++)
> >           denied[m]=99;
> >      assignment();
> >      }
> > void knight::assignment(void)
> >      {
> >      chess[i][j]=1;
>
>
>Where are i, j defined? Strangely it compiles in MINGW32!!!! (compiler
>defect).
>
>
> >      refresh();
> >      pos=value(j+(8*i));
> >      i=pos/8;
> >      j=pos%8;
>
> >      assignment();
>
>
>// Recursion never ends!
>
>
> >      }
> > int knight::value(int val)
> >      {
> >      row_loc++;
> >      int temp=1;
> >      int lock,ii,jj;
> >      location[row_loc][0]=val;
> >      ii=val/8;
> >      jj=val%8;
> >      if(jj==0)
> >           {
> >           if(ii>=1)
> >                {
> >                if(ii>=2)
> >                     {lock=append(val-15,temp);if(lock==0) {temp++;}}
> >                lock=append(val-6,temp);if(lock==0) {temp++;}
> >                }
> >           if(ii<=6)
> >                {
> >                if(ii<=5)
> >                     {lock=append(val+17,temp);if(lock==0) {temp++;}}
> >                lock=append(val+10,temp);if(lock==0) {temp++;}
> >                }
> >           }
> >      if(jj==7)
> >           {
> >           if(ii>=1)
> >                {
> >                if(ii>=2)
> >                     {lock=append(val-17,temp);if(lock==0) {temp++;}}
> >                lock=append(val-10,temp);if(lock==0) {temp++;}
> >                }
> >           if(ii<=6)
> >                {
> >                if(ii<=5)
> >                     {lock=append(val+15,temp);if(lock==0) {temp++;}}
> >                lock=append(val+6,temp);if(lock==0) {temp++;}
> >                }
> >           }
> >      if(jj==1)
> >           {
> >           if(ii>=1)
> >                {
> >                if(ii>=2)
> >                     {
> >                     lock=append(val-15,temp);if(lock==0) {temp++;}
> >                     lock=append(val-17,temp);if(lock==0) {temp++;}
> >                     }
> >                lock=append(val-6,temp);if(lock==0) {temp++;}
> >                }
> >           if(ii<=6)
> >                {
> >                if(ii<=5)
> >                     {
> >                     lock=append(val+17,temp);if(lock==0) {temp++;}
> >                     lock=append(val+15,temp);if(lock==0) {temp++;}
> >                     }
> >                lock=append(val+10,temp);if(lock==0) {temp++;}
> >                }
> >           }
> >      if(jj==6)
> >           {
> >           if(ii>=1)
> >                {
> >                if(ii>=2)
> >                     {
> >                     lock=append(val-15,temp);if(lock==0) {temp++;}
> >                     lock=append(val-17,temp);if(lock==0) {temp++;}
> >                     }
> >                lock=append(val-10,temp);if(lock==0) {temp++;}
> >                }
> >           if(ii<=6)
> >                {
> >                if(ii<=5)
> >                     {
> >                     lock=append(val+17,temp);if(lock==0) {temp++;}
> >                     lock=append(val+15,temp);if(lock==0) {temp++;}
> >                     }
> >                lock=append(val+6,temp);if(lock==0) {temp++;}
> >                }
> >           }
> >      if(jj>1 && jj<6)
> >           {
> >           if(ii>=1)
> >                {
> >                if(ii>=2)
> >                     {
> >                     lock=append(val-17,temp);if(lock==0) {temp++;}
> >                     lock=append(val-15,temp);if(lock==0) {temp++;}
> >                     }
> >                lock=append(val-10,temp);if(lock==0) {temp++;}
> >                lock=append(val-6,temp);if(lock==0) {temp++;}
> >                }
> >           if(ii<=6)
> >                {
> >                if(ii<=5)
> >                     {
> >                     lock=append(val+15,temp);if(lock==0) {temp++;}
> >                     lock=append(val+17,temp);if(lock==0) {temp++;}
> >                     }
> >                lock=append(val+6,temp);if(lock==0) {temp++;}
> >                lock=append(val+10,temp);if(lock==0) {temp++;}
> >                }
> >           }
> >           lock=append(-1,temp);
> >           code:
> >           if(location[row_loc][1]==-1)
> >                {
> >                ii=location[row_loc][0]/8;
> >                jj=location[row_loc][0]%8;
> >                chess[ii][jj]=0;
> >                row_loc--;
> >                if(row_loc<0) {cout<<"NO
> > SOLUTION";system("pause");exit(0);}
> >                for(int m=1;m<9;m++)
> >                     location[row_loc][m]=location[row_loc][m+1];
> >                goto code;
> >                }
> >           return location[row_loc][1];
> >      }
> > void knight::refresh(void)
> >      {
> >      int l,tot;
> >      l=tot=0;
> >      for(int m=0;m<64;m++)
> >           denied[m]=99;
> >      for(int m=0;m<8;m++)
> >           {
> >           for(int n=0;n<8;n++)
> >                {
> >                if(chess[m][n]==1)
> >                     {
> >                     if(l==63)
> >                          {
> >                          cout<<"RESULT :"<<endl;
> >                          for(int k=0;k<64;k++)
> >                               cout<<denied[k]<<" ";
> >                          system("pause");
> >                          exit(0);
> >                          }
> >                     tot=n+(8*m);
> >                     denied[l]=tot;
> >                     l++;
> >                     }
> >                }
> >           }
> >      }
> > int knight::append(int val1,int temp1)
> >      {
> >      int lock=0;
> >      for(int m=0;m<64;m++)
> >           if(denied[m]==val1)
> >                {lock=1;break;}
> >      if(!lock)
> >           location[row_loc][temp1]=val1;
> >      return lock;
> >      }
> > void main()
> >      {knight k;}
>
>int main()
>
>
>Ioannis
>
>* Ioannis Vranos
>* Programming pages: http://www.noicys.d2g.com
>* Alternative URL: http://run.to/noicys
>
>
>_______________________________________________
>Dev-cpp-users mailing list
>Dev...@li...
>https://lists.sourceforge.net/lists/listinfo/dev-cpp-users




_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp.

RE: [Dev-C++] reg-Knight's tour problem

[Ioannis V. <no...@ya...>]

> -----Original Message-----
> From: dev...@li...=20
> [mailto:dev...@li...] On Behalf=20
> Of Mohammed Riyaz
> Sent: Thursday, March 07, 2002 6:05 PM
> To: dev...@li...
> Subject: RE: [Dev-C++] reg-Knight's tour problem
>=20
>=20
> hey ioannis;
> The variables i,j are members of the class. Why do you say=20
> recursion never=20
> end. The function assignment calls the other functions=20
> 'refresh', 'value' in the line
>=20
> refresh();
> pos=3Dvalue(j+(8*i));


Apologies, i was in a hurry and said stupid things. I' ll never do  that
again.


Ioannis
=20
* Ioannis Vranos
* Programming pages: http://www.noicys.d2g.com
* Alternative URL: http://run.to/noicys

RE: [Dev-C++] reg-Knight's tour problem

[Santiago P. C. <San...@yd...>]

Hi Mohammed,

Let me try to give some help on this issue O:o)

A 'common' recursive algorithm looks like this one:

// Calculate factorial of int number
int recursive_function(int iParameter)
{
	// Check for posible errors
	if (iParameter < 0)
	{
		cout << "ERROR: Negative number!" << endl;
		exit(SOME_ERROR_VALUE);
	}

	// Check race condition
	if (iParameter == 0)
	{
		// We got it! No more loops ;o)
		return 1;
	}
	else
	{
		// Handle params & manage with values
		int iCurrentValue = iParameter;
		iParameter--;

		return (iCurrentValue*recursive_function(iParameter));
	}
}

This is not THE answer, it's a simple function to ilustrate recursive
algorithms, there are variants depending on the desired behaviour of the
function (p.e. you can handle parameter/s before checking the race
condition).

The point here is that you must reach the race condition inside the function
and terminate the program normally, if you don't do that you'll exit the
program 'the hard way' even when the program itself succeeds.

As a good programming practice you should try to avoid exiting abruptly,
instead of this, you should perform any necessary cleanup tasks when you
exit a program p.e.: close open files, deallocate reserved memory, etc...

Hope this helps!

Best regards, Santy


-----Original Message-----
From: Mohammed Riyaz [mailto:p_m...@ho...] 
Sent: Thursday, March 07, 2002 5:05 PM
To: dev...@li...
Subject: RE: [Dev-C++] reg-Knight's tour problem


hey ioannis;
The variables i,j are members of the class. Why do you say recursion never 
end. The function assignment calls the other functions 'refresh', 'value' in
the line

refresh();
pos=value(j+(8*i));

hence when the this situation (given below)arises in the function value, the

program wil hald and hence the recursion ends there.

if(row_loc<0) {cout<<"NO SOLUTION";system("pause");exit(0);}

(or)

when the situation
if(l==63)
                          {
                          cout<<"RESULT :"<<endl;
                          for(int k=0;k<64;k++)
                               cout<<denied[k]<<" ";
                          system("pause");
                          exit(0);
                          }
in refresh function is encountered the recursion ends.
-Riyaz

--------------------------------------------------------------------------------------
This message and any files transmitted with it are confidential and intended solely 
for the use of the individual or entity to whom they are addressed. No confidentiality 
or privilege is waived or lost by any wrong transmission. 
If you have received this message in error, please immediately destroy it and kindly 
notify the sender by reply email.
You must not, directly or indirectly, use, disclose, distribute, print, or copy any 
part of this message if you are not the intended recipient. Opinions, conclusions and 
other information in this message that do not relate to the official business of 
People Communications S.A. shall be understood as neither given nor endorsed by it. 
--------------------------------------------------------------------------------------

RE: [Dev-C++] reg-Knight's tour problem

[<Ech...@ne...>]

  Message: 8
  From: "Ioannis Vranos" <no...@ya...>
  To: "Dev-C++" <dev...@li...>
  Subject: RE: [Dev-C++] reg-Knight's tour problem
  Date: Thu, 7 Mar 2002 15:20:47 +0200

  > -----Original Message-----
  > From: dev...@li... 
  > [mailto:dev...@li...] On Behalf 
  > Of Mohammed Riyaz
  > Sent: Thursday, March 07, 2002 2:00 PM
  > To: dev...@li...
  > Subject: [Dev-C++] reg-Knight's tour problem
  > 
  > 
  > hey,
  > I had a look at the code sent in. Am new to programming, my 
  > code sux when 
  > compared to that. :D .If any one of you cud fix this code 
  > ,help me out. -Riyaz
  > 
  > #include <iostream.h>
  > #include <stdlib.h>

  Useless
  > #include <process.h>

  Pre-ANSI header file declaration


  > class knight
  >      {
  >      int chess[8][8],location[65][10],denied[64];
  >      int row_loc,pos,i,j;
  >      public:
  >      knight();
  >      void assignment(void);
  >      int value(int);
  >      void refresh(void);
  >      int append(int ,int);
  >      };
  > knight::knight(void)
  >      {
  >      row_loc=-1;
  >      i=j=0;
  >      for(int m=0;m<8;m++)
  >           for(int n=0;n<8;n++)
  >                chess[m][n]=0;
  >      for(int m=0;m<65;m++)
  >           for(int n=0;n<10;n++)
  >                location[m][n]=0;
  >      for(int m=0;m<64;m++)
  >           denied[m]=99;
  >      assignment();
  >      }
  > void knight::assignment(void)
  >      {
  >      chess[i][j]=1;


  Where are i, j defined? Strangely it compiles in MINGW32!!!! (compiler
  defect).

i, j are defined in class knight:

  class knight{
    int chess[8][8],location[65][10],denied[64];
    int row_loc,pos,i,j;                  <-- HERE
  
    public:
    knight();
    void assignment(void);
    int value(int);
    void refresh(void);
    int append(int ,int);
  };


  >      refresh();
  >      pos=value(j+(8*i));
  >      i=pos/8;
  >      j=pos%8;

  >      assignment(); 


  // Recursion never ends!

Since it is tail recursion it could be done in a while loop - once you figure out the exit condition ... while(1) is not good either.

  >      }
  > int knight::value(int val)
  >      {
  >      row_loc++;
  >      int temp=1;
  >      int lock,ii,jj;
  >      location[row_loc][0]=val;
  >      ii=val/8;
  >      jj=val%8;
  >      if(jj==0)
  >           {
  >           if(ii>=1)
  >                {
  >                if(ii>=2)
  >                     {lock=append(val-15,temp);if(lock==0) {temp++;}}
  >                lock=append(val-6,temp);if(lock==0) {temp++;}
  >                }
  >           if(ii<=6)
  >                {
  >                if(ii<=5)
  >                     {lock=append(val+17,temp);if(lock==0) {temp++;}}
  >                lock=append(val+10,temp);if(lock==0) {temp++;}
  >                }
  >           }
  >      if(jj==7)
  >           {
  >           if(ii>=1)
  >                {
  >                if(ii>=2)
  >                     {lock=append(val-17,temp);if(lock==0) {temp++;}}
  >                lock=append(val-10,temp);if(lock==0) {temp++;}
  >                }
  >           if(ii<=6)
  >                {
  >                if(ii<=5)
  >                     {lock=append(val+15,temp);if(lock==0) {temp++;}}
  >                lock=append(val+6,temp);if(lock==0) {temp++;}
  >                }
  >           }
  >      if(jj==1)
  >           {
  >           if(ii>=1)
  >                {
  >                if(ii>=2)
  >                     {
  >                     lock=append(val-15,temp);if(lock==0) {temp++;}
  >                     lock=append(val-17,temp);if(lock==0) {temp++;}
  >                     }
  >                lock=append(val-6,temp);if(lock==0) {temp++;}
  >                }
  >           if(ii<=6)
  >                {
  >                if(ii<=5)
  >                     {
  >                     lock=append(val+17,temp);if(lock==0) {temp++;}
  >                     lock=append(val+15,temp);if(lock==0) {temp++;}
  >                     }
  >                lock=append(val+10,temp);if(lock==0) {temp++;}
  >                }
  >           }
  >      if(jj==6)
  >           {
  >           if(ii>=1)
  >                {
  >                if(ii>=2)
  >                     {
  >                     lock=append(val-15,temp);if(lock==0) {temp++;}
  >                     lock=append(val-17,temp);if(lock==0) {temp++;}
  >                     }
  >                lock=append(val-10,temp);if(lock==0) {temp++;}
  >                }
  >           if(ii<=6)
  >                {
  >                if(ii<=5)
  >                     {
  >                     lock=append(val+17,temp);if(lock==0) {temp++;}
  >                     lock=append(val+15,temp);if(lock==0) {temp++;}
  >                     }
  >                lock=append(val+6,temp);if(lock==0) {temp++;}
  >                }
  >           }
  >      if(jj>1 && jj<6)
  >           {
  >           if(ii>=1)
  >                {
  >                if(ii>=2)
  >                     {
  >                     lock=append(val-17,temp);if(lock==0) {temp++;}
  >                     lock=append(val-15,temp);if(lock==0) {temp++;}
  >                     }
  >                lock=append(val-10,temp);if(lock==0) {temp++;}
  >                lock=append(val-6,temp);if(lock==0) {temp++;}
  >                }
  >           if(ii<=6)
  >                {
  >                if(ii<=5)
  >                     {
  >                     lock=append(val+15,temp);if(lock==0) {temp++;}
  >                     lock=append(val+17,temp);if(lock==0) {temp++;}
  >                     }
  >                lock=append(val+6,temp);if(lock==0) {temp++;}
  >                lock=append(val+10,temp);if(lock==0) {temp++;}
  >                }
  >           }
  >           lock=append(-1,temp);
  >           code:
  >           if(location[row_loc][1]==-1)
  >                {
  >                ii=location[row_loc][0]/8;
  >                jj=location[row_loc][0]%8;
  >                chess[ii][jj]=0;
  >                row_loc--;
  >                if(row_loc<0) {cout<<"NO 
  > SOLUTION";system("pause");exit(0);}
  >                for(int m=1;m<9;m++)
  >                     location[row_loc][m]=location[row_loc][m+1];
  >                goto code;
  >                }
  >           return location[row_loc][1];
  >      }
  > void knight::refresh(void)
  >      {
  >      int l,tot;
  >      l=tot=0;
  >      for(int m=0;m<64;m++)
  >           denied[m]=99;
  >      for(int m=0;m<8;m++)
  >           {
  >           for(int n=0;n<8;n++)
  >                {
  >                if(chess[m][n]==1)
  >                     {
  >                     if(l==63)
  >                          {
  >                          cout<<"RESULT :"<<endl;
  >                          for(int k=0;k<64;k++)
  >                               cout<<denied[k]<<" ";
  >                          system("pause");
  >                          }
  >                     tot=n+(8*m);
  >                     denied[l]=tot;
  >                     l++;
  >                     }
  >                }
  >           }
  >      }
  > int knight::append(int val1,int temp1)
  >      {
  >      int lock=0;
  >      for(int m=0;m<64;m++)
  >           if(denied[m]==val1)
  >                {lock=1;break;}
  >      if(!lock)
  >           location[row_loc][temp1]=val1;
  >      return lock;
  >      }
  > void main()
  >      {knight k;}

  int main()


  Ioannis

  * Ioannis Vranos
  * Programming pages: http://www.noicys.d2g.com
  * Alternative URL: http://run.to/noicys


Evan Hempel
-- 




__________________________________________________________________
Your favorite stores, helpful shopping tools and great gift ideas. Experience the convenience of buying online with Shop@Netscape! http://shopnow.netscape.com/

Get your own FREE, personal Netscape Mail account today at http://webmail.netscape.com/

Re: [Dev-C++] reg-Knight's tour problem

[Brian M. <str...@ho...>]

Wow.  For someone who is new to programming, you sure can pound out some 
serious code.  I think the biggest problem you have with this program is 
that the algorithm is too complex (i'm not exactly sure what algorithm it is 
you are working with, it just seems self-evident).  There is a trick to the 
knight's tour quandary that lends itself to a very simple algorithm.


The sure-fire way (has not failed my yet) to make it through the Knight's 
Tour completely without getting stuck is to always move to one of the spaces 
(out of a max of 8) which has the lowest "escape value."  A square's escape 
value is simply the number of squares that the knight can legally move from 
after landing on that square.  Here is an example of all the escape values 
on the board for the first few moves of the knight's tour:

                           2 3 4 4 4 4 3 2
                           3 4 6 6 6 6 4 3
                           4 6 8 8 8 8 6 4
                           4 6 8 8 8 8 6 4
                           4 6 8 8 8 8 6 4
                           4 6 8 8 8 8 6 4
                           3 4 6 6 6 6 4 3
                           2 3 4 4 4 4 3 2


                           2 3 3 4 3 4 3 2
                           3 3 6 6 6 5 4 3
                           4 6 8 K 8 8 6 4
                           4 5 8 8 8 7 6 4
                           4 6 7 8 7 8 6 4
                           4 6 8 8 8 8 6 4
                           3 4 6 6 6 6 4 3
                           2 3 4 4 4 4 3 2


                           2 3 K 4 3 4 3 2
                           2 3 6 6 5 5 4 3
                           4 5 8 X 8 8 6 4
                           4 5 8 8 8 7 6 4
                           4 6 7 8 7 8 6 4
                           4 6 8 8 8 8 6 4
                           3 4 6 6 6 6 4 3
                           2 3 4 4 4 4 3 2



                           2 3 X 4 3 4 3 2
                           K 3 6 6 5 5 4 3
                           4 5 7 X 8 8 6 4
                           4 4 8 8 8 7 6 4
                           4 6 7 8 7 8 6 4
                           4 6 8 8 8 8 6 4
                           3 4 6 6 6 6 4 3
                           2 3 4 4 4 4 3 2



                           2 3 X 4 3 4 3 2
                           X 3 5 6 5 5 4 3
                           4 5 7 X 8 8 6 4
                           4 K 8 8 8 7 6 4
                           4 6 7 7 7 8 6 4
                           3 6 7 8 8 8 6 4
                           3 4 6 6 6 6 4 3
                           2 3 4 4 4 4 3 2


If you keep moving the knight accross the board in this manner, going to the 
square with the lowest escape value, you will eventually complete the 
knights tour.


So, the algorithm for the knights tour is simply:

while the knight's tour is not complete:

find all next possible squares to move to
find the square with the lowest "escape value"
move there

loop


Don't ask me why this works, i just know it does.



>From: "Mohammed Riyaz" <p_m...@ho...>
>To: dev...@li...
>Subject: [Dev-C++] reg-Knight's tour problem
>Date: Thu, 07 Mar 2002 12:00:22 +0000
>
>hey,
>I had a look at the code sent in. Am new to programming, my code sux when
>compared to that. :D .If any one of you cud fix this code ,help me
>out.
>-Riyaz
>
>#include <iostream.h>
>#include <stdlib.h>
>#include <process.h>
>class knight
>     {
>     int chess[8][8],location[65][10],denied[64];
>     int row_loc,pos,i,j;
>     public:
>     knight();
>     void assignment(void);
>     int value(int);
>     void refresh(void);
>     int append(int ,int);
>     };
>knight::knight(void)
>     {
>     row_loc=-1;
>     i=j=0;
>     for(int m=0;m<8;m++)
>          for(int n=0;n<8;n++)
>               chess[m][n]=0;
>     for(int m=0;m<65;m++)
>          for(int n=0;n<10;n++)
>               location[m][n]=0;
>     for(int m=0;m<64;m++)
>          denied[m]=99;
>     assignment();
>     }
>void knight::assignment(void)
>     {
>     chess[i][j]=1;
>     refresh();
>     pos=value(j+(8*i));
>     i=pos/8;
>     j=pos%8;
>     assignment();
>     }
>int knight::value(int val)
>     {
>     row_loc++;
>     int temp=1;
>     int lock,ii,jj;
>     location[row_loc][0]=val;
>     ii=val/8;
>     jj=val%8;
>     if(jj==0)
>          {
>          if(ii>=1)
>               {
>               if(ii>=2)
>                    {lock=append(val-15,temp);if(lock==0) {temp++;}}
>               lock=append(val-6,temp);if(lock==0) {temp++;}
>               }
>          if(ii<=6)
>               {
>               if(ii<=5)
>                    {lock=append(val+17,temp);if(lock==0) {temp++;}}
>               lock=append(val+10,temp);if(lock==0) {temp++;}
>               }
>          }
>     if(jj==7)
>          {
>          if(ii>=1)
>               {
>               if(ii>=2)
>                    {lock=append(val-17,temp);if(lock==0) {temp++;}}
>               lock=append(val-10,temp);if(lock==0) {temp++;}
>               }
>          if(ii<=6)
>               {
>               if(ii<=5)
>                    {lock=append(val+15,temp);if(lock==0) {temp++;}}
>               lock=append(val+6,temp);if(lock==0) {temp++;}
>               }
>          }
>     if(jj==1)
>          {
>          if(ii>=1)
>               {
>               if(ii>=2)
>                    {
>                    lock=append(val-15,temp);if(lock==0) {temp++;}
>                    lock=append(val-17,temp);if(lock==0) {temp++;}
>                    }
>               lock=append(val-6,temp);if(lock==0) {temp++;}
>               }
>          if(ii<=6)
>               {
>               if(ii<=5)
>                    {
>                    lock=append(val+17,temp);if(lock==0) {temp++;}
>                    lock=append(val+15,temp);if(lock==0) {temp++;}
>                    }
>               lock=append(val+10,temp);if(lock==0) {temp++;}
>               }
>          }
>     if(jj==6)
>          {
>          if(ii>=1)
>               {
>               if(ii>=2)
>                    {
>                    lock=append(val-15,temp);if(lock==0) {temp++;}
>                    lock=append(val-17,temp);if(lock==0) {temp++;}
>                    }
>               lock=append(val-10,temp);if(lock==0) {temp++;}
>               }
>          if(ii<=6)
>               {
>               if(ii<=5)
>                    {
>                    lock=append(val+17,temp);if(lock==0) {temp++;}
>                    lock=append(val+15,temp);if(lock==0) {temp++;}
>                    }
>               lock=append(val+6,temp);if(lock==0) {temp++;}
>               }
>          }
>     if(jj>1 && jj<6)
>          {
>          if(ii>=1)
>               {
>               if(ii>=2)
>                    {
>                    lock=append(val-17,temp);if(lock==0) {temp++;}
>                    lock=append(val-15,temp);if(lock==0) {temp++;}
>                    }
>               lock=append(val-10,temp);if(lock==0) {temp++;}
>               lock=append(val-6,temp);if(lock==0) {temp++;}
>               }
>          if(ii<=6)
>               {
>               if(ii<=5)
>                    {
>                    lock=append(val+15,temp);if(lock==0) {temp++;}
>                    lock=append(val+17,temp);if(lock==0) {temp++;}
>                    }
>               lock=append(val+6,temp);if(lock==0) {temp++;}
>               lock=append(val+10,temp);if(lock==0) {temp++;}
>               }
>          }
>          lock=append(-1,temp);
>          code:
>          if(location[row_loc][1]==-1)
>               {
>               ii=location[row_loc][0]/8;
>               jj=location[row_loc][0]%8;
>               chess[ii][jj]=0;
>               row_loc--;
>               if(row_loc<0) {cout<<"NO SOLUTION";system("pause");exit(0);}
>               for(int m=1;m<9;m++)
>                    location[row_loc][m]=location[row_loc][m+1];
>               goto code;
>               }
>          return location[row_loc][1];
>     }
>void knight::refresh(void)
>     {
>     int l,tot;
>     l=tot=0;
>     for(int m=0;m<64;m++)
>          denied[m]=99;
>     for(int m=0;m<8;m++)
>          {
>          for(int n=0;n<8;n++)
>               {
>               if(chess[m][n]==1)
>                    {
>                    if(l==63)
>                         {
>                         cout<<"RESULT :"<<endl;
>                         for(int k=0;k<64;k++)
>                              cout<<denied[k]<<" ";
>                         system("pause");
>                         }
>                    tot=n+(8*m);
>                    denied[l]=tot;
>                    l++;
>                    }
>               }
>          }
>     }
>int knight::append(int val1,int temp1)
>     {
>     int lock=0;
>     for(int m=0;m<64;m++)
>          if(denied[m]==val1)
>               {lock=1;break;}
>     if(!lock)
>          location[row_loc][temp1]=val1;
>     return lock;
>     }
>void main()
>     {knight k;}
>
>
>
>_________________________________________________________________
>MSN Photos is the easiest way to share and print your photos:
>http://photos.msn.com/support/worldwide.aspx
>
>
>_______________________________________________
>Dev-cpp-users mailing list
>Dev...@li...
>https://lists.sourceforge.net/lists/listinfo/dev-cpp-users




_________________________________________________________________
Chat with friends online, try MSN Messenger: http://messenger.msn.com

RE: [Dev-C++] reg-Knight's tour problem

[Ioannis V. <no...@ya...>]

> -----Original Message-----
> From: dev...@li... 
> [mailto:dev...@li...] On Behalf 
> Of Santiago Palmier Campos
> Sent: Thursday, March 07, 2002 3:57 PM
> To: Dev-C++
> Subject: RE: [Dev-C++] reg-Knight's tour problem
> 
> 
> Hi to *,
> 
> There's NO compiler defect (with this issue), so... Don't panic! ;o)
> 
> The variables 'i' & 'j' are class' members, defined on line:
> 
> >      int row_loc,pos,i,j;
> 
> Just my 2 cents, regards
> Santy


Oops! Apologies, i should be more careful. Ioannis gives to Santiago 2
Eurocents.



Ioannis
 
* Ioannis Vranos
* Programming pages: http://www.noicys.d2g.com
* Alternative URL: http://run.to/noicys