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(1−yi,j)∑j′xi,j′+∑i′xi′,j+∑i′,j′|i′−j′=i−jxi′,j′+∑i′,j′|i′+j′=i+jxi′,j′−3xi,j≥M⋅yi,j∀i,j∑i,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
- More queens problems, https://yetanothermathprogrammingconsultant.blogspot.com/2018/12/more-queens-problems.html
- 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
- Maximum Queens Chess Problem, https://www.gams.com/latest/gamslib_ml/queens.103
No comments:
Post a Comment