Improved lower bounds for Queen's Domination via an exactly-solvable relaxation

arXiv2304.06620MaRDI QIDQ6432989FDOQ6432989

Authors: Archit Karandikar, Akashnil Dutta 

Publication date: 13 April 2023

Abstract: 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 $mimesn$ chessboard so that they either attack or occupy every cell? We propose a novel relaxation of the Queen's Domination problem and show that it is exactly solvable on both square and rectangular chessboards. As a consequence, we improve on the best known lower bound for rectangular chessboards in $approx12.5\mathrm{\%}$ of the non-trivial cases. As another consequence, we simplify and generalize the proofs for the best known lower-bounds for Queen's Domination of square $nimesn$ chessboards for $nequiv0,1,2mod4$ using an elegant idea based on a convex hull. 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 $nequiv3mod4$ (and $n>11$). These simple-to-state conjectures may also be of independent interest.

Has companion code repository: https://github.com/architkarandikar/queens-domination

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Lattice packing and covering (number-theoretic aspects) (11H31) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

This page was built for publication: Improved lower bounds for Queen's Domination via an exactly-solvable relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432989)