Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 37 Β· Applications in CS

DPLL and SAT Solvers

Learn CNF, the satisfiability problem and the DPLL algorithm with unit propagation and pure literals, then solve puzzles with a SAT solver you write in Python.

The Boolean satisfiability problem (SAT) asks: given a propositional formula, is there an assignment of truth values that makes it true? SAT was the first problem proved NP-complete (Cook, 1971), and yet modern SAT solvers routinely solve industrial instances with millions of variables. They check hardware designs, plan schedules, verify software and break puzzles. The core of nearly all of them descends from the 1962 DPLL algorithm (Davis, Putnam, Logemann, Loveland), which you will implement in this lesson.

Validity and satisfiability are two faces of one question, as you saw with tableaux: Ο† is valid exactly when ¬φ is unsatisfiable.

Conjunctive normal form

Solvers take input in CNF: an AND of clauses, where each clause is an OR of literals (a variable or its negation). Every formula can be converted to CNF, and a standard encoding (Tseitin) does it with only linear growth by adding fresh variables. The usual file format, DIMACS, writes variables as positive integers and negation as a minus sign: (p ∨ ¬q) ∧ (q ∨ r) is [[1, -2], [2, 3]].

A clause is satisfied if some literal in it is true; the CNF is satisfied if all clauses are. An empty clause is false, so a formula containing one is unsatisfiable. An empty formula (no clauses) is trivially true.

Python Brute-force SAT on CNF

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 DPLL algorithm

DPLL is a backtracking search over assignments, with two powerful inference rules that prune the tree:

  1. Unit propagation: if a clause has only one unassigned literal (and no true literal), that literal must be true. Setting it may create new units, so repeat.
  2. Pure literal elimination: if a variable appears only positively (or only negatively) in the remaining clauses, set it to satisfy those clauses.
  3. Branching: pick an unassigned variable, try it true, and if that fails try false.

Simplifying a formula under a literal l: remove clauses containing l (satisfied) and delete Β¬l from other clauses.

flowchart TB
    S["Simplify with units and pure literals"] --> E{"Empty clause?"}
    E -->|yes| U["UNSAT: backtrack"]
    E -->|no| F{"No clauses left?"}
    F -->|yes| A["SAT: found a model"]
    F -->|no| B["Pick variable, try true, then false"]
    B --> S

DPLL alternates simplification and branching.

Python A DPLL solver

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 solver above returns a partial model: variables not mentioned can take either value. A real solver also reports a full assignment, and verifies it, as the next example does.

Encoding a puzzle: graph coloring

SAT solvers shine when you can encode a problem as clauses. To color a graph with k colors, use variable x(v, c) meaning "vertex v gets color c" and add:

  • At least one color per vertex: x(v,1) ∨ … ∨ x(v,k).
  • At most one color per vertex: Β¬x(v,c) ∨ Β¬x(v,d) for each pair c < d (optional if any one color suffices).
  • Neighbors differ: Β¬x(u,c) ∨ Β¬x(v,c) for each edge (u,v) and color c.
Python 3-coloring a graph with SAT, checked against sympy

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.

Beyond DPLL: CDCL

Modern solvers use conflict-driven clause learning (CDCL). When a branch fails, the solver analyzes the conflict, derives a new clause that captures the cause, adds it to the formula and jumps back several levels instead of one. Add smart variable-ordering heuristics (VSIDS), watched literals for fast propagation and periodic restarts, and instances of millions of clauses become routine. Extensions include SMT solvers (SAT plus theories such as integers and arrays) used in program verification, and MaxSAT for optimization.

Special cases that are easy

General SAT is NP-complete, but important fragments are fast:

  • 2-SAT (clauses of at most 2 literals) is solvable in linear time via strongly connected components of the implication graph.
  • Horn-SAT (at most one positive literal per clause) is solved by unit propagation alone, which is why logic programming (Prolog) is efficient.
  • 3-SAT is already NP-complete.
Python Horn clauses: unit propagation is enough

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.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What does CNF stand for and look like?

    Conjunctive normal form is a conjunction of disjunctive clauses.
  2. 2. What does unit propagation do?

    If a clause has one unassigned literal left it must be true, which then simplifies other clauses.
  3. 3. A CNF containing an empty clause is

    An empty clause is a disjunction of nothing, which is false, so the whole conjunction is false.
  4. 4. Which fragment is solvable by unit propagation alone?

    Horn formulas can be decided by forward chaining, which is unit propagation.

Summary

  • SAT asks whether a formula has a satisfying assignment; it is NP-complete but practically solvable.
  • DPLL combines unit propagation, pure-literal elimination and backtracking on CNF.
  • Problems like coloring, scheduling and verification are solved by encoding them into clauses.
  • CDCL, learned clauses and heuristics scale this to industrial sizes; 2-SAT and Horn-SAT are polynomial.

Next: Boolean Algebra and Logic Circuits