can any one help me reagarding this problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

can any one help me reagarding this problem

Post by samueljj »

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;
}
novice programmer

Post Reply

Return to “Algorithms”