N Queens Domination 퍼즐을 풀 수있는 알고리즘

Question

좀 더 일반적인 N Queens 문제를 풀었지만 N Queens Domination 문제를 해결하는 알고리즘을 찾고 있습니다.

"N 보드 ×는 n을 감안할 때, 공격 또는 매 1 평방를 차지하기 위해 필요한 왕비 (또는 다른 개)의 최소 수는 지배 번호를 찾을 수 있습니다. 8 × 8 보드를 들어, 여왕의 지배 번호는 5입니다. " - 위키 백과

나는 광범위하게 검색하고이 문제에 대한 학술 논문 아무것도하지만, 원격으로 이해할 수 아무것도 찾을 수 없습니다.

첫 번째 생각은 여왕을 내려 놓고 다음 여왕을 가장 많은 다른 사각형을 공격 할 수있는 장소에 배치하는 것입니다. 그러나 이것이 솔루션을 생성 할 수는 있지만, 솔루션이 최소한의 솔루션이라는 것을 보장 할 수있는 방법을 찾을 수는 없습니다.

감사합니다. 감사드립니다.

Answer 1

알고리즘을 사용하여 가능한 모든 조합을 생성하고 최소 조합을 취할 수 있습니다. 힌트 :이 재귀를 사용하고 대칭 배치, 같은 순서와 같은 유사한 조건 (또는 캐시)을 처리하지 마십시오.

Answer 2

다음은 효율적이지 않지만 작동합니다.

정수 프로그래밍 문제로 문제를 다시 설명하십시오. 보드의 모든 사각형은 0 또는 1입니다. 모든 사각형의 경우 자체와 모든 공격 사각형의 합은 정확히 1이어야합니다. 총합을 최소화하고자합니다.

Answer 3

숙제 문제라는 정신에서 나는 해결책을 제시하지 않고 해결책을 제시하는 일련의 질문을 제공 할 것입니다. 다음은 "n 퀸즈로 보드를 지배 할 수 있습니까?"라고 대답하는 방법입니다. 다음은 n = 1, n = 2, ...을 테스트하여 지배 번호를 찾을 수 있습니다.

1) 여왕을 1 * 위치에 놓으면 퀸 1에 도달하지 않은 나머지 위치를 모두 (2,3, ...)에서 선택된 (n - 1) 포지션의 여왕 (n - 1)

2) 퀸을 2 위에 올린 다음 (n-1) 퀸을 (n-1) , ...)?

3)를 3 위치, 4 위치에서 등등 ... 즉 장소 제 여왕이 용액 재귀 있음 등

주 - "퀸을 추가 할 위치를 나머지"각 순환에서, 및 "여왕이 아직 도달 할 수없는 직책"이 인수로 전달됩니다. "여왕이 아직 도달 할 수없는 위치"가 비어 있으면 해결책을 찾았습니다.

* 모든 보드 위치를 어떤 식 으로든, 예를 들어 왼쪽에서 오른쪽, 위에서 아래로 순서대로 정렬하십시오. 따라서 8x8 보드의 64 개 위치는 인덱스 (1..64)로 참조 할 수 있습니다.

Answer 4

int count; 

int safetyOfThisPosition(int col,int row,int *x) 

{ 

     int iterator; 
     for(iterator=0;iterator<col;iterator++) 
     { 
     if(row==x[iterator] || abs(col-iterator)==abs(row-x[iterator])) 
      return 0; 
     } 
     return 1; 
} 

void Nqueen(int col){ 

     int row,iterator; 
     static int x[N]; 
     for(row=0;row<N;row++) 
     { 
      if(safetyOfThisPosition(col,row,x)) 
      { 
       x[col]=row; 
       if(col==N-1) 
       { 
        for(iterator=0;iterator<=col;iterator++) 
       printf("%d ",x[iterator]); 
        printf("\n"); 
       } 
       else 
        Nqueen(col+1); 
      } 
     } 

    } 

int main(){ 

     Nqueen(0); 
     return 0; 
    }