「ナイトツアー」のコードが正しく動作しないのはなぜですか？

Question

私は再帰とバックトラックを使用してナイト・ツアーの問題を解決しようとすると、CでコードブロックIDEに次のコードを使用しています。しかし、無限回帰のケースではないと思うけど、それは永遠に続き、出力を出さないということです。

#include <stdio.h> 
#include <conio.h> 
int board[8][8]= {{0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,0}}; 
int i = 1; 
int next(int a, int b); 
int main() 
{ 
    int j, k; 
    next(0,0); 
    for(k = 0; k < 64; k++) 
    { 
     printf(" %d ", board[k/8][k%8]); 
     if((i+1)%8==0) 
      printf("\n"); 
    } 
} 
int next(int a, int b) 
{ 
    if(i==64) 
    { 
     board[a][b]=64; 
     return 1; 
    } 
    if((a<0||a>7||b<0||b>7)) 
     return 0; 
    if(board[a][b]!=0) 
     return 0; 
     printf(" %d %d ", a, b); 
     //getch(); 
    board[a][b]= i; 
    if(next(a+2, b+1)) 
    { 
     i++; 
     return 1; 
    } 
    if(next(a+1, b+2)) 
    { 
     i++; 
     return 1; 
    } 
    if(next(a-1, b+2)) 
    { 
     i++; 
     return 1; 
    } 
    if(next(a+2, b-1)) 
    { 
     i++; 
     return 1; 
    } 
    if(next(a-2, b-1)) 
    { 
     i++; 
     return 1; 
    } 
    if(next(a-1, b-2)) 
    { 
     i++; 
     return 1; 
    } 
    if(next(a+1, b-2)) 
    { 
     i++; 
     return 1; 
    } 
    if(next(a-2, b+1)) 
    { 
     i++; 
     return 1; 
    } 
    board[a][b]=0; 
    return 0; 
} 

Answer 1

あなたの主な問題は、ツアーの長さと再帰の深度を記録するためにグローバル変数を使用することです。あなたはこの変数を増分するだけです。

経路の長さは、各再帰呼び出しのために可変であるべきであり、従ってnext関数に対してローカルであるべきです。

（ちなみに、iは大域変数の恐ろしい名前です。これはローカルにすると明らかになります：ボードを印刷するループはkを超えていますが、改行を印刷するかどうかを確認するときは、 iです）

ボードが一杯になっているかどうかのテストは、次の2つの方法で実行できます。まず、深さが64であることを確認してください。値を割り当てないでください。 （。さらにので、あなたがaとbが有効なボードの座標であることを保証していないので）第64ジャンプは違法になります64個の正方形を訪問パスは、63の長さを持っているので、64番目のジャンプはちょうどボードがあることを示し、フル。

もう一つの方法は、正方形が有効であることを確認した後、thet i + 1が64でチェックすることです。これは最初のメソッドと同等で、1回の呼び出しを保存します。これらの変更により

、あなたのプログラムは次のようになります。

#include <stdio.h> 

#define N 8 
#define NN (N*N) 

int board[N][N]= {{0}}; 

int next(int a, int b, int i); 

int main() 
{ 
    int k; 

    if (next(0, 0, 0)) { 
     for(k = 0; k < NN; k++) { 
      if(k && k % N == 0) puts(""); 
      printf(" %2d", board[k/N][k % N]); 
     } 
     puts(""); 
    } else { 
     puts("No solution."); 
    } 

    return 0; 
} 

int next(int a, int b, int i) 
{ 
    if (a < 0 || a >= N) return 0; 
    if (b < 0 || b >= N) return 0; 
    if (board[a][b] != 0) return 0; 

    i++; 
    board[a][b] = i; 
    if (i == NN) return 1; 

    if (next(a + 2, b + 1, i)) return 1; 
    if (next(a + 1, b + 2, i)) return 1; 
    if (next(a - 1, b + 2, i)) return 1; 
    if (next(a + 2, b - 1, i)) return 1; 
    if (next(a - 2, b - 1, i)) return 1; 
    if (next(a - 1, b - 2, i)) return 1; 
    if (next(a + 1, b - 2, i)) return 1; 
    if (next(a - 2, b + 1, i)) return 1; 

    board[a][b] = 0; 
    return 0; 
} 

（プロヒント：N == 6最初でテスト;けだもの強制8 × 8ボードは、私のマシンで3分の周りに、ある程度の時間がかかる4 ×を。 4は解決策を持っていません。）