A SAT-solving mechanism that analyzes conflicts encountered during search to derive and record new clauses (learned clauses) which prevent the same conflict pattern on subsequent search branches, typically combined with non-chronological backtracking.

Principle

When a conflict is detected, construct an implication (dependency) graph from recent assignments, identify a cut or Unique Implication Point (UIP), derive a clause that blocks the conflict (a logical consequence of the clause set), add it to the database, and backjump to an earlier decision level.

Demonstration

During a search, unit propagation leads to a clause conflict. Build the implication graph of assigned literals, find the first UIP, resolve clauses along the cut to produce a learned clause ¬a ∨ ¬b that prevents repeating the same conflicting combination, then backjump to the decision level where that clause becomes unit.

Misapplication

Recording clauses that are not logical consequences (incorrect derivation), learning overly specific or trivially subsumed clauses without deletion policy, or treating learned clauses as mere heuristics without ensuring soundness undermines solver correctness or performance.

Consequence

CDCL prevents repeated exploration of the same conflict patterns, enables powerful non-chronological backtracking, and is a primary reason modern SAT solvers achieve dramatic practical speedups on many classes of problems.

Reversal

Pure DPLL without clause learning repeatedly rediscovers the same conflicts and is typically much less efficient; local-search methods also avoid learning and follow a different performance profile.

Boundary

Applies to clause-based propositional solving and to extensions with theory reasoning when combined with careful integration; requires sound conflict analysis and management of the learned-clause database (garbage collection, subsumption) to remain effective.

Semantic Tension

CDCL balances between learning too many clauses (memory/time blowup) and learning too few (ineffective pruning); it sits between pure resolution proof systems and heuristic search, blending deduction with search control.

Synthesis

Conflict-driven clause learning is the process of analyzing conflicts via implication graphs to extract sound learned clauses and performing backjumping, producing a dynamic clause database that prunes future search and powers modern SAT solving.