NP-completeness of minimal queen completion on chessboards

Let nn be a positive integer and let QQ be a set of kk queens placed on an n×nn\times n chessboard. For a nonnegative integer ll, the minimal chessboard domination queen completion problem asks whether there is a set QQ' of size k+lk+l such that QQQ\subset Q' and QQ' 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.