An upper bound for the minimum number of queens covering the \(n {\times} n\) chessboard
A set of queens on an \(n\times n\) chessboard \(Q_n\) dominates the chessboard if every field is either occupied or attacked by a queen. It is an old problem to determine the exact value of the minimum number \(\gamma(Q_n)\) of queens needed to dominate \(Q_n\). Using explicit constructions the authors prove that \(\gamma(Q_n)\leq \frac{8}{15}n+O(1)\) which considerably narrows the gap between the best known lower bound (essentially due to Spencer) and the previously known best upper bound due to the same authors and Cockayne.
scientific article; zbMATH DE number 1792332
scientific article