NP-completeness of minimal queen completion on chessboards
NP-completeness of minimal queen completion on chessboards
Let be a positive integer and let be a set of queens placed on an chessboard. For a nonnegative integer , the minimal chessboard domination queen completion problem asks whether there is a set of size such that and dominates the chessboard.
Chessboard queen completion conjecture. The minimal chessboard domination queen completion problem is NP-complete.
The problem concerns completing a prescribed partial queen placement to a dominating placement with a specified increase in size. The paper presents the claim as an open conjecture and does not provide a proof of NP-completeness.
Sources & referencesView supporting material
Primary source
Alexis Langlois-Rémillard, Mia Müßig and Érika Róldan, “Complexity of chess domination problems”, arXiv:2211.05651 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.