Skip to content
Tutorials Center
My learning

Topics

Lesson 41 of 46 ยท Projects

Project: Sudoku Solver with CSP

Build a Sudoku solver as a constraint satisfaction problem in Python: AC-3 propagation, backtracking with MRV, difficulty benchmarks and hard-instance analysis.

Sudoku is the perfect constraint satisfaction problem (CSP): the rules fit in one sentence, humans solve it by exactly the reasoning that CSP algorithms automate, and the difference between a naive solver and a smart one is the difference between "never finishes" and "instant". In this project you will build the smart one in stages and measure every stage.

You will need the ideas from constraint satisfaction problems, backtracking search and constraint propagation. The plan: model the puzzle, run AC-3 to see how far pure propagation gets, add backtracking with MRV for the rest, compare against a naive solver on puzzles of increasing difficulty, and finish with an analysis of one puzzle that is nasty for the standard method.

Sudoku as a CSP

The three ingredients of every CSP:

  • Variables: the 81 cells, named by (row, column).
  • Domains: the digits each cell may still take. A cell with a given has a one-element domain; an empty cell starts with {1,...,9}.
  • Constraints: every row, column and 3x3 box contains each digit once. As binary constraints this is a set of "not equal" relations between peers, cells that share a row, column or box. Each cell has exactly 20 peers.

Representing the domains as a dictionary from cell to a Python set makes everything else short. The solver's job is to shrink domains until every cell has exactly one value.

graph TD
    P["Parse puzzle<br/>into domains"] --> A["AC-3<br/>propagate constraints"]
    A --> D{"All domains<br/>single-valued?"}
    D -- yes --> S["Solved"]
    D -- no --> V["Pick the cell with the<br/>fewest candidates (MRV)"]
    V --> T["Try one value,<br/>copy the domains"]
    T --> A
    A -- "a domain became empty" --> B["Backtrack: undo and<br/>try the next value"]
    B --> V

The solver alternates between inference (AC-3) and guessing (backtracking), and a wipe-out triggers a retreat.

Step 1: AC-3 on its own

A constraint arc (Xi, Xj) is consistent when every value left in Xi has at least one compatible value in Xj. For a "not equal" constraint the only way a value can fail is if Xj has been narrowed to that single value. So revise is tiny: if Xj has exactly one value and Xi still lists it, remove it from Xi.

AC-3 keeps a queue of arcs. It takes one, revises it, and if Xi lost a value, it re-queues every arc pointing at Xi (because those neighbors may now lose values in turn). It stops when the queue is empty (the network is arc consistent) or when a domain becomes empty (a contradiction: no solution under the current assumptions).

Python AC-3 on an easy and a hard puzzle

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.

For the easy puzzle AC-3 alone does everything: starting from 30 givens, 408 value removals fix all 81 cells, without a single guess. This is the "naked single" technique that people use, repeated automatically. The 17-given puzzle is a different story: AC-3 removes 275 candidates but fixes no new cell, leaving 318 candidates spread over the 64 empty cells (about 4.7 each). Propagation has run out of inferences, and the solver must guess.

AC-3 on Sudoku's pairwise constraints is weaker than what people do. Human solvers also use "hidden singles" (a digit that fits in only one cell of a row, column or box). That reasoning comes from the all-different constraint over a whole group, which is stronger than 20 separate "not equal" arcs. Production solvers add it, and it solves many more puzzles without search.

Step 2: Backtracking with MRV and propagation

When propagation stalls, pick a cell, try each of its candidate values in turn, propagate, and recurse. Two decisions control the cost:

  1. Which cell? The minimum remaining values (MRV) rule picks the cell with the fewest candidates. It fails fast: a cell with two candidates has a 50 percent chance of each guess being right, and a cell with zero candidates reveals a contradiction immediately.
  2. How much inference after each guess? The program implements two levels. Forward checking (FC) removes the new value from the cell's 20 peers and stops. Maintaining arc consistency (MAC) runs AC-3 after each guess, so a newly forced value ripples through the grid.

Each recursive call works on a copy of the domains, which makes backtracking trivial: to undo a guess, discard the copy. Sudoku domains are tiny (81 sets), so the copy is cheap.

For comparison, a naive solver walks the empty cells in reading order, tries 1 to 9, and checks only whether the digit conflicts with a filled peer. It does no propagation and no clever ordering.

Benchmark: easy to hard

The program below includes the full solver library (it is reused in the next program). It runs the three solvers on four puzzles and counts assignments, the number of times a value was tried in a cell. The naive solver is cut off after 20,000 assignments. Every returned solution is checked for validity.

Python Naive search versus forward checking versus MAC

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.

Read the table from left to right:

