SAT Solvers Explained — DPLL, CDCL and Practical Solving

In this tutorial, you'll learn about SAT Solvers Explained. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

SAT solvers determine whether a propositional formula in conjunctive normal form has a satisfying assignment, forming the computational engine behind bounded Model Checking and automated test generation.

Learning Path

flowchart LR
  A["Propositional Logic"] --> B["SAT Solvers
DPLL & CDCL"]
  B --> C["SAT & SMT Solving"]
  B --> D["Bounded Model Checking"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Propositional logic, CNF conversion, and basic algorithm analysis.

What Is a SAT Solver?

SAT solvers take a boolean formula in conjunctive normal form and answer whether an assignment of true/false to variables satisfies all clauses. The problem is NP-complete, but modern solvers handle industrial instances with millions of clauses through conflict-driven learning and efficient data structures.

The breakthrough came in the early 2000s with the CDCL algorithm, which learns new clauses from conflicts and uses restarts to escape local regions of the search space.

Step-by-Step: The DPLL Algorithm

Step 1: Unit Propagation

When a clause has exactly one unassigned literal, that literal must be true to satisfy the clause.

def unit_propagate(clauses, assignment):
    changed = True
    while changed:
        changed = False
        for clause in clauses:
            unassigned = []
            false_lits = 0
            for lit in clause:
                var = abs(lit)
                if var not in assignment:
                    unassigned.append(lit)
                elif assignment[var] != (lit > 0):
                    false_lits += 1
            if false_lits == len(clause):
                return clauses, assignment, False
            if len(unassigned) == 1:
                val = unassigned[0] > 0
                assignment[abs(unassigned[0])] = val
                changed = True
    return clauses, assignment, True

clauses = [[1, 2], [-1], [2, -3]]
assign = {}
result, assign, ok = unit_propagate(clauses, assign)
print(f"Assignment: {assign}, Consistent: {ok}")

Expected output:

Assignment: {1: False, 2: True}, Consistent: True

Step 2: Pure Literal Elimination

If a variable appears only positively or only negatively across all clauses, assign it to satisfy those clauses.

def pure_literal(clauses):
    pos = set()
    neg = set()
    for c in clauses:
        for l in c:
            if l > 0:
                pos.add(l)
            else:
                neg.add(abs(l))
    pure_pos = pos - neg
    pure_neg = neg - pos
    assign = {}
    for v in pure_pos:
        assign[v] = True
    for v in pure_neg:
        assign[v] = False
    return assign

clauses = [[1, 2], [-2, 3], [1, -3], [4]]
result = pure_literal(clauses)
print(f"Pure literals: {result}")

Expected output:

Pure literals: {1: True, 4: True}

Step 3: Complete DPLL Solver

def dpll(clauses, assignment):
    clauses, assignment, ok = unit_propagate(clauses, assignment)
    if not ok:
        return None
    pure_assign = pure_literal(clauses)
    assignment.update(pure_assign)
    unassigned = set()
    for c in clauses:
        for l in c:
            if abs(l) not in assignment:
                unassigned.add(abs(l))
    if not unassigned:
        for c in clauses:
            sat = False
            for l in c:
                v = assignment[abs(l)]
                if (l > 0) == v:
                    sat = True
                    break
            if not sat:
                return None
        return assignment
    var = unassigned.pop()
    for val in [True, False]:
        new_assign = assignment.copy()
        new_assign[var] = val
        result = dpll(clauses, new_assign)
        if result is not None:
            return result
    return None

clauses = [[1, 2, 3], [-1, 2], [-2, 3], [-3]]
result = dpll(clauses, {})
print(f"SAT result: {result}")

Expected output:

SAT result: {1: False, 3: False, 2: True}

Conflict-Driven Clause Learning

CDCL extends DPLL with three critical features: clause learning from conflicts, non-chronological Backtracking, and restarts.

Clause Learning

When a conflict occurs, the solver analyzes the implication graph to derive a conflict clause that prevents the same conflict from recurring.

def learn_conflict_clause(implication_graph, conflict_var):
    clause = set()
    for node in implication_graph.get(conflict_var, []):
        clause.add(-node)
    return list(clause)

graph = {3: [-1, -2], 4: [3], 5: [3]}
conflict_clause = learn_conflict_clause(graph, 5)
print(f"Learned clause: {conflict_clause}")

Expected output:

Learned clause: [1, 2]

VSIDS Branching Heuristic

VSIDS (Variable State Independent Decaying Sum) assigns an activity score to each variable. Variables involved in recent conflicts get higher scores and are branched on first.

class VSIDS:
    def __init__(self, variables):
        self.scores = {v: 0 for v in variables}
        self.decay = 0.95

    def bump(self, var):
        self.scores[var] += 1.0

    def decay_all(self):
        for v in self.scores:
            self.scores[v] *= self.decay

    def select(self):
        return max(self.scores, key=self.scores.get)

vsids = VSIDS([1, 2, 3, 4])
vsids.bump(2)
vsids.bump(3)
vsids.bump(3)
print(f"Next branch: {vsids.select()}")

Expected output:

Next branch: 3

Using MiniSat and CryptoMiniSat

MiniSat is the reference CDCL implementation. CryptoMiniSat extends it with XOR clause handling and Gaussian elimination for cryptographic problems.

# Install MiniSat
sudo apt-get install minisat

# Solve a CNF file
minisat formula.cnf

The CNF format:

p cnf 3 4
1 -2 0
2 -3 0
-1 3 0
-1 -2 -3 0

Common Errors

1. Not Converting to CNF Properly

SAT solvers require CNF input. Non-CNF formulas need Tseitin transformation, which introduces auxiliary variables but preserves satisfiability.

2. Ignoring Unit Propagation Order

The order of unit propagation affects performance dramatically. Using a two-watched-literals scheme (as in MiniSat) provides constant-time propagation.

3. Over-relying on Random Restarts

Restarts help escape local plateaus but too many restarts waste progress. Modern solvers use dynamic restart policies based on conflict counts.

4. Confusing SAT and SMT

SAT handles only propositional logic. SMT extends SAT with theories. Use SAT when your problem is purely boolean; use SMT for arithmetic, arrays, or bit vectors.

5. Not Using Incremental Solving

For multiple related queries, reuse the solver state with assumptions instead of solving from scratch each time.

Practice Questions

Q1: What is the difference between DPLL and CDCL?

DPLL is the basic Backtracking search algorithm. CDCL extends it with clause learning from conflicts, non-chronological Backtracking, and restart heuristics.

Q2: What is a conflict clause?

A clause derived from the implication graph during a conflict that prevents the solver from exploring the same conflicting assignment again.

Q3: How does the two-watched-literals scheme work?

Each clause tracks two unassigned literals. Unit propagation only triggers when one of the two watched literals becomes false, reducing clause inspection overhead.

Q4: What is a restart in SAT solving?

The solver discards the current partial assignment and starts from scratch while keeping learned clauses accumulated from previous runs.

Q5: Why do SAT solvers use CNF?

The DPLL and CDCL algorithms operate on clauses. CNF is a universal normal form that preserves satisfiability and enables efficient unit propagation.

Challenge

Implement a Tseitin transformation that converts an arbitrary boolean formula into CNF with auxiliary variables. Test it on (a AND b) OR (c AND NOT d) and verify that the resulting CNF is equisatisfiable using a simple SAT solver.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.