Skip to content
Tutorials Center
My learning

Topics

Lesson 58 of 68 ยท Projects

Project: A Tiny SAT Solver

Build a SAT solver from scratch: parse formulas, convert to CNF, run DPLL with unit propagation, then solve a Sudoku and an exam schedule.

The satisfiability problem (SAT) asks: given a logical formula, is there a way to set its variables to true and false so the whole formula is true? It sounds abstract, but it is one of the most useful problems in computer science. Hardware verification, package managers, planning, scheduling and puzzle solving can all be translated into SAT and handed to a solver. Modern solvers handle formulas with millions of variables.

In this project you build a small but real solver. You will parse formulas written as text, convert them to conjunctive normal form (CNF), implement the DPLL algorithm with unit propagation, test it against brute force, and then use it to solve a Sudoku and to schedule exams. The theory is in normal forms and SAT and truth tables; here we put it to work.

The plan

Parse Turn text like p -> q into a tree.
CNF Rewrite as an AND of ORs of literals.
DPLL Search with smart pruning.
Puzzles Encode Sudoku and schedules as SAT.
1 / 2

Step 1: formulas as text

We want to type formulas like (p | q) & ~r -> s. The symbols are ~ (not), & (and), | (or), -> (implies) and <-> (if and only if), with the usual precedence: ~ binds tightest, then &, then |, then ->, then <->. A small recursive-descent parser has one function per precedence level. Each function parses operands of the next-tighter level and combines them. The result is a tree such as ("and", ("var", "p"), ("not", ("var", "q"))).

Step 2: converting to CNF

A literal is a variable or its negation. A clause is an OR of literals. A formula in CNF is an AND of clauses. SAT solvers work on CNF because the structure is uniform: the formula is satisfied when every clause has at least one true literal.

The conversion has three stages:

  1. Eliminate -> and <-> using p -> q โ‰ก ~p | q and p <-> q โ‰ก (p -> q) & (q -> p).
  2. Push negations inward with De Morgan's laws until only variables are negated (negation normal form, NNF).
  3. Distribute OR over AND: a | (b & c) โ‰ก (a | b) & (a | c).

We represent a clause as a frozenset of nonzero integers: variable number k is the literal k, and its negation is -k. This is the same idea as the standard DIMACS file format that real solvers use. Tautological clauses (containing both x and -x) are dropped, as they are always true.

Distribution can blow up exponentially: (a1 & b1) | (a2 & b2) | ... produces 2^n clauses. Real tools use the Tseitin transformation, which adds helper variables to keep the size linear. For our small formulas, distribution is fine and easy to follow.

Python Parser and CNF converter

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 the third line of output: (a & b) | (c & d) becomes four clauses, one for each way of picking one item from each side. And the second formula, De Morgan's law, has no clauses at all, because every clause was a tautology. An empty CNF means "always true".

Step 3: DPLL with unit propagation

The brute-force approach tries all 2^n assignments. DPLL (Davis, Putnam, Logemann, Loveland) is a backtracking search that prunes most of that work. Given a list of clauses:

  • Unit propagation: if a clause has just one literal left, that literal must be true. Set it, then simplify: clauses containing that literal are satisfied and removed, and the opposite literal is deleted from the others. Repeat until no unit clause remains.
  • Conflict: if simplification creates an empty clause, this branch is contradictory. Backtrack.
  • Success: if no clauses remain, every clause is satisfied; the variables set so far are a model (unset variables are free).
  • Branch: otherwise pick a variable, try it true, and if that fails try it false.

Modern solvers add clause learning, restarts and clever variable ordering (CDCL), but this core loop is the heart of all of them. The function assign below does the simplification; dpll returns a model (a dictionary from variable number to True or False) or None. We add counters for decisions and unit propagations so we can see how much guessing was needed.

Python DPLL, tested against brute force

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 chain of implications is solved by propagation alone: zero decisions. The contradiction is also found without guessing. On 200 random 3-SAT formulas with 8 variables and 34 clauses, DPLL agrees with brute force every time, and the average number of decisions is far below the 256 assignments brute force may need. The ratio of clauses to variables (here 4.25) is near the point where random 3-SAT flips from mostly satisfiable to mostly unsatisfiable, and that is where formulas are hardest.

