Dominando el tablero con reinas

Solución del reto

Al resolver el modelo con un solucionador de optimización entera como Gurobi, se demuestra que el número mínimo de dominación para un tablero de $8 \times 8$ es de 5 reinas.

Una de las configuraciones óptimas obtenidas sitúa las reinas según la siguiente figura:

Para modelar este problema, definimos el alcance de ataque de una reina desde cada celda del tablero. Si colocamos una reina en la celda $(r,c)$, esta ejerce su dominio sobre todas las celdas alineadas horizontal, vertical o diagonalmente.

Conjuntos de índices

• \(\mathcal{I} = \{1, 2, \dots, 8\}\): Filas del tablero.
• \(\mathcal{J} = \{1, 2, \dots, 8\}\): Columnas del tablero.
• \(\mathcal{A}_{ij} \subset \mathcal{I} \times \mathcal{J}\): Conjunto de celdas $(r,c)$ desde las cuales una reina atacaría la celda $(i,j)$ (incluyendo la propia celda $(i,j)$). Una celda $(r,c) \in \mathcal{A}_{ij}$ si cumple alguna de estas condiciones:
  • Misma fila: \(r = i\)
  • Misma columna: \(c = j\)
  • Misma diagonal:$ $ \(\lvert r - i \rvert = \lvert c - j \rvert\)

Variables de decisión

• \(x_{ij} = 1\) si se coloca una reina en la celda $(i,j)$, y $0$ en caso contrario, $\forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}$

Función objetivo

Queremos minimizar el número total de reinas colocadas en el tablero:

\[\min z = \sum_{i \in \mathcal{I}} \sum_{j \in \mathcal{J}} x_{ij}\]

Las restricciones de dominación se aseguran de que cada casilla $(i,j)$ esté cubierta:

Restricción de Cobertura (Dominación):

Para cada casilla $(i,j)$, la suma de las reinas en celdas que pueden atacarla debe ser como mínimo $1$:

\[\sum_{(r,c) \in \mathcal{A}_{ij}} x_{rc} \geqslant 1 \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}\]

Dominio de las variables

\[x_{ij} \in \{0, 1\} \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}\]

Código fuente

La implementación en Python utilizando gurobipy para construir la matriz de adyacencias y resolver el problema de dominación se encuentra disponible en el repositorio de GitHub.

Repositorio GitHub: fjmartincampo/QueensDomination