More queens problems

In [1] the famous \(n\)-queens problem was discussed: how many queens can we place on a chess-board such that non of them are attacked by others. Interestingly, we had some non-obvious problem with Cplex enumerating the different configurations (due to tolerance issues).

A different problem is the Minimum Dominating Set of Queens Problem:

Find the minimum number of queens needed such that they dominate each square.

Here dominate means: either a square is under attack by at least one queen, or it is occupied by a queen.

To develop a Mixed Integer Programming model, we introduce the familiar binary variables:

\[x_{i,j} = \begin{cases} 1 & \text{if square \((i,j)\) is occupied by a queen}\\ 0 & \text{otherwise}\end{cases}\]

A square \((i,j)\) is dominated if:

1. \(x_{i,j}=1\): a queen is located here. This case will be covered by the following other cases, so we don't have to worry about this.
2. There is a queen in row \(i\): \[\sum_{j'} x_{i,j'} \ge 1\]
3. There is a queen in column \(j\):\[\sum_{i'} x_{i',j} \ge 1\]
4. There is a queen in the same diagonal. The diagonal is described by \((i',j')\) such that \(i'-j'=i-j\). So we have: \[\sum_{i',j'|i'-j'=i-j} x_{i',j'}\ge 1\] If you prefer you can write this as \[\sum_{i'|1 \le i'-i+j \le n } x_{i',i'-i+j} \ge 1 \] 
5. There is a queen in the same anti-diagonal. The anti-diagonal is described by \((i',j')\) such that \(i'+j'=i+j\). So we have: \[\sum_{i',j'|i'+j'=i+j} x_{i',j'}\ge 1\] This can also be written as \[\sum_{i'| 1 \le i+j-i' \le n} x_{i',i+j-i'} \ge 1\]

We can write these conditions in one big constraint. So we can write:

Minimum Dominating Set of Queens Problem
\[\begin{align}\min& \>\color{DarkRed}z=\sum_{i,j} \color{DarkRed} x_{i,j}\\ & \sum_{j'} \color{DarkRed}x_{i,j'} + \sum_{i'} \color{DarkRed}x_{i',j} + \sum_{i',j'|i'-j'=i-j} \color{DarkRed}x_{i',j'} +\sum_{i',j'|i'+j'=i+j} \color{DarkRed}x_{i',j'} \ge 1 && \forall i,j \\ & \color{DarkRed}x_{i,j}\in\{0,1\} \end{align}\]

For an \(8\times 8\) board, we need 5 queens. Here are two solutions:

You can verify that every unoccupied square is under attack.

Note that this formulation actually does a bit of double counting. E.g. when we look at the constraint for cell \((2,3)\) we see:

e(2,3)..  x(1,2) + x(1,3) + x(1,4) + x(2,1) + x(2,2) + 4*x(2,3) + x(2,4)
     
      + x(2,5) + x(2,6) + x(2,7) + x(2,8) + x(3,2) + x(3,3) + x(3,4) + x(4,1)
     
      + x(4,3) + x(4,5) + x(5,3) + x(5,6) + x(6,3) + x(6,7) + x(7,3) + x(7,8)
     
      + x(8,3) =G= 1 ; (LHS = 0, INFES = 1 ****)

We see that x(2,3) has a coefficient 4. This is harmless. However it looks a bit unpolished. With a little bit more careful modeling we can get rid of this coefficient 4. A complicated way would be: \[ \sum_{j'}x_{i,j'} + \sum_{i'|i'\ne i} x_{i',j} + \sum_{i',j'|i'-j'=i-j,i'\ne i, j'\ne j} x_{i',j'} +\sum_{i',j'|i'+j'=i+j,i'\ne i, j'\ne j} x_{i',j'} \ge 1 \>\> \forall i,j\] The first summation includes \(x_{i,j}\) while the other three summations exclude explicitly an occurrence of \(x_{i,j}\). Simpler is just to subtract \(3 x_{i,j}\): \[\sum_{j'} x_{i,j'} + \sum_{i'} x_{i',j} + \sum_{i',j'|i'-j'=i-j} x_{i',j'} +\sum_{i',j'|i'+j'=i+j} x_{i',j'}-3x_{i,j} \ge 1\>\> \forall i,j\] Here we just compensate for the double counting.

Now we see:

e(2,3)..  x(1,2) + x(1,3) + x(1,4) + x(2,1) + x(2,2) + x(2,3) + x(2,4) + x(2,5)
     
      + x(2,6) + x(2,7) + x(2,8) + x(3,2) + x(3,3) + x(3,4) + x(4,1) + x(4,3)
     
      + x(4,5) + x(5,3) + x(5,6) + x(6,3) + x(6,7) + x(7,3) + x(7,8) + x(8,3)

      =G= 1 ; (LHS = 0, INFES = 1 ****)

When we ask: how many different solution are there?, we use again the Cplex solution pool. And again, we have our tolerance problem:

pool.absgap	Number of solutions
0	2
0.5	4860

As the objective is integer valued, in some sense an absolute gap tolerance of 0.5 seems the safest. With this we find the correct number of solutions [2]. See [1] for a more in-depth discussion of this tolerance problem.

References

1. Chess and solution pool, http://yetanothermathprogrammingconsultant.blogspot.com/2018/11/chess-and-solution-pool.html.
2. Weisstein, Eric W.,  Queens Problem, http://mathworld.wolfram.com/QueensProblem.html
3. Henning Fernau, minimum dominating set of queens: A trivial programming exercise?, Discrete Applied Mathematics, Volume 158, Issue 4, 28 February 2010, Pages 308-318. This is about programming instead of modeling. The issues are very different.
4. Saad Alharbi and, Ibrahim Venkat, A Genetic Algorithm Based Approach for Solving the Minimum Dominating Set of Queens Problem, Hindawi Journal of Optimization, Volume 2017. I am not sure why a meta-heuristic is a good choice for solving this problem: you will not find proven optimal solutions.