在骑士之旅回溯中陷入无限循环

Question

这段代码陷入了我正在使用回溯解决的骑士巡回赛问题的无限循环。我已经使用 x[8] and y[8] 数组访问 8 方向上可能的移动。我还形成了这些 x 和 y 数组，与已经解决的答案相同。但是我仍然缺少一些东西，我不明白出了什么问题。

#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;
}

Answer 1

OP 很不耐烦。代码很好，只是花了点时间。

"Are you certain you are in an infinite loop, as opposed to simply a long-running loop? "

为了运行更快，省略调试打印

在骑士之旅回溯中陷入无限循环

stuck in infinite loop in knight tour backtracking

c

backtracking

knights-tour