🔢 mathematics

Queen Domination by SAT Solving

This paper presents a high-performance, proof-producing SAT framework that resolves the previously open $n=19$ queen domination case and corrects the enumeration for $n=16$ by leveraging a geometrically informed encoding, symmetry breaking, and a unified verification pipeline to ensure independently verifiable correctness.

Original authors: Taha Rostami, Curtis Bright

Published 2026-07-30

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Taha Rostami, Curtis Bright

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where math isn't just about numbers on a page, but about solving puzzles so complex that even the smartest human brains get dizzy. This is the realm of combinatorial search, a branch of computer science and mathematics dedicated to finding the best way to arrange things. Think of it like trying to find the perfect seating chart for a massive wedding where every guest has specific rules about who they can sit next to, or figuring out the absolute minimum number of security guards needed to watch every corner of a museum without leaving a blind spot.

One of the most famous puzzles in this field is the Queen Domination Problem. Picture a chessboard. A queen is a powerful piece that can attack everything in its row, its column, and both of its diagonal paths. The question is simple but tricky: What is the smallest number of queens you need to place on an $n \times n$ board so that every single square is under attack? It sounds easy for a small board, but as the board gets bigger, the number of possible arrangements explodes into the billions, trillions, and beyond. For over a century, mathematicians have been trying to solve this, not just to find the number, but to count exactly how many different ways you can arrange those queens. Why does this matter? Because solving these puzzles helps us understand how to organize complex systems, from scheduling flights to designing computer chips. But there's a catch: when computers do the math, they can make mistakes, and sometimes they miss the answer entirely.

This is where Taha Rostami and Curtis Bright step in with their paper, "Queen Domination by SAT Solving." They tackled the problem of counting all the unique ways to place the minimum number of queens on chessboards up to size 19. Instead of writing a custom program to hunt for solutions like previous researchers did, they translated the entire chessboard puzzle into a language that a SAT solver (a super-smart logic machine) understands. Think of a SAT solver as a detective that checks if a set of rules can ever be true. If the detective says "no," it can prove it with a certificate that anyone else can check to make sure the detective didn't lie.

The authors built a special "translation" of the chessboard that highlighted the geometry of the game, using a clever trick called a Hilbert curve to organize the clues so the detective could find the answer faster. They also used a strategy called Cube-and-Conquer, which is like splitting a giant, impossible-to-eat cake into thousands of tiny, manageable slices that different computers can eat at the same time. The result? They didn't just solve the puzzle; they proved their solution was 100% correct.

Their work uncovered a surprising error in the history of this problem. For a 16x16 board, previous experts thought there were only 43 unique ways to place the queens. Rostami and Bright proved that there are actually 371 ways—a massive difference that suggests the old computer program had a hidden bug that was missing most of the solutions. Furthermore, they solved a case that had been open for a long time: the 19x19 board. They found that there are exactly 11 unique ways to dominate that board with the minimum number of queens. By generating "proof certificates" for every single result, they gave the math community a level of trust that was previously impossible, showing that when you combine smart encoding with rigorous proof-checking, you can solve problems that even the best specialized software might miss.

Technical Summary: Queen Domination by SAT Solving

