NQueen은 실제로 후퇴 중입니까?

Question

NQueen problem은 backtracking의 유명한 예입니다. source에서 읽은 후 다음 코드 스 니펫을 시도했습니다.

int isSafe(int k,int i,int *x) 
{ 
    int j; 
    for(j=0;j<k;j++) 
    { 
       //old queen is placed at jth row of x[j] column 
       //new queen to be placed at kth row of ith column 
      if(i==x[j] || abs(k-j)==abs(i-x[j])) 
        return 0; 
    } 
    return 1; 
} 

int Nqueen(int k, int* sol, int N) 
{ 
    int col; 
    if(k == N) 
    { 
      printSol(sol,N); 
      return 1; 
    } 
    else 
    { 
      for(col = 1;col <= N; col++) //determines appropriate column number of the kth queen to be placed 
      { 
        if(isSafe(k,col,sol)) 
        { 
          sol[k] = col; 
          if(Nqueen(k+1, sol, N)) 
            return 1; 
          sol[k] = 0; // backtrack 
        } 
      } 
      return 0; // solution not possible 
    } 
} 

나는 점점 오전 output 같은 : 그러나

1 5 8 6 3 7 2 4 

, 내가 백 트럭 문을 언급 할 때, 나는 아무 문제없이 같은 output을 얻고있다.

int Nqueen(int k, int* sol, int N) 
{ 
    int col; 
    if(k == N) 
    { 
      printSol(sol,N); 
      return 1; 
    } 
    else 
    { 
      for(col = 1;col <= N; col++) //determines appropriate column number of the kth queen to be placed 
      { 
        if(isSafe(k,col,sol)) 
        { 
          sol[k] = col; 
          if(Nqueen(k+1, sol, N)) 
            return 1; 
          // sol[k] = 0; <-------------- Notice this change 
        } 
      } 
      return 0; 
    } 
} 

정확하게 NQueen에 어떤 문제가 있습니까?

간단한 재귀 방식이 아닙니까?

Answer 1

sol[k] = 0은 역 추적 부분이 아닙니다. 역 추적은 재귀 호출 if(Nqueen(k+1, sol, N))에서 수행됩니다.

역 추적의 아이디어는 철저한 검색입니다. 사용자가 발견 될 때까지 모든 가능성을 검색하려고합니다. 여기서 당신은 보드에있는 여왕의 모든 가능한 과제를 시도하고 있으며 여전히 안전하다면 "계속"하십시오. 안전하지 않은 것으로 판단되면 재귀에서 실패로 돌아가 다음 옵션을 시도합니다.

주석 처리 된 행은 해결책을 찾지 못하면 결과가 배열이 [0,...,0]이고 일부 비 감각적 인 배열이 아니라는 것을 확인합니다.

Answer 2

먼저 알고리즘을 이해해야합니다 (이 사실은 해당 내용의 주석이 중요하지 않음을 나타냅니다). 이 알고리즘은 이미 알고 있듯이 재귀 적입니다. 당신

• 는
• 는 여왕의 K + 1에 사용할 수있는 게재 위치를 찾아 위치, K + 2에 k 번째 여왕 설정 때문에
은 당신이 K로 돌아가 ... 역 추적한다 - 여왕, 그것을 어딘가에 놓고 반복하십시오.

참조하십시오. 3 단계에서 우리는 k 번째 여왕에게 "돌아갑니다"를보십시오. 이것은 내가 왜 역 추적이라고 불리는 지 스스로 설명하는 방법입니다.

Answer 3

역 추적 문제는 가능한 모든 조합을 시도하는 프로그래밍 패러다임입니다. 그런 다음 모든 조합에 대해 지금까지의 조합이 올바른지 확인합니다. 다음은 N (또는 8) 여왕 문제에 대한 몇 가지 단계입니다.

1. 위치가없는 안전한 장소 2 여왕에서 만약
2. 안전한지
3. 지금 2 행 1에서 여왕과 COL 0
4. 체크 표시를 골 0에서 행 0과 장소 1 여왕에서 시작 행 1, COL 1
5. 은 지금 행 1에서 2 여왕을 안전한 장소 안, COL 2.

각각에 대해 가능한 모든 열에서 여왕을 배치하고 안전한지 확인하여 다음과 같이 진행합니다. 동일한 행에 2 명의 여왕을 배치하지 않는 것처럼 명백한 거짓 조건을 생략 할 수 있습니다. 다음은 가능한 모든 해결책을 인쇄 한 8 개의 여왕 문제에 대한 코드입니다.

#include<stdio.h> 


int abs(int a){ 
     return a>0? a : -a; 
} 

int isSafe(int col[],int row){ 
     int row2,col2,i,yDiff,xDiff; 
       if(row == 0) return 1; 


    for(row2=0;row2<row;row2++){ 
        if(col[row2] == col[row]) 
          return 0; 

        xDiff = col[row2] - col[row]; 
        xDiff = abs(xDiff); 
        yDiff = row - row2; 
        if(xDiff == yDiff) 
            return 0; 
      } 

    return 1; 

}

int Nqueen(int col[],int n, int row){ 
     int i; 
     if(row==n){ 
       printf("\n"); 
       for(i=0;i<n;i++) 
         printf("%d ",col[i]+1); 

     }else{ 
       for(i=0;i<n;i++){ 
        col[row] = i; 
        if(isSafe(col,row)){ 
          queen(col,n,row+1); 
        } 

      } 
    } 

}

int main(){ 
     int col[8]; 
     queen(col,8,0); 

}