can any one help me reagarding this problem
Posted: Sat Jun 12, 2004 10:16 am
i am trying to make a knight tour all the position in 64 moves from any position... i used recurvise backtracking... having prob...can some check my code and tell me the mistake...
MY CODE :
#include<stdio.h>
int moves[65][2]={0}; //the co-ordinate of each move
int position[9][9]={0}; //the status of each block of the board
int type_moves[8][2]={{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1}}; //8 types of move possible by knight
int k=64;
int checker(int,int); //function to check whether the move is valid or not
void backtrack(int,int,int);
void main()
{
int i,j;
scanf("%d %d",&i,&j);
printf("running...\n");
backtrack(1,i,j); //(i,j) the starting co-ordinate
printf("ended...\n");
for(i=1;i<65;i++)
if(i%2%2==0)
printf("%2d. - (%d,%d)\n",i,moves[0],moves[1]);
else
printf("%2d. - (%d,%d) ",i,moves[0],moves[1]);
printf("\n");
}
void backtrack(int n,int i,int j)
{
int check=checker(i,j);
if(n<k && check==1) // if the move is valid.
{
position[j]=1; // changing the status of block to 1 as occupied.
moves[n][0]=i; // storing the co-ordinate.
moves[n][1]=j;
n++;
for(int m=0;m<8;m++) // for 8 moves possible
{
i+=type_moves[m][0];
j+=type_moves[m][1];
backtrack(n,i,j);
i-=type_moves[m][0];
j-=type_moves[m][1];
}
// if road is blocked... changing again to status 0 and
// removing the stored co-ordinate.
position[j]=moves[n-1][0]=moves[n-1][1]=0;
}
if(n==k) // the last move.
{
moves[n][0]=i;
moves[n][1]=j;
return;
}
}
int checker(int i,int j)
{
if(i<1||i>8||j<1||j>8||position[j]==1)
return 0;
else
return 1;
}
MY CODE :
#include<stdio.h>
int moves[65][2]={0}; //the co-ordinate of each move
int position[9][9]={0}; //the status of each block of the board
int type_moves[8][2]={{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1}}; //8 types of move possible by knight
int k=64;
int checker(int,int); //function to check whether the move is valid or not
void backtrack(int,int,int);
void main()
{
int i,j;
scanf("%d %d",&i,&j);
printf("running...\n");
backtrack(1,i,j); //(i,j) the starting co-ordinate
printf("ended...\n");
for(i=1;i<65;i++)
if(i%2%2==0)
printf("%2d. - (%d,%d)\n",i,moves[0],moves[1]);
else
printf("%2d. - (%d,%d) ",i,moves[0],moves[1]);
printf("\n");
}
void backtrack(int n,int i,int j)
{
int check=checker(i,j);
if(n<k && check==1) // if the move is valid.
{
position[j]=1; // changing the status of block to 1 as occupied.
moves[n][0]=i; // storing the co-ordinate.
moves[n][1]=j;
n++;
for(int m=0;m<8;m++) // for 8 moves possible
{
i+=type_moves[m][0];
j+=type_moves[m][1];
backtrack(n,i,j);
i-=type_moves[m][0];
j-=type_moves[m][1];
}
// if road is blocked... changing again to status 0 and
// removing the stored co-ordinate.
position[j]=moves[n-1][0]=moves[n-1][1]=0;
}
if(n==k) // the last move.
{
moves[n][0]=i;
moves[n][1]=j;
return;
}
}
int checker(int i,int j)
{
if(i<1||i>8||j<1||j>8||position[j]==1)
return 0;
else
return 1;
}