backtracking을 사용하는 n queens 알고리즘의 기본 논리

Question

이 n-queens 용 프로그램은 역 추적을 위해 이상한 논리를 사용합니다. 코드를 여러 번 추적하려고했지만 항상 혼란스러워합니다. 나는 실제로 장소 (int pos) 기능과 혼동된다.

#include<stdio.h> 
#include<conio.h> 
int a[30],count=0; 
int place(int pos) 
{ 
    int i; 
    for(i=1;i<pos;i++) 
    { 
     if((a[i]==a[pos]) || ((abs(a[i]-a[pos])==abs(i-pos)))) 
     { 
      return 0; 
     } 
    } 
    return 1; 
} 

void print_sol(int n) 
{ 
    int i,j; 
    count++; 
    printf("\nSOLUTION #%d\n",count); 
    for(i=1;i<=n;i++) 
    { 
     for(j=1;j<=n;j++) 
     { 
      if(a[i]==j) 
       printf("Q\t"); 
      else 
       printf("*\t"); 
     } 
     printf("\n"); 
    } 
} 



void queen(n) 
{ 
    int k=1; 
    a[k]=0; 
    while(k!=0) 
    { 
     a[k]++; 
     while(a[k]<=n && !place(k)) 
      a[k]++; 
     if(a[k]<=n) 
     { 
      if(k==n) 
       print_sol(n); 
      else 
      { 
       k++; 
       a[k]=0; 
      } 
     } 
     else 
      k--; 
    } 
} 

void main() 
{ 
    int n; 
    clrscr(); 
    printf("\nEnter the number of queens:"); 
    scanf("%d",&n); 
    queen(n); 
    getch(); 
} 

어떻게 자동으로 역 추적하는지 알고 싶습니까?

Answer 1

place은 행 pos에있는 여왕이 a[pos] 열에 배치 될 수 있는지 여부를 확인하기 만합니다.

되돌아가 queens 함수이며, 행 k에서 퀸을 배치 할 때, 우선, a[k] 여왕

a[k]++;  // here, a[k] was not a valid position and no smaller was valid, so increment 
while(a[k]<=n && !place(k)) // while the position is invalid, check next 
    a[k]++; 
if(a[k]<=n) // if a valid column was found 
{ 
    if(k==n) // that was the last row, done 
     print_sol(n); 
    else  // next row 
    { 
     k++; 
     a[k]=0; 
    } 
} 
else // no possible column found (a[k] > n), so backtrack 
k--; // check for next possible column in previous row 

Answer 2

모든 것 pos은 pos보다 적은 수의 여왕이 공격 할 수 있는지를 결정합니다. 이것은 여왕 #pos가 다른 여왕과 같은 열 또는 대각선에 있는지 차례대로 검사하여 확인합니다. 따라서 place(pos)이 1을 반환하면 a[pos]의 값은 여왕이 합법적으로 배치 될 수있는 열의 0부터 시작하는 인덱스임을 의미합니다.