Queen Domination by SAT Solving
Taha Rostami, Curtis Bright · 2025
Read Queen Domination by SAT Solving by Taha Rostami, Curtis Bright (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-11945.txt.
Introduction
Taha Rostami and Curtis Bright solve a chess puzzle with SAT tools in 2025. The queen domination task asks for the fewest queens that can attack every square on a board. Past hunts used custom search code whose results rest on trust in that code.
Their frame adds helper values for rows, files, and diagonals so the solver sees the board shape. Proof files let any reader check each claim on its own. The work fixes a past count error for the 16 board and settles the open 19 board case in full.
Catalog record
| CREATOR | Taha Rostami, Curtis Bright |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-11945
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Queen Domination by SAT Solving Taha Rostami, Curtis Bright Abstract The queen domination problem asks for the minimum number of queens needed to attack all squares on an n × n 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, these approaches have not provided proofs that can be independently verified by third-party checkers. In contrast, this paper aims to combine efficiency with verifiability. We reduce the problem to a propositional satisfiability problem (SAT) using a straightforward encoding, and solve the resulting formulas with modern SAT solvers capable of generating proof certificates. By improving the SAT encoding with a novel literal ordering strategy, and leveraging established techniques such as static symmetry breaking and the Cube-and-Conquer paradigm, this paper achieves both performance and trustworthiness. Our approach discovers and corrects a discrepancy in previous results for n = 16 n=16 and resolves the previously open case n = 19 n=19 . 1 Introduction Given an n\times n chessboard, the queen domination problem asks for the minimum number of queens, denoted \gamma(Q_{n}) , required to cover all squares of the board [ 1 ] . A queen in chess is a piece that covers all squares in the same row, column, and diagonals from its position. For over a century and a half, mathematicians have studied not only the queen domination problem itself but also various related variants [ 1 ] . For example, in addition to determining the optimal value of \gamma(Q_{n}) , researchers have been interested in enumerating all distinct solutions of an n\times n chessboard up to isomorphism [ 2 ] . The latter is the primary focus of this paper. Figure 1 provides a concrete illustration of the minimum queen domination problem on a 4\times 4 chessboard. It presents all 12 optimal solutions and highlights their classification into three isomorphism classes based on board symmetries. Figure 1: A minimum of two queens is necessary to dominate all squares of a 4\times 4 chessboard. While there exist 12 distinct configurations that achieve this, many are symmetric under rotation and reflection. Up to isomorphism, these reduce to only three essentially different solutions, as highlighted in the figure. Before the advent and widespread use of computers in mathematics, early efforts to study the problem focused on establishing tighter theoretical bounds [ 3 , 4 , 5 ] and solving small open cases manually [ 6 ] . Analytical work continues to this day [ 7 ] . However, with the rise of computational methods, previously open cases have increasingly been tackled using algorithmic and computer-based search [ 2 , 8 , 9 ] . This has led to a fruitful synergy between theoretical and practical approaches: theorists provide tighter bounds to narrow the search space, while practitioners solve specific instances and generate data that inform further theoretical insights. A more detailed discussion of prior contributions is provided in Section 5 . Two theoretical observations are particularly useful for constraining the queen domination problem: the inequality \gamma(Q_{n})-\gamma(Q_{n-1})\leq 1 restricts how quickly the minimum number of queens can increase as n grows, and the lower bound \gamma(Q_{n})\geq\lceil(n-1)/2\rceil further narrows the range of candidate values [ 3 ] . Together, these bounds often reduce the number of values that need to be checked for a given n to just one or two. Recently, the tool Unidom [ 2 ] was used to determine \gamma(Q_{n}) for all n\leq 25 , as well as all (non-isomorphic) solutions using exactly \gamma(Q_{n}) queens for boards with n\leq 18 . Despite the value of computational methods, they come with inherent risks regarding correctness. Since results depend on software (typically custom-written code), the potential of bugs can undermine confidence in reported outcomes. This concern is not hypothetical: discrepancies in computational results have been documented in computer-assisted proofs of other problems, such as in Lam’s problem of proving the nonexistence of a projective plane of order ten [ 10 ] . Even though Lam’s problem was solved by two independent computational implementations [ 11 , 12 ] , discrepancies in the intermediate results of both implementations were later discovered, including the discovery of partial planes that were asserted to not exist but actually do [ 13 ] . Unfortunately, it is simply a reality of software development that even the most well-tested programs have bugs [ 14 ] . This is particularly important for code that purports to find all solutions of a mathematical problem: how can we have confidence that all solutions were indeed found? One promising direction is the use of Boolean satisfiability problem (SAT) solvers. SAT solvers have already been successfully applied to a number of difficult combinatorial problems in recent years, including the Boolean Pythagorean Triples problem [ 15 ] , a case of the Erdős Discrepancy Conjecture [ 16 ] , Lam’s problem [ 10 ] , the enumeration of Williamson matrices [ 17 ] , and Ramsey number computations [ 18 ] . Rather than developing a custom search algorithm—an error-prone and time-consuming endeavor—researchers instead encode the problem in propositional logic. Many combinatorial problems have natural and compact Boolean encodings, and these are often simpler and more reliable to implement compared to custom software. These logical formulations are then passed to SAT solvers which are highly optimized and extensively tested search engines. Modern SAT solvers also output formal resolution proofs in the case of unsatisfiability, enabling independent certification of unsatisfiability results. Unidom is a state-of-the-art search tool written by W. Bird that was used to resolve open instances of the queen domination problem, including the largest board sizes reported in the literature [ 2 ] . During the course of our investigation, we discovered a bug that causes Unidom to not enumerate all solutions of the queen domination problem when run under certain configurations. Details of a failing testcase are provided in Appendix A . In our work, we adopt a SAT-based approach to first certify the correctness of all previously reported queen domination results for chessboard sizes n\leq 18 and also solve the open instance n=19 under the model enumeration setting—i.e., enumerating all optimal solutions up to isomorphism. Our results are detailed in Section 3 . Even with highly efficient modern SAT solvers, the task of enumerating all solutions of the queen domination problem remains computationally expensive. Domain-specific solvers written for the domination problem, such as Unidom , in some cases can even outperform SAT solvers by incorporating custom heuristics and stronger domain-specific reasoning. Modern SAT solvers, commonly known as conflict-driven clause learning (CDCL) solvers, operate on a general-purpose Boolean representation and rely primarily on unit propagation and clause learning. As such, a non-trivial part of our work lies in carefully optimizing the SAT encoding to make the most effective use of the SAT solver’s capabilities. Our SAT approach is detailed in Section 2 , while Section 4 presents experiments comparing its performance with other encoding methods. The main contributions of this paper are: 1. We develop a SAT encoding of the queen domination problem and investigate various