Loading [MathJax]/jax/output/CommonHTML/jax.js

Monday, December 10, 2018

More queens problems (2)

In [1], I discussed the Minimum Dominating Set of Queens Problem. Here is a variant:

Given an n×n chess board, place n queens on the board such that the number of squares not under attack is maximized. 

For an n=8 problem, the maximum number of non-dominated squares is 11. An example is:

11 white pawns are not under attack

We base the model on the one in [1]. First we define two sets of binary variables:

xi,j={1if square (i,j) is occupied by a queen0otherwiseyi,j={1if square (i,j) is under attack0otherwise

The model can look like:


Maximum Non-Dominated Squares Problem
maxz=i,j(1yi,j)jxi,j+ixi,j+i,j|ij=ijxi,j+i,j|i+j=i+jxi,j3xi,jMyi,ji,ji,jxi,j=nxi,j,yi,j{0,1}

The funny term 3xi,j is to compensate for double counting occurrences of xi,j in the previous terms [1]. We need to find a reasonable value for M. An upper bound is M=n. For n=8, there are 48 different optimal solutions.

The problem n=9 has one structural optimal solution (with 18 unattacked positions), and 3 variants by symmetry:


Is there a good way to find only structural solutions? One way is to use your own cuts as in [4], If we want to use the solution pool technology, we need to invent a constraint that forbids some symmetry (or have an objective that favors some of symmetric versions).

References


  1. More queens problems, https://yetanothermathprogrammingconsultant.blogspot.com/2018/12/more-queens-problems.html
  2. Bernard Lemaire, Pavel Vitushinkiy, Placing n non-dominating queens on the n×n Chessboard, 2011, https://www.ffjm.org/upload/fichiers/N_NON_DOMINATING_QUEENS.pdf
  3. Maximum Queens Chess Problem, https://www.gams.com/latest/gamslib_ml/queens.103

No comments:

Post a Comment