Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 46 · Logic and Knowledge Representation

SAT Solving and DPLL

Learn the satisfiability problem and write a DPLL solver with unit propagation in Python, encode n-queens as SAT, see the 3-SAT phase transition, and read an overview of CDCL.

The previous lessons asked whether a knowledge base entails a sentence. There is a closely related question that turns out to be even more useful: is there any model that makes this set of clauses true? That is the Boolean satisfiability problem, SAT. If you can answer it, you can also answer entailment, because KB ⊨ α exactly when KB ∧ ¬α is unsatisfiable.

SAT was the first problem proved to be NP-complete (Cook, 1971), so nobody expects a fast algorithm for every instance. And yet modern SAT solvers routinely handle formulas with millions of variables and clauses, from chip verification to software package installation. The trick is clever search, and the starting point of that search is a 1960s algorithm called DPLL. In this lesson you will write it, use it to solve a puzzle by encoding it as logic, and see why some random formulas are far harder than others.

The SAT problem

The input of SAT is a formula in conjunctive normal form: a set of clauses, each a set of literals. The output is either a satisfying assignment, one value for every variable making every clause true, or the answer unsatisfiable. We use the common numeric format from the DIMACS files that all real solvers read: variables are the integers 1, 2, 3, ..., a positive number is the variable, and a negative number is its negation. So [1, -2, 3] means x1 ∨ ¬x2 ∨ x3.

Brute force tries all 2^n assignments. DPLL is a smarter backtracking search, and its power comes from two ideas that cut the search tree.

  • Unit propagation. If a clause has only one literal left, that literal is forced: set it true. Setting it true may make other clauses shorter, or satisfied, and produce more forced literals. Often one decision triggers a long chain of consequences, and no guessing is needed.
  • Pure literal elimination. If a variable occurs with only one sign in the whole formula (always positive, or always negative), setting it to make those occurrences true can never hurt.

When neither rule applies, the algorithm branches: pick a variable, try it true; if that leads to a conflict (an empty clause), backtrack and try it false.

graph TD
    S["Formula"] --> U["Unit propagation<br/>(repeat while unit clauses exist)"]
    U --> C{"Empty clause?"}
    C -- "yes" --> F["Fail: backtrack"]
    C -- "no" --> D{"No clauses left?"}
    D -- "yes" --> OK["SAT: success"]
    D -- "no" --> B["Pick a literal and branch:<br/>try it, then its negation"]
    B --> S

DPLL in one picture: propagate, check for conflict or success, otherwise branch and recurse on the simplified formulas.

A traced run

The program below is DPLL in its simplest form. To make it a learning tool, it can print what it does. Our five variables are a, b, c, d, e. The function simplify applies an assumption: it removes every clause that the literal satisfies, and deletes the opposite literal from the clauses that remain.

Python DPLL with a visible trace

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the trace. The solver decides ¬a, then b. That choice makes the clause (¬b ∨ c) into the unit (c), and the chain c, d, e follows with no further guessing, but (¬e) is also a unit clause and the formula collapses to an empty clause. That is a conflict. The solver backtracks one level, tries ¬b instead, and the same chain of forced steps now ends with every clause satisfied. One wrong guess cost almost nothing, because the propagation found the contradiction immediately.

Encoding problems as SAT

The real power of SAT is that many problems can be translated into it. The recipe:

  1. Choose Boolean variables that describe a solution. For n-queens: Q(r, c) means "there is a queen in row r, column c".
  2. Write the constraints as clauses. "Every row has a queen" is one long clause per row. "No two queens attack each other" becomes many two-literal clauses ¬Q(r1,c1) ∨ ¬Q(r2,c2), one for each pair of squares in the same row, column or diagonal.
  3. Run the solver and decode the satisfying assignment back into the answer.
graph LR
    P["Problem<br/>(8 queens)"] --> E["Encode as<br/>clauses"]
    E --> S["SAT solver<br/>(DPLL)"]
    S --> M["Satisfying<br/>assignment"]
    M --> D["Decode into<br/>a board"]

The standard SAT workflow. The same solver serves every problem you can encode.

The next program contains a full DPLL solver (with pure literal elimination and statistics), builds the queens encoding, solves it and checks the answer independently. It also shows a famous hard family: the pigeonhole principle. Putting p pigeons in p−1 holes (one per hole at most) is impossible, but proving it by DPLL takes enormous search because the clauses give little to propagate until many decisions are made.

Python n-queens and the pigeonhole principle as SAT

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Queens are easy for DPLL: the 8-queens instance has 64 variables and 736 clauses, and needs only a few dozen calls, because every placed queen makes unit propagation eliminate many squares. The pigeonhole table is the opposite lesson. The answer is obvious to a human, but the number of DPLL calls grows by a factor of about 8 with every extra pigeon: 3, 14, 90, 570, 4,032 and 32,312. There are formulas on which this kind of search (and resolution itself) provably needs exponential time.