Puzzle Givens Naive FC + MRV MAC + MRV
easy 30 4,208 51 0
tricky 23 8,969 217 22
hard A 17 more than 20,000 481 130
hard B 17 more than 20,000 1,791 452
  • The naive solver needs thousands of assignments even for the easy puzzle and gives up on both hard ones. Its trouble is that it discovers a conflict only when it tries to fill a cell that has no legal digit, perhaps dozens of moves after the mistake that caused it.
  • Forward checking with MRV needs 40 to 80 times fewer assignments than naive search on the two easier puzzles and finishes the hard ones with hundreds of assignments. (It also counts forced moves as assignments, because it only notices single-valued cells when it picks them.)
  • MAC folds forced moves into propagation. For the easy puzzle it needs zero guesses, and on the hard ones it needs 3 to 4 times fewer assignments than FC. More inference per node pays for itself.

The ordering is robust, but the exact numbers are specific to the puzzles and to the tie-breaking rule (MRV picks the first cell in reading order among equals). The next program shows how much that last detail matters.

Hard instance analysis

Some Sudokus are built to defeat brute force: the puzzle below has only 17 givens, and its entire top row is empty. It is solvable, with a unique solution, but a search that makes a bad early guess can wander for a long time before discovering it.

Run MAC with different ways of breaking MRV ties: reading order (the baseline), the degree heuristic (prefer the cell that constrains the most unfilled peers) and five random tie-breakers. The program also records at which depth the dead ends occur in the baseline run.

Python Why one Sudoku is hard: variable ordering and dead ends

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.

You should see these results:

  • The baseline needs 12,094 assignments. The degree heuristic cuts that to 3,757, and the random tie-breakers land anywhere from 516 to 1,867, so the same algorithm on the same puzzle differs by a factor of 20 depending only on how ties are resolved.
  • The depth profile shows that dead ends pile up around depth 14 to 17, not near the top. The search does not fail quickly: it makes a poor guess early on, then spends thousands of nodes deep in a subtree that cannot contain a solution, because no inference prunes it. Such behavior is called heavy-tailed, and it is why real solvers use random restarts: run the search with a node limit, and if it runs out, restart with a different random tie-breaker. With limits like 2,000 assignments, all five random runs above would have finished on the first attempt.

The moral is practical: for hard instances, the quality of the variable ordering and the inference matter more than raw speed, and a little randomness protects you from unlucky choices.

Make it stronger

  • Hidden singles and naked pairs. Add the group-level reasoning described above. Many puzzles then need no guessing at all.
  • Value ordering. Try least-constraining value (LCV): try first the digit that removes the fewest candidates from peers.
  • Count solutions. Change the search to continue after the first solution and stop at two; a puzzle with more than one is not a valid Sudoku. This is the check a puzzle generator needs.
  • Generate puzzles. Fill a grid by solving an empty puzzle with random value order, then remove cells one at a time while the solution stays unique.
  • Other sizes and variants. A 16x16 board, or a "Sudoku X" with diagonal constraints, needs only a new PEERS table; the solver is generic. This is the payoff of modeling the problem as a CSP.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the CSP model of Sudoku, what are the variables, and what are the constraints?

    Each cell is a variable with a domain of candidate digits. The rules become pairwise not-equal constraints between peers, 20 peers per cell.
  2. 2. Why does the AC-3 queue get new arcs added when a domain shrinks?

    If Xi loses a value, a neighbor Xk that relied on that value may now have values without support, so arcs (Xk, Xi) must be checked again.
  3. 3. What does the MRV heuristic choose?

    MRV (minimum remaining values) picks the most constrained cell. It fails early and gets forced moves out of the way first.
  4. 4. Why is backtracking with copied domains easy to implement?

    Each recursive call gets its own copy of the domains, so returning from a failed call automatically restores the previous state.
  5. 5. Why do solvers use random restarts on hard puzzles?

    Run times vary by orders of magnitude with the choice order. Cutting a run off and trying again with another random tie-break usually beats waiting for one unlucky run.

Summary

  • Sudoku is a CSP with 81 variables, digit domains and not-equal constraints between 20 peers each.
  • AC-3 repeatedly removes values that have no support; on easy puzzles it solves everything, on hard ones it stalls and search must take over.
  • Backtracking with MRV and forward checking or MAC solves hard puzzles in hundreds of assignments, where a naive solver gives up after tens of thousands.
  • More inference per node (MAC) usually beats less (FC); both beat none by orders of magnitude.
  • Tie-breaking in variable ordering can change the work by a factor of 20 on a hard puzzle; random restarts guard against unlucky orderings.
  • Because the solver is generic, other grids and variants need only a new peer table.

Next: Project: Connect Four AI.