0

このコードは、バックトラッキングを使用して解決しているナイト ツアーの問題で無限ループに陥っています。配列を使用して、方向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;
}
4

1 に答える 1

3

OPはせっかちでした。コードは問題ありません。しばらく時間がかかりました。

「単なる長時間ループではなく、無限ループに陥っていると確信していますか?」@John Bollinger

より速く実行するには、デバッグ出力を省略します @Weather Vane

于 2016-06-22T21:13:58.620 に答える