Abstract
In this article, we demonstrate how to solve a variety of problems and puzzles using the built-in SAT solver of the computer algebra system Maple. Once the problems have been encoded into Boolean logic, solutions can be found (or shown to not exist) automatically, without the need to implement any search algorithm. In particular, we describe how to solve the $n$-queens problem, how to generate and solve Sudoku puzzles, how to solve logic puzzles like the Einstein riddle, how to solve the 15-puzzle, how to solve the maximum clique problem, and finding Graeco-Latin squares.
Introduction
In computer science and mathematics, we often encounter NP-hard problems, such as the "Maximum Clique" problem or complex combinatorial puzzles. Traditionally, solving these requires writing specialized, "imperative" algorithms—step-by-step instructions on how to search for a solution. This process is time-consuming and often results in code that is less efficient than general-purpose tools.
This research addresses the gap between complex mathematical problems and the highly optimized world of Satisfiability (SAT) solvers. While SAT solvers are incredibly powerful, they usually require input in a rigid format called Conjunctive Normal Form (CNF), which is difficult for humans to write. By leveraging modern tools like Maple, researchers can bridge this gap, expressing problems in natural logic and solving them automatically.
Methodology: The Declarative Approach
The core methodology presented is Declarative Programming via SAT encoding. Instead of instructing the computer how to search, the user defines what a valid solution looks like using Boolean variables and logical operators (AND, OR, NOT, Implication).
Key technical components of this workflow include:
- MapleSAT: A state-of-the-art SAT solver integrated directly into the Maple environment.
- Tseitin Transformation: An algorithm used by Maple to convert high-level logical expressions into the CNF format required by the solver without causing an exponential blowup in formula size.
- Symmetry Breaking: Adding extra constraints to the logic to prevent the solver from wasting time exploring redundant, mirrored versions of the same solution.
- Boolean Counters: A method used in problems like Maximum Clique to track the count of "true" variables (e.g., "at least $k$ vertices are in the clique") using logical gates.
Benchmarks and Applications
The authors evaluated this approach using several famous benchmarks and puzzles:
- The "World's Hardest" Sudoku: A puzzle designed by Arto Inkala to challenge human and algorithmic solvers alike.
- DIMACS Implementation Challenge: A standard set of 80 benchmarks for the Maximum Clique problem.
- Euler’s Graeco-Latin Square Conjecture: A historical mathematical problem regarding orthogonal squares.
- The 15-Puzzle: A classic sliding-tile puzzle used to test dynamic state encoding.
Results: Puzzles and Mathematical Conjectures
The results highlight the "SAT Beatdown"—a phenomenon where a simple translation to SAT outperforms clever, hand-crafted algorithms. For many mathematicians, the "aha moment" is realizing they only need to be experts in defining their problem's constraints, not in search heuristics.
Key performance metrics include:
- $n$-Queens: The 32-queens problem was solved in under one second.
- Sudoku: The "world's hardest" Sudoku was solved in just 0.25 seconds.
- Graeco-Latin Squares: The system automatically disproved Euler's conjecture for order 10 (a problem that famously made the front page of the New York Times in 1959) in approximately 23 hours.
- Maximum Clique: The SAT-based approach solved 18 out of 80 DIMACS benchmarks in under 3 minutes, significantly outperforming Maple’s dedicated backtracking algorithm. In one instance, SAT took 8 seconds to solve a problem that required 57 minutes for the standard algorithm.
Discussion and Future Directions
While highly effective for static puzzles, the approach faces challenges with "state-changing" puzzles like the 15-puzzle, which require encoding time-steps ($t, t+1$), leading to very large logic formulas. Additionally, declarative programming lacks the "fine-grained control" sometimes necessary for specific optimizations.
Future work may involve extending these techniques to Satisfiability Modulo Theories (SMT). This would allow for the natural expression of problems involving real numbers or more complex data structures, further expanding the reach of automated problem solving in mathematics.
Summary updated