Algoritmo para resolver el rompecabezas de N Queens Dominación

Question

He resuelto el problema más genérico de N Queens, pero ahora estoy buscando un algoritmo para resolver el problema de N Queens Domination.

"Dado un n × n bordo, encuentra el número dominación, que es el número mínimo de reinas (u otras piezas) necesarios para atacar u ocupar todas las plazas. Para el tablero de 8 × 8, de la reina el número de dominación es 5. " - Wikipedia

He buscado mucho y no puedo encontrar cualquier cosa menos trabajos académicos sobre este problema, nada remotamente comprensible.

Mis primeras ideas son simplemente colocar una Reina y luego colocar la próxima Reina en el lugar que pueda atacar a la mayoría de los otros cuadrados, y así sucesivamente. Sin embargo, si bien esto puede generar una solución, no puedo encontrar la manera de garantizar que esa solución sea la mínima.

Cualquier ayuda sería apreciada, gracias.

Answer 1

Usando su algoritmo, puede generar todas las combinaciones posibles y tomar un mínimo de eso. Sugerencias: utilice la recursividad para esto y no procese condiciones similares (o la guarde en caché) como la ubicación simétrica, el mismo orden, etc.

Answer 2

Lo siguiente no es eficiente, pero funcionará.

Repita el problema como un problema de programación entero. Cada cuadrado en el tablero es 0 o 1. Para cualquier cuadrado, la suma de sí mismo y todos los cuadrados atacantes deben ser exactamente 1. Y desea minimizar la suma total.

Answer 3

En el espíritu de ser una pregunta de tareas, no proporcionaré una solución, sino una serie de preguntas que conducen a una solución. La siguiente es una forma de responder "¿puedes dominar el tablero con n reinas?" A continuación, puede encontrar el número de dominación probando n = 1, n = 2, ...

1) Al colocar una reina en la posición 1 *, puede dominar todas las posiciones restantes no alcanzadas por la reina 1 colocando (n - 1) reinas en (n - 1) posiciones elegidas entre (2,3, ...)?

2) De lo contrario, puede colocar una reina en la posición 2 y luego dominar todas las posiciones restantes no alcanzadas por la reina 1 colocando (n - 1) reinas en (n - 1) posiciones elegidas de (3,4 , ...)?

3) un así sucesivamente ... es decir lugar primero reina en la posición 3, entonces la posición 4, etc.

Tenga en cuenta que esta solución es recursivo - en cada recursión, "posiciones restantes para añadir una reina" y "posiciones que aún no son alcanzables por ninguna reina" se pasan como argumentos. Cuando "las posiciones aún no alcanzables por ninguna reina" están vacías, ha encontrado una solución.

* ordene todas las posiciones de la placa de alguna manera, por ejemplo de izquierda a derecha, de arriba a abajo. De modo que las 64 posiciones en una placa de 8x8 se pueden consultar solo por un índice (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; 
    }