"나이트 투어"에 대한 다음 코드가 왜 제대로 작동하지 않습니까?

Question

C의 Codeblocks 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.)

보드가 가득 찼는 지 여부는 두 가지 방법으로 테스트 할 수 있습니다. 깊이가 64라는 것을 확인한 후 반환하십시오. 값을 지정하지 마십시오. (a과 b이 유효한 보드 좌표라고 확신하지 못했기 때문에 더욱 그렇습니다.) 64 번째 점프는 길이가 63이므로 64 번째 점프는 보드가 완전한.

또 다른 방법은 사각형이 유효한지 확인한 후 i + 1이 64인지 확인하는 것입니다. 이는 첫 번째 방법과 동일하며 하나의 호출을 저장합니다. 이러한 변화와

, 당신의 프로그램이된다 :

#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 보드를 브 루트 - 강제하는 것은 내 컴퓨터에서 삼분의 주위에 약간의 시간이 소요됩니다 4 × 4에는 해결책이 없습니다.)