Step 4: putting it together

Now we connect the pieces: text in, answer out. To check whether a formula is satisfiable, convert it and run DPLL. To check whether it is valid (a tautology, true in every row), ask whether its negation is unsatisfiable. That is exactly how SAT solvers prove theorems: they search for a counterexample and fail.

Python From formula text to an answer

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.

We can now verify logical laws without writing truth tables: the contrapositive and De Morgan's law are valid, while confusing an implication with its converse is not. Compare with implication and the biconditional.

Step 5: solving puzzles by encoding

The real power of SAT is that you describe what a solution looks like and let the solver find one. The recipe is: choose boolean variables, then write clauses for the rules. A recurring building block is "exactly one of these is true", written as one clause (at least one) plus pairwise clauses ~a | ~b (at most one).

Sudoku (4 by 4). Use a variable v(r, c, d) meaning "cell (r, c) holds digit d". There are 4 ร— 4 ร— 4 = 64 variables. The rules are: every cell has exactly one digit; every digit appears exactly once in each row, each column and each 2 by 2 box. The given digits are unit clauses. A 9 by 9 puzzle uses the same encoding with 729 variables.

Exam scheduling. Courses that share students cannot take their exams in the same slot. Use a variable for "course c is in slot s". Each course gets a slot, and for every clash edge (a, b) and slot s, the clause ~a_s | ~b_s forbids sharing. This is graph coloring from coloring and planarity, solved by a general-purpose tool. To find the minimum number of slots, try 1, 2, 3, ... until the formula becomes satisfiable.

Python Sudoku and exam scheduling with SAT

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 puzzle has exactly one solution: after finding one, we added a clause that forbids it and asked again, and the solver reported no further model. The schedule needs three slots because Math, Physics and Chem all clash with each other, forming a triangle, so two slots can never be enough.

Ideas to extend the project

  • Add the pure literal rule: a variable that appears with only one sign can be set to satisfy all its clauses.
  • Choose branching variables by smarter rules, such as the shortest clause first, and compare the decision counts.
  • Read and write the DIMACS CNF text format, so you can test your solver on files from the standard SAT benchmarks.
  • Encode N-Queens or a small Latin square, and count the solutions by blocking each model.
  • Implement Tseitin conversion so large formulas stay small.
  • Add watched literals, the data structure that makes real solvers fast, in place of rescanning every clause.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does unit propagation do?

    A clause with a single literal can only be satisfied by making that literal true, so the value is forced and the formula can be simplified.
  2. 2. To check that a formula F is valid (true in every row) with a SAT solver, you:

    F is valid exactly when no assignment makes it false, that is, when ~F has no satisfying assignment.
  3. 3. What does an empty clause mean during DPLL?

    A clause with no literals left cannot be satisfied, so the whole AND is false under the current choices.
  4. 4. In the SAT encoding of Sudoku, which clauses express that a cell holds at most one digit?

    At most one is written as pairwise clauses ~a | ~b; the long clause expresses at least one, and the units are the givens.
  5. 5. Why do real tools use the Tseitin transformation instead of plain distribution?

    Distributing OR over AND can make the number of clauses grow exponentially, while Tseitin adds new variables to keep growth linear.

Summary

  • SAT asks whether some assignment of true and false makes a formula true; many problems can be encoded as SAT.
  • Parsing builds a tree; converting to CNF eliminates -> and <->, pushes negations inward and distributes OR over AND.
  • DPLL combines unit propagation, branching and backtracking, and prunes most of the 2^n search space.
  • A formula is valid exactly when its negation is unsatisfiable, so SAT solvers also prove theorems.
  • To use SAT on a puzzle, pick variables, add at-least-one and at-most-one clauses for the rules, and add the givens as unit clauses.

Next: Project: A Combinatorics Toolkit, where you build counting functions and check them by brute force.