Effective Problem Solving Using SAT Solvers

Curtis Bright, Jürgen Gerhard, Ilias S. Kotsireas, Vijay Ganesh

TL;DR

This paper demonstrates that many complex combinatorial problems—from Sudoku and the "Einstein Riddle" to disproving centuries-old mathematical conjectures—can be solved more efficiently by translating them into Boolean logic than by writing custom search algorithms. By leveraging the built-in SAT solver in the Maple computer algebra system, researchers can use a "declarative" approach: simply describe the rules of the game, and let the machine find the solution.

What Problem Does This Paper Address?

In computer science and mathematics, we often encounter NP-hard problems like the "Maximum Clique" problem or complex puzzles. Traditionally, solving these requires writing specialized, "imperative" algorithms—step-by-step instructions on how to search for a solution. This is time-consuming and often results in code that is less efficient than general-purpose tools.

The authors address 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. This paper showcases how modern tools (specifically Maple) bridge this gap, allowing users to express problems in natural logic and solve them automatically.

Methods

The core methodology is Declarative Programming via SAT encoding. Instead of telling the computer how to search, the authors define what a valid solution looks like using Boolean variables and logical operators (AND, OR, NOT, Implication).

Key technical components include:

  • MapleSAT: A state-of-the-art SAT solver integrated directly into the Maple environment.
  • Tseitin Transformation: A clever algorithm used by Maple to convert high-level logical expressions into the CNF format required by the solver without causing an "exponential blowup" in the size of the formula.
  • 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 the Maximum Clique problem to track the count of "true" variables (e.g., "at least $k$ vertices are in the clique") using logical gates.

Datasets

The authors evaluated their approach using several famous benchmarks and puzzles:

  • The "World's Hardest" Sudoku: A puzzle designed by Arto Inkala.
  • 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.

Key Insights and Ideas

  • The "SAT Beatdown": The authors quote Chris Jefferson, noting the "constant source of annoyance" when a clever, hand-crafted algorithm is outperformed by a simple translation to SAT. This highlights the maturity and raw power of modern SAT solvers.
  • Declarative vs. Imperative: The paper argues that for many mathematicians, the "aha moment" is realizing they don't need to be experts in search heuristics. They only need to be experts in defining their problem's constraints.
  • Symmetry is the Enemy of Speed: In problems like Graeco-Latin squares, the search space is astronomical. By "breaking" symmetries (e.g., forcing the first row to be in ascending order), the authors show how to prune billions of useless search paths.
  • Dynamic Problems are Tricky: While static puzzles (Sudoku) are easy for SAT, "state-changing" puzzles like the 15-puzzle require encoding time-steps ($t, t+1$), which makes the logic much more complex.

Key Results

  • $n$-Queens: Solved the 32-queens problem in under one second.
  • Sudoku: Solved the "world's hardest" Sudoku in just 0.25 seconds.
  • Graeco-Latin Squares: Automatically disproved Euler's conjecture for order 10 (a problem that famously made the front page of the New York Times in 1959) in about 23 hours.
  • Maximum Clique: The SAT-based approach solved 18 out of 80 DIMACS benchmarks in under 3 minutes, outperforming Maple’s dedicated backtracking algorithm. In one specific case, SAT took 8 seconds to solve a problem that took the standard algorithm 57 minutes.

Limitations and Future Work

  • Encoding Complexity: For problems where the state changes over time (like the 15-puzzle), the SAT encoding becomes very large and less competitive with dedicated solvers.
  • Lack of Control: The authors acknowledge that declarative programming lacks "fine-grained control," which can be a disadvantage if a problem requires a very specific optimization that the general SAT solver doesn't prioritize.
  • Natural Expression: Not all problems are easily expressed as Boolean logic. Future work could involve extending these techniques to Satisfiability Modulo Theories (SMT) to handle real numbers or more complex data structures more naturally.

Summary updated

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.
BibTeX
@inproceedings{bright2019effective,
  author = {Curtis Bright and Jürgen Gerhard and Ilias S. Kotsireas and Vijay Ganesh},
  title = {{Effective Problem Solving Using SAT Solvers}},
  booktitle = {MC},
  year = {2019},
  url = {https://openreview.net/forum?id=OgWXuKA7Oq_a},
}

Loading related content...

Figure