Queen Domination by SAT Solving

The queen domination problem asks for the minimum number of queens required to attack all squares on an $n \times n$ chessboard.

Once this optimal number is known, determining the number of distinct solutions up to isomorphism has also attracted considerable attention.

Previous work has introduced specialized and highly optimized search procedures to address open instances of the problem.

While efficient in terms of runtime, confidence in their computational results ultimately depends on the correctness of these specialized implementations, motivating approaches that additionally provide independently verifiable correctness certificates.

To this end, we present a proof-producing SAT framework for the queen domination problem based on an encoding that introduces auxiliary variables representing whether rows, columns, diagonals, and anti-diagonals contain queens, thereby exposing the geometric structure of the problem to the SAT solver.

The framework is further strengthened through a novel literal-ordering strategy, symmetry breaking, a modern Cube-and-Conquer framework, and a unified proof-generation and verification pipeline.

Together, these techniques yield both high performance and independently verifiable correctness.

Our results uncover and correct a discrepancy in the previously reported enumeration for $n=16$ and resolve the previously open case $n=19$.