Algoritmo per risolvere il puzzle di N Queens Domination

Question

Ho risolto il problema di N Queens più generico, ma ora sto cercando un algoritmo per risolvere il problema di N Queens Domination.

"Dato un n × scheda n, trova il numero dominio, che è il numero minimo di regine (o altri pezzi) necessari per attaccare o occupare ogni quadrato. Per il Consiglio 8 × 8, della regina il numero di dominazione è 5. " - Wikipedia

Ho cercato a lungo e non riesco a trovare nulla, ma documenti accademici su questo problema, nulla di lontanamente comprensibile.

I miei primi pensieri sono di mettere giù una Regina e poi piazzare la prossima Regina nel posto che può attaccare la maggior parte delle altre caselle, e così via. Tuttavia, mentre questo può generare una soluzione, non riesco a capire un modo per garantire che quella soluzione sia la soluzione minima.

Qualsiasi aiuto sarebbe apprezzato, grazie.

Answer 1

Utilizzando l'algoritmo, è possibile generare tutte le combinazioni possibili e prendere il minimo da esso. Suggerimenti: utilizzare la ricorsione per questo e non elaborare condizioni simili (o memorizzarlo nella cache) come il posizionamento simmetrico, lo stesso ordine e così via.

Answer 2

Quanto segue non è efficiente, ma funzionerà.

Restituisce il problema come un problema di programmazione in numeri interi. Ogni quadrato sul tabellone è 0 o 1. Per qualsiasi quadrato la somma di se stesso e di tutti i quadrati attaccanti dovrebbe essere esattamente 1. E si vuole minimizzare la somma totale.

Answer 3

Nello spirito di questa domanda di compiti a casa, non fornirò una soluzione, ma piuttosto una serie di domande che portano a una soluzione. Quello che segue è un modo per rispondere "puoi dominare la scacchiera con le regine n?" È quindi possibile trovare il numero di dominazione testando n = 1, n = 2, ...

1) Posizionando una regina nella posizione 1 *, è possibile quindi dominare tutte le posizioni rimanenti non raggiunte dalla regina 1 posizionando (n - 1) regine in (n - 1) posizioni scelte da (2,3, ...)?

2) In caso contrario, puoi posizionare una regina in posizione 2, e quindi dominare tutte le posizioni rimanenti non raggiunte dalla regina 1 posizionando (n - 1) regine in (n - 1) posizioni scelte da (3,4 , ...)?

3) una così via ... cioè luogo prima regina in posizione 3, poi posizione 4, ecc

noti che questa soluzione è ricorsiva - ad ogni ricorsione, "posizioni rimanenti per aggiungere una regina" e "le posizioni non ancora raggiungibili da nessuna regina" vengono passate come argomenti. Quando "le posizioni non ancora raggiungibili da nessuna regina" sono vuote, hai trovato una soluzione.

* ordinare tutte le posizioni della scheda in qualche modo, ad esempio da sinistra a destra, dall'alto in basso. In modo che le 64 posizioni su una scheda 8x8 possono essere riferite solo da un indice (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; 
    }