Dominating the chessboard with queens

Challenge solution

By solving the model with an integer optimization solver like Gurobi, it can be proven that the minimum domination number for an $8 \times 8$ board is 5 queens.

One of the optimal configurations obtained places the queens as shown in the following figure:

To model this problem, we define the attack range of a queen from each cell on the board. If we place a queen in cell $(r,c)$, it dominates all cells aligned horizontally, vertically, or diagonally.

Index sets

• \(\mathcal{I} = \{1, 2, \dots, 8\}\): Board rows.
• \(\mathcal{J} = \{1, 2, \dots, 8\}\): Board columns.
• \(\mathcal{A}_{ij} \subset \mathcal{I} \times \mathcal{J}\): Set of cells $(r,c)$ from which a queen would attack cell $(i,j)$ (including cell $(i,j)$ itself). A cell $(r,c) \in \mathcal{A}_{ij}$ if it satisfies any of these conditions:
  • Same row: \(r = i\)
  • Same column: \(c = j\)
  • Same diagonal: \(\lvert r - i \rvert = \lvert c - j \rvert\)

Decision variables

• \(x_{ij} = 1\) if a queen is placed in cell $(i,j)$, and $0$ otherwise, $\forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}$

Objective function

We want to minimize the total number of queens placed on the board:

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

The domination constraints ensure that every cell $(i,j)$ is covered:

Coverage (Domination) Constraint:

For each cell $(i,j)$, the sum of queens in cells that can attack it must be at least $1$:

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

Variable domains

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

Source code

The Python implementation using gurobipy to build the adjacency matrix and solve the domination problem is available in the GitHub repository.

GitHub Repository: fjmartincampo/QueensDomination