Mathematics matters in SAT solvers because many planning, verification and configuration problems can be asked as one precise question: is there an assignment of true and false values that makes every required clause true? The statement sounds simple. Yet n Boolean variables allow 2^n complete assignments, so blind enumeration becomes impossible quickly. Modern solvers succeed by deduction, carefully chosen guesses and learning from contradictions.
For students asking why mathematics is important in AI and computing, Boolean satisfiability is a remarkable bridge. Logic supplies the language, graphs explain implications, algorithms organise search, probability can guide choices, and proof checking provides trust. A solver is not magical intelligence. It is disciplined reasoning at extraordinary speed.
Quick Reading Routes
- Students can begin with variables, literals, clauses and the small timetable example.
- Parents and teachers can use the light-switch and seating-rule activities to make constraints tangible.
- Computing learners can focus on CNF, unit propagation, implication graphs, learned clauses and backjumping.
- Practitioners can review modelling, incremental solving, proof certificates, performance limits and responsible claims.
What SAT Asks
SAT stands for Boolean satisfiability. Given a formula over variables that can be true or false, determine whether at least one assignment makes the formula true.
Variables and literals
Let A mean “workshop A is scheduled in the morning.” The variable A can be true or false. A literal is either A or its negation ¬A.
Clauses
A clause is an OR of literals. Clause (A∨B∨¬C) is true when at least one listed literal is true.
Conjunction
Many solvers receive formulas in conjunctive normal form, or CNF: an AND of clauses. Every clause must be satisfied. For example, (A∨B)∧(¬A∨C) requires both clauses to be true.
SAT and UNSAT
If a satisfying assignment exists, the instance is SAT and the solver may return a model. If none exists, it is UNSAT. A trustworthy solver should not confuse “I have not found a model yet” with a proof that no model exists.
A Small Example
Consider three variables:
- A: Ana joins the robotics group.
- B: Ben joins the robotics group.
- C: the group uses the advanced kit.
Rules:
1. At least one of Ana or Ben joins: (A∨B). 2. If Ana joins, use the advanced kit: (¬A∨C). 3. If Ben joins, do not use the advanced kit: (¬B∨¬C). 4. Ana and Ben cannot both join: (¬A∨¬B).
Assignment A=true, B=false, C=true satisfies all four clauses. The formula is SAT.
Translating implication
“If A then C” becomes ¬A∨C. It fails only when A is true and C is false. This equivalence is one of the most useful translation steps in Boolean modelling.
At least one and at most one
At least one of A and B is A∨B. At most one is ¬A∨¬B. Together they express exactly one. For many variables, naive pairwise at-most-one clauses use quadratic space; alternative encodings introduce auxiliary variables.
A model is not always a unique answer
A SAT formula may have many satisfying assignments. If an application needs the best assignment, not merely any one, it may use repeated SAT calls, MaxSAT, pseudo-Boolean optimisation or another optimisation framework.
Why Brute Force Explodes
With n Boolean variables, there are 2^n complete assignments. For n=20, that is 1,048,576. For n=50, it exceeds one quadrillion. At n=100, exhaustive enumeration is beyond ordinary physical feasibility.
Exponential does not mean every instance is hopeless
The worst-case complexity of general SAT is hard, but real formulas often contain structure. Unit clauses force values. Repeated patterns create implications. Conflicts can teach reusable facts. Solvers exploit this structure instead of visiting every leaf.
Input size and encoding
A compact formula can represent a vast search space. Conversely, a poor encoding can inflate clause count or hide useful propagation. Modelling is part of performance.
SAT is NP-complete
The Cook–Levin theorem established SAT as the first NP-complete problem. Informally, solutions can be checked quickly, and every problem in NP can be reduced to SAT with polynomial overhead. This explains both theoretical importance and practical reach; it does not imply every SAT instance takes the same time.
From DPLL to CDCL
The Davis–Putnam–Logemann–Loveland procedure combines decisions with logical propagation and backtracking. Conflict-driven clause learning, or CDCL, extends this family by analysing conflicts, learning new clauses and jumping back to a relevant decision level.
A compact primary description of a modern solver is MiniSat v1.13 — A SAT Solver with Conflict-Clause Minimization. It explains a small Chaff-like solver using watched literals, conflict learning and clause minimisation.
The main loop
1. Propagate forced literals. 2. If a conflict appears, analyse it. 3. Learn a clause that blocks the same conflicting combination. 4. Backjump to an earlier decision level. 5. Otherwise choose a new decision literal. 6. Continue until a model is complete or conflict at level zero proves UNSAT.
Search plus proof
Decisions explore possibilities. Propagation performs deduction. Learned clauses record consequences derived from existing clauses. Over time, the solver builds a proof-oriented memory of why regions of the search space cannot work.
Unit Propagation
A unit clause has one unassigned literal and all other literals false. To satisfy it, the remaining literal must be true.
Suppose clauses are (A∨B), (¬A∨C) and (¬C). Clause (¬C) forces C=false. Then (¬A∨C) becomes (¬A∨false), forcing A=false. Then (A∨B) forces B=true. No guess was required.
Cascades
One forced assignment can shorten several clauses and create more unit clauses. This cascade is Boolean constraint propagation, a central source of solver power.
Conflict
If propagation requires both X and ¬X, or makes every literal in a clause false, the current partial assignment is inconsistent.
Fixed point
Propagation continues until there are no unit clauses or a conflict occurs. The result is a fixed point under the propagation rule, not necessarily a complete solution.
Watched Literals
Naively scanning every clause after every assignment is expensive. The two-watched-literal technique associates each non-unit clause with two watched literals.
When one watched literal becomes false, the solver tries to move the watch to another literal that is not false. If it cannot and the other watch is unassigned, the clause is unit. If both are false, the clause conflicts.
Why two watches help
A clause needs attention mainly when a watched literal becomes false. Assignments that make unwatched literals false require no immediate scan of that clause.
Invariant
The watches are maintained so that a clause with two non-false watched literals cannot yet be unit or conflicting. The exact implementation may allow certain lazy states, but correctness relies on preserving the propagation meaning.
Amortised thinking
A watch can move only through clause literals as they become unsuitable at a decision branch. The technique reduces repeated full scans and is a fine example of data structure and logic working together.
Decision Levels
Each guessed literal starts a new decision level. Literals forced by propagation inherit the current level and record a reason clause.
A decision-level example
At level 1, decide A=true. Propagation forces C=true. At level 2, decide D=false. Further propagation forces E=true and then conflicts.
The implication graph records edges from assignments that made a reason clause unit to the literal it forced. Decision nodes have no reason clause inside the formula; they are branch choices.
Chronological backtracking
A basic solver might undo level 2 and try D=true. If the conflict actually depends on A and another earlier fact, this can explore irrelevant branches.
Non-chronological backjumping
Conflict analysis can identify the decision levels involved and jump directly to the highest level needed by the learned clause. Work unrelated to the conflict is not reconsidered one level at a time.
Implication Graphs
An implication graph is a directed graph for the current trail. Nodes are assigned literals. Edges explain which earlier assignments caused a propagation.
Suppose clause (¬A∨¬B∨C) forces C because A and B are true. Draw edges A→C and B→C labelled by that clause. If later clause (¬C∨¬D) conflicts because C and D are true, the graph shows paths from decisions to the contradiction.
Conflict node
The conflict can be represented as a special node reached from literals that falsified the conflicting clause.
Cut interpretation
Conflict analysis chooses a cut separating earlier decisions from the conflict. Literals crossing the cut form a learned clause. The clause states that this combination cannot all occur again.
First UIP
Many CDCL solvers learn at the first unique implication point: a node at the current decision level through which all paths from that level’s decision to the conflict pass. This often yields a compact, effective clause.
A Worked Conflict
Consider clauses:
1. (¬A∨B) 2. (¬A∨C) 3. (¬B∨¬C∨D) 4. (¬D)
Decide A=true at level 1. Clause 1 forces B=true. Clause 2 forces C=true. Clause 3 then forces D=true. Clause 4 forces D=false immediately, so there is a conflict.
Resolve reasons
The conflict involves D and ¬D. D was forced by ¬B∨¬C∨D, so substitute its reasons: B and C cannot both be true while D is false. B came from A; C came from A. Ultimately the branch A=true is impossible.
Learned clause
The solver can learn (¬A). This unit clause forces A=false at level 0. The entire A=true half of the search space is removed.
Why learning matters
Without learning, a solver might rediscover the same contradiction through different downstream decisions. The learned clause summarises the reason in a form propagation can reuse.
Clause Resolution
Resolution is a sound inference rule. From (X∨P) and (¬X∨Q), infer (P∨Q). Any assignment satisfying both parent clauses satisfies the resolvent.
A resolution example
From (¬A∨B) and (¬B∨C), resolve on B to obtain (¬A∨C). If A is true, C must be true whether or not B is written explicitly.
Conflict analysis as resolution
CDCL repeatedly resolves the conflicting clause with reason clauses for current-level literals until a chosen stopping condition, such as first UIP, is reached.
Soundness
Because learned clauses are derived by sound resolution, adding them does not remove any genuine model. It only makes implicit consequences explicit.
Clause minimisation
Some learned literals may be redundant given other reasons. Removing them can strengthen propagation and save memory, but minimisation itself costs work.
Backjumping and the Asserting Clause
A learned clause usually contains one literal from the current highest decision level. After jumping to the second-highest level represented in the clause, that remaining literal becomes unit and is forced.
Example levels
Suppose learned clause (¬A∨¬F∨G) contains A at level 2, F at level 5 and G=false at level 3. The highest level is 5 and the second-highest is 3. Jump to level 3; ¬F is no longer assigned, while ¬A and G are false, so the clause forces ¬F.
More than undo
Backjumping does not merely reverse a bad guess. It returns with a new constraint that changes future propagation.
Level zero conflict
If propagation conflicts without any decisions, the original formula plus learned consequences is inconsistent. The solver declares UNSAT.
Branching Heuristics
When propagation stops before all variables are assigned, the solver chooses a decision literal.
Activity scores
VSIDS-style heuristics increase scores for variables appearing in recent conflicts and periodically decay scores. The solver focuses on the currently active conflict region.
Phase choice
The solver must also choose true or false. Phase saving reuses a variable’s recent value, which can help resume a promising region after backtracking.
Heuristics do not change correctness
A complete solver can remain correct under many branching orders, but runtime can change by orders of magnitude. Heuristics shape the proof search.
Machine learning claims
Learned branching models can help some distributions, but they need out-of-sample evaluation and fallback behaviour. A benchmark win does not imply universal superiority.
Restarts
A solver may abandon the current decision trail periodically while keeping learned clauses.
Why restart?
A poor early decision can lead to an unproductive region. Learned clauses have changed the formula, so returning to level zero is not starting over. The solver keeps knowledge and explores with a refreshed order.
Schedules
Fixed, geometric, Luby-style or adaptive restart schedules balance local exploration against global redirection.
Too frequent or too rare
Very frequent restarts can prevent deep consequences from emerging. Very rare restarts can trap the solver in a difficult branch. Performance is empirical and instance-dependent.
Analogy limits
Restarts resemble taking a fresh approach to a puzzle while keeping notes. Unlike a human metaphor, the solver’s retained clauses are formally derived and machine-checkable consequences.
Clause Databases Need Deletion
Learning a clause at every conflict can consume memory and slow propagation.
Usefulness metrics
Solvers score learned clauses by activity, size or literal block distance. Short clauses are often valuable because they propagate easily, but some longer clauses capture important structure.
Garbage collection
Low-value clauses can be removed while locked reason clauses and strategically important clauses remain. Deletion changes performance, not logical soundness, because learned clauses were redundant consequences of the original formula.
Balance
Too little deletion bloats memory and watch lists. Too much deletion discards useful lessons and causes repeated conflicts. The policy is an optimisation layer atop a correct inference engine.
Encoding Real Problems
The solver sees variables and clauses, not “timetable” or “circuit.” A modeller translates domain rules into Boolean constraints.
Timetabling
Variable X_{c,t} can mean class c uses slot t. Clauses require each class to choose a slot, prevent two slots for the same class, and block resource clashes.
Package selection
Variable P_v can mean package version v is installed. Dependency “A requires B or C” becomes ¬A∨B∨C. Version conflicts become clauses such as ¬B1∨¬B2. The existing article on package managers, dependency graphs, version ranges and lockfiles explores the surrounding application.
Hardware verification
Encode a circuit implementation and its specification, then ask whether an input makes their outputs differ. SAT means a counterexample exists. UNSAT proves equivalence for the encoded scope.
Planning
Variables represent actions or states at time steps. Clauses enforce preconditions, transitions and goals. Increase the horizon until a plan is found or a bound is reached.
Encoding Cardinality Constraints
“Exactly one of n variables” combines at-least-one with at-most-one.
Pairwise encoding
For every pair i<j, add (¬Xi∨¬Xj). This uses n(n-1)/2 binary clauses. With n=100, that is 4,950 clauses.
Sequential counters
Auxiliary variables can encode running counts with linear-size clauses. More variables may produce fewer clauses and stronger or weaker propagation depending on the encoding.
Trade-offs
Smaller CNF is not automatically faster. Clause length, propagation strength, symmetry and solver heuristics matter.
Preserve meaning
Auxiliary variables may not correspond directly to domain choices. When presenting a model to users, translate the returned assignment back into the original terms.
Incremental SAT and Assumptions
Applications often solve related formulas repeatedly.
Incremental solving
Keep the solver state and learned clauses while adding constraints. This can reuse work, provided learned clauses remain valid in the evolving context.
Assumption literals
Temporary literals activate or deactivate conditions for one solve call. If the formula is UNSAT under assumptions, the solver can return an unsatisfiable core: a subset of assumptions sufficient for contradiction.
Explanation
An UNSAT core can help explain why no configuration works, but it may not be minimal. Minimising cores requires additional computation.
Product configuration
Users can toggle features while the base compatibility formula stays fixed. Incremental SAT answers each choice set without rebuilding all knowledge.
Proof Certificates and Trust
For SAT, a model is easy to check: evaluate every clause. For UNSAT, “no assignment exists” needs a proof.
Proof logging
Modern solvers can emit derivation traces in formats such as DRAT or LRAT. Independent checkers verify that learned additions and deletions establish contradiction.
Trusted computing base
A small checker can be easier to audit than a highly optimised solver. The solver searches for a proof; the checker validates it.
Proof size
Some UNSAT proofs are enormous. Logging and checking add I/O and storage costs. Safety-critical workflows may accept the cost for stronger assurance.
Models need domain checking too
A SAT assignment can satisfy the CNF while the CNF incorrectly represents the real rule. Verification must cover both solver output and encoding correctness.
Symmetry and Redundant Search
If swapping two identical resources produces an equivalent solution, the solver may explore symmetric branches.
Symmetry breaking
Add a constraint choosing one canonical ordering, such as resource 1 receiving the lexicographically first role. This removes equivalent models without removing all meaningful solutions.
Danger
An incorrect symmetry-breaking clause can remove valid non-equivalent solutions. The claimed symmetry must be proven.
Human modelling insight
Recognising interchangeable choices can matter more than micro-tuning a solver. Domain structure guides the mathematical formulation.
SAT, Constraint Programming and Integer Programming
Several tools can model choices and rules.
SAT
Strong for Boolean structure, mature learning and proof ecosystems. Numeric quantities require encodings or extensions.
SMT
Satisfiability modulo theories combines Boolean search with theories such as integers, reals, arrays or bit-vectors. It can express domain relations more directly.
Constraint programming
Finite-domain variables and specialised global constraints can make scheduling models natural.
Mixed-integer programming
Linear objectives and constraints over integer or continuous variables are a natural fit, with branch-and-bound and cutting planes.
Choose by structure
The best formulation balances expressiveness, solver strength, explainability and proof requirements. Reducing everything to SAT is theoretically possible in many cases but not always the best engineering choice.
Performance Evaluation
SAT runtime distributions can be heavy-tailed. One instance may solve in milliseconds and a visually similar one may take hours.
Benchmark families
Use diverse instances from the target domain and separate tuning from evaluation. Public competition sets help compare solvers, but domain-specific workloads still matter.
Metrics
Report solved count under a time limit, runtime distributions, memory, conflicts, propagations and proof size. Geometric means or performance profiles are often more informative than one arithmetic average.
Timeouts are censored data
If an instance hits a 1,000-second limit, its true runtime is unknown, not exactly 1,000 seconds. Comparative statistics should handle timeouts explicitly.
Hardware and versions
Record processor, memory, solver commit, compiler flags, preprocessing and random seed. Reproducibility needs more than the formula file.
Misconceptions Worth Correcting
“SAT solvers test every assignment”
Modern solvers combine propagation, learning, backjumping and heuristics to avoid enormous regions.
“UNSAT means the solver gave up”
UNSAT is a logical conclusion. A timeout or unknown status is different.
“More clauses always make a problem harder”
Additional redundant clauses can strengthen propagation and make a formula easier. Clause count alone is not difficulty.
“A satisfying assignment proves the real plan is valid”
It proves the encoded formula is satisfied. The encoding and domain interpretation must also be correct.
“Heuristics make the result approximate”
Branching heuristics change search order. A complete solver still returns exact SAT or UNSAT results when it finishes correctly.
Which Mathematics Matters Most?
Boolean algebra defines formulas. Combinatorics explains the 2^n search space. Graphs represent implications. Resolution supplies sound inference. Algorithms organise propagation and backtracking. Statistics compares solvers. Optimisation and modelling translate real goals into constraints.
The article on compiler optimisation, control-flow graphs and data-flow analysis shows another fixed-point and graph-based reasoning setting. Regular expressions, finite automata, state sets and pattern matching offers a contrasting computational model with very different complexity boundaries.
A Practical Learning Sequence
1. Evaluate small formulas under complete truth tables. 2. Translate implication, at-least-one and at-most-one rules into clauses. 3. Perform unit propagation by hand. 4. Draw decision levels and reason edges. 5. Analyse one conflict and derive a learned clause by resolution. 6. Compare chronological backtracking with backjumping. 7. Encode a small timetable and validate every returned model against the story.
A paper activity
Give learners cards labelled A and ¬A, B and ¬B, and so on. Each rule card contains a clause. Choose a decision, remove falsified literals and highlight unit clauses. When a clause becomes empty, trace which choices caused the conflict.
A coding project
Build a tiny DPLL solver with CNF input, unit propagation and recursive branching. Add reason recording and count visited decisions. Then implement a simple learned-clause mechanism or compare against MiniSat on small formulas.
Tests should include a satisfiable formula with several models, an immediate level-zero contradiction, a propagation chain, an XOR-style constraint and a pigeonhole instance. Validate models independently.
Guidance for Students
Translate carefully. Most errors occur before the solver runs. Test each clause by asking which forbidden assignment makes it false.
Keep decision facts separate from propagated facts. A reason clause explains why a literal was forced. That distinction makes the implication graph meaningful.
Do not equate practical success with an easy worst case. SAT remains theoretically hard while modern solvers handle many enormous structured instances. Both facts can be true.
Guidance for Parents and Teachers
SAT is an excellent logic laboratory. Start with three or four variables so learners can check every assignment. Then show how propagation replaces repeated truth-table work.
Ask students to explain a contradiction as a chain of reasons, not merely announce “impossible.” This builds proof habits and communication skills.
Celebrate modelling revisions. If a returned schedule violates the story, the solver has exposed an encoding error. Debugging the model is genuine mathematical work, not failure.
Did You Know?
A learned clause is both memory and proof. It prevents the solver from repeating a conflicting combination, and because it is derived by sound resolution, it remains true for every model of the original formula.
Another surprise is that restarting can accelerate exact reasoning. The solver discards the current guesses but keeps learned consequences. It changes route without forgetting what the contradictions taught.
A Worked Scheduling Encoding
Three talks—Art, Biology and Computing—must occupy morning or afternoon. Let A, B and C mean the corresponding talk is in the morning.
Rules are:
1. Art and Biology cannot both be in the morning: (¬A∨¬B). 2. At least one of Biology or Computing is in the morning: (B∨C). 3. If Computing is in the morning, Art is in the afternoon: (¬C∨¬A). 4. Art must be in the morning: (A).
Propagate
Clause 4 forces A=true. Clause 1 then forces B=false. Clause 2 forces C=true. Clause 3 with C=true forces A=false, conflicting with A=true. The formula is UNSAT.
Explain the contradiction
Art morning excludes Biology morning. With Biology afternoon, rule 2 requires Computing morning. Computing morning excludes Art morning. These rules form an implication cycle ending in the negation of the starting fact.
Repair the model, not the solver
If rule 3 was mistranslated and should say “Computing morning implies Art morning,” its clause is ¬C∨A, not ¬C∨¬A. After correction, assignment A=true, B=false, C=true satisfies every clause. The solver’s contradiction was useful evidence about the encoded rules.
Add room capacity
Suppose Art and Computing need the same room and cannot share a period. They must have opposite truth values: (A∨C)∧(¬A∨¬C). This XOR conflicts with the corrected implication when A is forced true and C becomes true. Modelling makes the policy conflict explicit.
Tseitin Encoding Without Exponential Expansion
Converting a nested Boolean formula to CNF by distributing OR over AND can grow exponentially. Tseitin-style encoding introduces an auxiliary variable for each subformula and clauses enforcing equivalence.
Example AND gate
Let X represent A∧B. Enforce X↔(A∧B) using clauses (¬X∨A), (¬X∨B) and (X∨¬A∨¬B). The first two say X implies both inputs. The third says both inputs imply X.
Example OR gate
Let Y represent X∨C. Enforce Y↔(X∨C) using (¬X∨Y), (¬C∨Y) and (¬Y∨X∨C). To require the whole formula true, add unit clause (Y).
Equisatisfiable versus equivalent
The extended CNF uses new variables, so assignments over all variables are not identical to the original formula’s assignments. It is equisatisfiable: a model exists for one exactly when a compatible model exists for the other. Project the result onto original variables.
Linear growth
Each connective adds a constant number of clauses, so formula size grows linearly with the syntax tree rather than through repeated distribution. Auxiliary variables often also create useful propagation structure.
Preprocessing and Inprocessing
Solvers simplify formulas before and during search.
Pure literals
If variable P appears only positively, setting P=true satisfies all of its occurrences without directly harming another clause. In model-finding contexts, pure-literal elimination can simplify the formula, though modern interactions with proof logging and incremental use require care.
Subsumption
Clause (A∨B) subsumes (A∨B∨C). Any assignment satisfying the shorter clause satisfies the longer, so the longer clause is redundant.
Variable elimination
Resolve clauses containing X with clauses containing ¬X, add needed resolvents and remove the original X clauses when growth is controlled. Reconstruct eliminated values when a model is returned.
Blocked clause elimination
A clause may be removable when resolving on a particular literal always produces tautologies. This preserves satisfiability but can complicate model reconstruction and proof traces.
Inprocessing
Simplification during search can exploit learned information. The solver must preserve incremental assumptions, proof correctness and reason references. An optimisation that silently changes meaning is unacceptable.
Practice Problems With Solutions
Problem 1: Translate implication
“If P then Q” is ¬P∨Q. It is false only when P=true and Q=false. “P only if Q” has the same direction; “P if Q” means Q→P.
Problem 2: Unit propagation
Formula (A∨B)∧(¬B∨C)∧(¬C). From ¬C, clause 2 forces ¬B. Clause 1 then forces A. The model A=true, B=false, C=false satisfies all clauses.
Problem 3: Immediate UNSAT
Formula (X)∧(¬X) conflicts at decision level zero. No branching is needed. A proof checker can validate the contradiction directly.
Problem 4: Resolution
Resolve (A∨B∨C) with (¬B∨D) on B to obtain (A∨C∨D). The resolvent is satisfied by every assignment satisfying both parents.
Problem 5: Blocking a model
To block model A=true, B=false, C=true, add clause (¬A∨B∨¬C). It is false exactly on that complete assignment and permits every other assignment.
Problem 6: Count pairwise clauses
At-most-one over 20 variables uses 20×19/2=190 pairwise binary clauses. This may be fine for 20 but expensive for thousands, motivating alternative encodings.
Problem 7: Read solver status
SAT with a model means a satisfying assignment was found. UNSAT means contradiction was established. UNKNOWN or timeout means neither conclusion was produced within limits. Reporting timeout as UNSAT is a serious error.
FAQ
Is SAT used only in research?
No. SAT and related solvers support hardware and software verification, planning, configuration, testing, scheduling and dependency reasoning. The suitability depends on the formulation.
Why use CNF?
CNF supports efficient propagation and standard solver interfaces. General formulas can be converted with auxiliary variables while controlling growth, for example through Tseitin-style encodings.
Does a solver find all models?
Usually it stops after one model. Repeatedly add blocking clauses to enumerate more, though the number of models can itself be exponential.
What is a clause database?
It contains original and learned clauses plus indexing structures such as watch lists. Solvers periodically reduce learned clauses to manage memory and propagation cost.
Can SAT optimise a score?
Plain SAT asks feasibility. Optimisation can be layered through repeated bounds or handled by MaxSAT and pseudo-Boolean solvers.
What should a student remember?
Clauses describe allowed choices. Unit propagation derives necessities. Conflicts reveal impossible combinations. CDCL learns a clause, backjumps and searches again with more knowledge.
Useful Next Reading
- Read the concise MiniSat v1.13 paper and identify propagation, decision and learning components.
- Read crossword grids, rotational symmetry and constraint satisfaction for a familiar constraint-model example.
- Read jigsaw puzzles, edge matching and search complexity to compare combinatorial search with different structure.
Final Perspective
SAT solvers show why mathematics matters when possibilities explode. Logic compresses rules into clauses. Propagation turns local facts into consequences. Implication graphs expose the causes of failure. Resolution converts a contradiction into a lesson. Restarts and heuristics steer the proof search without changing the meaning of SAT or UNSAT.
The inspiring part is not that every hard problem becomes easy. It is that precise representation and reusable reasoning can make astonishingly large structured problems tractable. A solver progresses because it remembers why a path failed—and mathematics guarantees that the learned lesson is safe to keep.