The Queen's Domination problem, studied for over 160 years, poses the following question: What is the least number of queens that can be arranged on a m × n chessboard so that they either attack or occupy every cell? We propose a relaxation of the Queen's Domination problem and solve it exactly for rectangular chessboards. As a consequence, we improve on the best known lower bound for rectangular chessboards for one-eighth of the nontrivial cases. As another consequence, we generalize and provide a new interpretation of the best known lower bounds for Queen's Domination of square n × n chessboards for n ≡ {0, 1, 2} mod 4.Finally, we show some results and make some conjectures towards the goal of simplifying the long complicated proof for the best known lower bound for square boards when n ≡ 3 mod 4 (and n > 11). These simply stated conjectures may also be of independent interest.
Classification :
05C69, 05B15
Mots-clés :
\(n\)-queens problem
Affiliations des auteurs :
Archit Karandikar
1
;
Akashnil Dutta
2
1
Waymo LLC
2
LinkedIn Inc
Archit Karandikar; Akashnil Dutta. Improved lower bounds for Queen's Domination via an exactly-solvable relaxation. The electronic journal of combinatorics, Tome 31 (2024) no. 4. doi: 10.37236/12003
@article{10_37236_12003,
author = {Archit Karandikar and Akashnil Dutta},
title = {Improved lower bounds for {Queen's} {Domination} via an exactly-solvable relaxation},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {4},
doi = {10.37236/12003},
zbl = {1556.05125},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12003/}
}
TY - JOUR
AU - Archit Karandikar
AU - Akashnil Dutta
TI - Improved lower bounds for Queen's Domination via an exactly-solvable relaxation
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/12003/
DO - 10.37236/12003
ID - 10_37236_12003
ER -
%0 Journal Article
%A Archit Karandikar
%A Akashnil Dutta
%T Improved lower bounds for Queen's Domination via an exactly-solvable relaxation
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/12003/
%R 10.37236/12003
%F 10_37236_12003
