This code is stuck in an infinite loop in the knight tour problem which i am solving using backtracking. I have used x[8] and y[8] array to access possible moves in 8 directions. Also I have formed these x and y arrays same as an already solved answer. But still there is something I am missing and I cant understand what is going wrong.
#include<stdio.h>
int x[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int sol[100][100]={0};
int isvalid(int i,int j,int n)
{
if(i>=0&&j>=0&&i<n&&j<n)
{
if(sol[i][j]==0)
return 1;
else
return 0;
}
return 0;
}
int solvekt(int i,int j,int k,int n)
{
printf("i=%d j=%d k=%d\n",i,j,k);
if(k==n*n+1)
return 1;
int m,i1,j1,ans=0;
for(m=0;m<8;m++)
{
i1=i+x[m];
j1=j+y[m];
if(isvalid(i1,j1,n))
{
printf("i=%d j=%d i1=%d j1=%d k=%d\n",i,j,i1,j1,k);
sol[i1][j1]=k;
ans=solvekt(i1,j1,k+1,n);
if(ans)return 1;
else
sol[i1][j1]=0;
}
}
return 0;
}
int main()
{
int n=6,i,j;
sol[0][0]=1;
if(!solvekt(0,0,2,n))printf("not possible\n");
else
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}
OP was impatient. Code is fine, just took a while.
"Are you certain you are in an infinite loop, as opposed to simply a long-running loop? " @John Bollinger
To run faster, omit debug prints @Weather Vane