Algorytmy do rozwiązania N Queens Puzzle Domination

Question

Rozwiązałem bardziej ogólny problem N Queens, ale teraz szukam algorytmu do rozwiązania problemu N Queens Domination.

„Biorąc pod uwagę n × n pokładzie, znaleźć numer dominacja, która jest minimalna liczba królowych (lub innych elementów) potrzebnych do ataku lub zajmują każdy kwadrat. Na pokładzie 8 x 8, królowej numer dominacji to 5. " - Wikipedia

Szukałem intensywnie i nie mogę znaleźć nic, ale prac naukowych na temat tego problemu, nic zdalnie zrozumiałe.

Moje pierwsze myśli to po prostu postawić Królową, a następnie umieścić następną Królową w miejscu, które może zaatakować większość innych kwadratów i tak dalej. Jednakże, chociaż może to generować rozwiązanie, nie mogę znaleźć sposobu na zagwarantowanie, że to rozwiązanie jest rozwiązaniem minimalnym.

Każda pomoc będzie doceniona, dzięki.

Answer 1

Korzystając z algorytmu, można wygenerować wszystkie możliwe kombinacje i wziąć od niego minimum. Wskazówki: Użyj rekurencji i nie przetwarzaj podobnych warunków (ani nie buforuj ich) jak symetryczne miejsce docelowe, ta sama kolejność i tak dalej.

Answer 2

Poniższe nie jest skuteczne, ale zadziała.

Powtórz problem jako problem z programowaniem całkowitoliczbowym. Każdy kwadrat na planszy ma wartość 0 lub 1. Dla dowolnego kwadratu suma jego wartości i wszystkich atakujących kwadratów powinna wynosić dokładnie 1. I chcesz zminimalizować łączną sumę.

Answer 3

W duchu tego, że jest to zadanie domowe, nie dostarczę rozwiązania, ale raczej serię pytań, które doprowadzą do rozwiązania. Poniżej znajduje się sposób na odpowiedź "czy możesz zdominować planszę z królami n?" Następnie możesz znaleźć numer dominacji, testując n = 1, n = 2, ...

1) Umieszczając królową w pozycji 1 *, możesz dominować we wszystkich pozostałych pozycjach, do których nie dotarła królowa 1, umieszczając (n - 1) queens w (n - 1) pozycjach wybranych z (2,3, ...)?

2) Jeśli nie, możesz umieścić królową na pozycji 2, a następnie zdominować wszystkie pozostałe pozycje nieosiągnięte przez królową 1, umieszczając (n - 1) królowych w (n - 1) wybranych pozycjach (3,4 , ...)?

3) tak dalej ... czyli miejsce pierwsza królowa w pozycji 3, a następnie pozycji 4 itd

Zauważ, że to rozwiązanie jest rekurencyjna - na każdym rekursji „pozostałe pozycje dodać Queen” i "pozycje, które jeszcze nie są osiągalne dla żadnej królowej" są przekazywane jako argumenty. Gdy "pozycje, które nie są jeszcze dostępne dla żadnej królowej", są puste, znalazłeś rozwiązanie.

* uporządkuj wszystkie pozycje planszy w pewien sposób, na przykład od lewej do prawej, od góry do dołu. Tak więc 64 pozycje na planszy 8x8 można odnieść do indeksu (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; 
    }