Problem Definition
The queen domination problem seeks the minimum number of queens, denoted $\gamma(Q_n)$ , required to attack every square on an $n \times n$ chessboard. Beyond determining this minimum value, a significant challenge lies in enumerating all distinct solutions up to isomorphism (accounting for board symmetries such as rotation and reflection). While the optimal values for $\gamma(Q_n)$ have been established for $n \le 25$ using specialized search tools like UNIDOM, the enumeration of non-isomorphic solutions for larger boards remains computationally intensive. A critical concern in this domain is the reliability of computational results; previous discrepancies in other combinatorial proofs (e.g., Lam's problem) and the discovery of bugs in specialized solvers highlight the need for independently verifiable correctness certificates.

Methodology
The authors propose a proof-producing Boolean Satisfiability (SAT) framework to address the queen domination problem. Rather than implementing a custom search algorithm, the problem is encoded into a propositional formula in Conjunctive Normal Form (CNF). The methodology relies on several key technical innovations:

Line-Variable Encoding: The core innovation is the introduction of auxiliary Boolean variables representing whether specific geometric lines (rows, columns, diagonals, and anti-diagonals) contain at least one queen.
- Queen Variables ( $Q_i$ ): Indicate if a queen is placed on square $i$ .
- Line Variables ( $L_\ell$ ): Indicate if line $\ell$ is "active" (contains a queen).
- Constraints: Clauses ensure that if a line is active, a queen exists on it. Domination is expressed by requiring that for every square, at least one of its four intersecting lines is active. Cardinality constraints limit the total number of queens ( $\sum Q_i \le \gamma$ ) and the total number of active lines ( $\sum L_\ell \le 4\gamma$ ).
Cardinality Encoding and Literal Ordering:
- The cardinality constraints are encoded using totalizer-based methods. The queen constraint uses a standard totalizer compatible with the Cube-and-Conquer framework, while the line constraint uses a modulo totalizer for performance.
- Hilbert Curve Ordering: A novel literal-ordering strategy is applied to the queen cardinality constraint. By traversing the board via a Hilbert curve, spatially adjacent squares are grouped together in the counting tree. This preserves spatial locality, leading to stronger unit propagation. Experiments showed this ordering solved the $n=14$ instance approximately 31.5 times faster than default ordering.
Symmetry Breaking: To eliminate redundant exploration of symmetric solutions, the framework enforces lexicographic ordering constraints (based on Warwick Harvey's method) between the original queen configuration and its seven non-identity geometric transformations. This reduced solving times significantly in preliminary tests (e.g., 6.64× speedup for $n=15$ ).
Cube-and-Conquer: For larger instances, the search space is partitioned into independent subproblems (cubes) by branching on auxiliary variables from the totalizer encoding. This allows parallel solving and improves scalability without relying on individual queen placements for partitioning.
Proof Generation and Verification: The framework uses cadical-exhaust to enumerate all models by iteratively adding blocking clauses. It generates DRAT proofs with "trusted clauses" to certify completeness. These proofs are independently verified using drat-trim-t, ensuring that the results do not rely on the internal correctness of the solver's search logic, but only on the encoding and the proof checker.

Key Results
The study successfully enumerated non-isomorphic minimum queen domination solutions for all $n \le 19$ . The results include:

Correction of Literature: For $n=16$ , the paper identifies a discrepancy in previous reports. While the specialized solver UNIDOM reported 43 non-isomorphic solutions, the SAT framework proves there are exactly 371. The authors attribute this to a bug in UNIDOM that causes valid solutions to be missed under specific configurations.
Resolution of Open Case: The previously open case of $n=19$ is resolved, establishing that there are exactly 11 non-isomorphic minimum solutions.
Performance: The SAT framework consistently outperformed the specialized solver UNIDOM on non-trivial instances. For $n=19$ , the SAT approach took approximately 171,575 seconds (CPU time) for enumeration, compared to UNIDOM's 714,733 seconds. The inclusion of line variables was crucial; a preliminary version without them took 22.8 times longer to solve and verify the $n=19$ instance.

Significance and Claims
The paper claims that its primary contribution is providing a high-performance, independently verifiable solution to the queen domination enumeration problem. By shifting from specialized search code to a proof-producing SAT framework, the authors reduce the "trust" required in the computational process. The correctness of the results now depends solely on the SAT encoding and the external proof verifier, rather than the complex, custom-written logic of a specialized solver.

The work demonstrates that careful encoding design—specifically the introduction of auxiliary variables to expose geometric structure, the use of global constraints, and geometry-aware literal ordering—can make proof-producing SAT solving competitive with, and superior to, highly optimized domain-specific solvers. The authors make their source code and solution data publicly available to facilitate further verification and research.

Technical Summary: Queen Domination by SAT Solving

More like this