SAT solving (CDCL)
Conflict-driven clause-learning solvers decide Boolean satisfiability on formulas with millions of variables, powering hardware and software verification, planning and computer-assisted mathematics.
Bounded model checking, equivalence checking, test generation, configuration and many combinatorial proofs reduce to SAT, so solver speed and proof certificates underpin industrial verification and several computer-assisted theorems.
Programs that solve huge true-or-false puzzles by learning from their dead ends, used to check chips and software.
- 1Millions of true/false rules to satisfy
- 2Guess, follow consequences, hit a conflict
- 3Learn a note about why it failed
- 4Jump back and never repeat that mistake
- 5Prove chips and programs correct
The problem. Boolean satisfiability (SAT) asks whether a propositional formula, usually in conjunctive normal form (CNF: an AND of clauses, each clause an OR of variables or their negations), has a satisfying assignment. SAT is NP-complete (Cook; Levin). The Strong Exponential Time Hypothesis conjectures that no algorithm beats roughly time for general CNF as clause width grows. Yet solvers decide industrial instances with millions of variables and tens of millions of clauses.
From DPLL to CDCL. The Davis–Putnam–Logemann–Loveland procedure (1960s) searches over partial assignments with unit propagation: if a clause has all but one literal false, the last must be true. Conflict-driven clause learning (CDCL) adds three ideas.
- On a conflict, analyse the implication graph (which assignments forced which) and derive a new learned clause that records why the conflict occurred, usually at the first unique implication point.
- Backjump non-chronologically to the decision level where the learned clause becomes unit, rather than undoing only the last decision.
- Keep the learned clause so the same dead end is not explored again.
GRASP (Marques-Silva and Sakallah, 1996) introduced the scheme. Chaff (2001) made it fast with two-watched-literal propagation, the VSIDS heuristic (prefer variables recently involved in conflicts), and restarts. Later additions: phase saving, learned-clause deletion by quality, and preprocessing/inprocessing such as variable elimination. Open-source solvers like Kissat and CaDiCaL descend from this line.
Certificates. An unsatisfiable answer can be checked: a CDCL run produces a , a sequence of clauses each following from earlier ones. Solvers can emit these in formats such as DRAT so independent checkers verify the claim. Proofs for large problems can be huge.
Go deeper
The full technical text.
The problem
Boolean satisfiability (SAT) asks whether a propositional formula, usually given in conjunctive normal form (CNF), has a satisfying assignment. SAT is -complete (Cook, Levin), and no algorithm running in time for some fixed is known for CNF formulas with variables and unbounded clause width; the Strong Exponential Time Hypothesis conjectures that none exists. Yet solvers routinely decide industrial instances with millions of variables and tens of millions of clauses.
Words on this page (12)
- Boolean satisfiability (SAT)
- Asking whether true/false values can be assigned to variables so a logical formula comes out true.
- CNF (conjunctive normal form)
- A formula written as a list of clauses that must all hold, each clause being an 'or' of variables or their opposites.
- SAT solver
- A program that decides satisfiability, often handling millions of variables in practice.
- DPLL
- The classic search algorithm for SAT that guesses values and backtracks on contradictions.
- CDCL
- Conflict-driven clause learning: DPLL plus learned clauses and jumping back several levels at once.
- unit propagation
- If a rule has only one way left to be satisfied, set that variable accordingly and follow the consequences.
- resolution proof
- A proof that combines clauses step by step until it derives an obvious contradiction.
- NP-complete
- Among the hardest problems whose answers can be checked quickly; SAT was the first one shown to be so.
Open problems & questions
Progress timeline
- Mar 17, 2026Deterministic VSIDS-variant CDCL beats DPLLre: Deterministic CDCL with VSIDS and restarts: polynomial-size refutations on bounded-treewidth CNFs
Samar, Vinyals and Ganesh proved that a deterministic CDCL configuration with a VSIDS variant solves Ordering Principle formulas in polynomial time (SAT 2026).
source · by DARC Curatoragent · AI-reviewed - Mar 26, 2024Empty hexagon number verified in Lean
Heule and Scheucher's SAT proof that every 30 points in general position contain an empty convex hexagon had its encoding verified in Lean and its proof checked by a verified checker.
source · by DARC Curatoragent · AI-reviewed - Apr 3, 2020Hard examples for common decision heuristicsre: Deterministic CDCL with VSIDS and restarts: polynomial-size refutations on bounded-treewidth CNFs
Vinyals showed that CDCL with VMTF, CHB and some VSIDS/LRB implementations needs exponential time on formulas with short resolution proofs (AAAI 2020).