The phase transition in random 3-SAT

How hard is a typical SAT instance? It depends on the ratio of clauses to variables. Generate random 3-SAT formulas: each clause picks three distinct variables and negates each at random.

  • With few clauses per variable (a ratio below about 3), the formula is underconstrained: almost always satisfiable, and easy.
  • With many (a ratio above about 6), it is overconstrained: almost always unsatisfiable, and contradictions are found quickly.
  • Near a ratio of 4.27 the probability of being satisfiable drops sharply from near 1 to near 0, like a physical phase transition. Instances right at that edge are the hardest.

The experiment builds 16 random formulas with 40 variables for each ratio and reports how many are satisfiable and the average number of DPLL calls. The seeds are fixed, so the table is reproducible.

Python Watching the 3-SAT phase transition

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table shows the transition. All 16 formulas are satisfiable up to a ratio of 4.0, only 7 of 16 at 4.26, 5 of 16 at 4.5, and none from 5.0 on. The average work is highest around the critical ratio (86.1 calls at 4.26 and 95.8 at 4.5) and lower on both sides: 26.9 calls at ratio 3.0 and 49.6 at ratio 6.0. With only 40 variables and 16 formulas per row the picture is noisy and the peak is modest; with a few hundred variables the same shape becomes dramatic, with the hardest instances needing millions of steps.

From DPLL to modern solvers: CDCL

DPLL forgets everything when it backtracks: it can run into the same contradiction in a thousand different corners of the search tree. Modern solvers (MiniSat, Glucose, CaDiCaL, Kissat) use conflict-driven clause learning (CDCL), which turns each conflict into knowledge.

TEXT
loop:
    propagate all unit clauses                 # as in DPLL, but with watched literals (fast)
    if a conflict occurs:
        if at decision level 0:  return UNSAT
        analyze the conflict -> learn a new clause that rules out this whole situation
        backjump to the level where the new clause becomes a unit (not just one step back)
        add the learned clause to the formula
    else if all variables are assigned:  return SAT
    else:
        pick a variable by a heuristic (VSIDS: favor variables seen in recent conflicts)
        assign it a value and go one decision level deeper
    occasionally: restart the search, keeping the learned clauses

This sketch is read-only, but each ingredient is concrete.

  • Clause learning. When a conflict arises, the solver traces back through the implication graph (which decision led to which forced literal) and derives a new clause, a resolvent, that records "this combination of decisions is impossible". It never repeats that mistake.
  • Non-chronological backjumping jumps straight back to the decision that actually mattered, skipping irrelevant ones.
  • Watched literals. Each clause watches two of its literals, so propagation does not touch most clauses on most assignments.
  • VSIDS (variable state independent decaying sum) and restarts keep the search focused on the hard core of the problem.

Together, these made SAT practical at industrial scale. SAT solvers check microprocessor designs, find bugs in software, schedule exams, solve dependency problems in package managers and are used to prove mathematical results. The pysat and z3 libraries give Python programmers access to such solvers, but they are not available in the browser sandbox, so everything on this page uses our own small DPLL.

Not every SAT variant is hard. 2-SAT, where every clause has at most two literals, can be solved in linear time. Horn-SAT (the Horn clauses of the previous lesson) is also linear. Hardness begins with three literals per clause.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What does unit propagation do in DPLL?

    A clause with one literal left can only be satisfied by making that literal true, so the literal is forced. Simplifying may create further unit clauses.
  2. 2. How do you use a SAT solver to decide whether KB entails α?

    KB entails α exactly when there is no model of the KB in which α is false, that is when KB ∧ ¬α is unsatisfiable.
  3. 3. In random 3-SAT, where are the hardest instances found?

    At the satisfiability threshold, formulas are neither clearly satisfiable nor clearly contradictory, and DPLL does the most work.
  4. 4. What is the main idea that CDCL adds to DPLL?

    CDCL analyzes each conflict, stores a clause that prevents it from happening again, and jumps back to the relevant decision.
  5. 5. Why does DPLL do so badly on the pigeonhole formulas?

    The formulas are small but have no short refutation for this kind of search, so the number of calls multiplies with every added pigeon.

Summary

  • SAT asks whether a CNF formula has a satisfying assignment; entailment reduces to SAT because KB ⊨ α iff KB ∧ ¬α is unsatisfiable.
  • DPLL is backtracking search with unit propagation and pure-literal elimination; one decision often forces a long chain of consequences.
  • Problems are solved by encoding: choose Boolean variables, write constraints as clauses, solve, decode (n-queens is a small example).
  • Some formulas, such as pigeonhole, make DPLL explode, and random 3-SAT is hardest near a clause-to-variable ratio of about 4.27.
  • Modern CDCL solvers learn clauses from conflicts, backjump, use watched literals, VSIDS and restarts.
  • 2-SAT and Horn-SAT are easy; general SAT is NP-complete.

Next: First-Order Logic and Knowledge Bases.