Project 8: Sudoku Constraint Solver

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Beginner-Intermediate
  • Time: 8-14 hours (about a weekend)
  • Language: Python (alternatives: JavaScript, C++)
  • Prerequisites: Projects 2 and 7
  • Source: Prog P01

What You Will Build

Build a Sudoku solver that treats each empty cell as a set of candidates constrained by its row, column, and 3×3 box. Read a standard 81-character or formatted grid, validate the givens, repeatedly apply constraint propagation, and explain every forced placement. When deduction stalls, choose a constrained cell, branch, and backtrack on contradiction. The final report should distinguish deductions from guesses, show search depth and explored branches, and reject malformed, contradictory, or non-unique puzzles according to a documented mode.

Real World Outcome

For a valid puzzle, the CLI prints the solved grid plus a replayable sequence such as “r4c7 = 9 because 9 is its only remaining candidate.” It reports propagation rounds and search statistics. A contradictory puzzle points to the conflicting row/column/box; an unsatisfiable puzzle returns no solution; an optional uniqueness check searches for a second solution rather than assuming the first is unique.

Core Question

How can a set of local constraints shrink a huge search space, and when should deterministic deduction give way to systematic backtracking?

Concepts You Must Understand First

  1. Sets and predicates: candidates are values satisfying all active constraints.
  2. Constraint satisfaction problems: variables, domains, constraints, assignments, and contradictions.
  3. Propagation: every assignment removes possibilities from peers and may force new assignments.
  4. Backtracking search: branch, propagate, detect failure, undo, and try the next value.
  5. Search heuristics: choosing the cell with the fewest candidates usually exposes contradictions sooner. See Skiena and Revilla, Programming Challenges.

Build Milestones

  1. Parse and validate grids; construct peer sets for every cell.
  2. Compute candidates and implement naked singles with an explanation log.
  3. Add hidden singles in each row, column, and box; propagate until no changes occur.
  4. Add recursive backtracking with complete state isolation and minimum-remaining-values selection.
  5. Detect invalid, unsatisfiable, solved, and optionally non-unique outcomes with tests.

Hints in Layers

  1. Precompute each cell’s peers once; repeated row/column/box scans are simpler when relationships are explicit.
  2. Make propagation return one of three states: contradiction, stable unsolved, or solved.
  3. Copy or immutably derive candidate state at each branch; debugging shared mutable state is far harder than spending modest memory.

Common Pitfalls and Debugging

  • Symptom: a backtracked branch contaminates later attempts. Cause: candidate sets were mutated in place across recursion. Fix: clone state or use an explicit reversible change log.
  • Symptom: the solver loops without progress. Cause: a propagation pass reports change even when no candidate changed. Fix: compare before/after state and assert monotonic candidate removal.
  • Symptom: a full grid is accepted though invalid. Cause: completion was checked without constraints. Fix: validate every unit before declaring success.

Definition of Done

  • Input validation identifies malformed and contradictory givens.
  • Constraint propagation explains forced placements before search.
  • Backtracking solves puzzles that deduction alone cannot.
  • Branch state is isolated and search statistics are reproducible.
  • Tests cover easy, hard, invalid, unsatisfiable, and multiple-solution cases.

Previous: Project 7 · Complete learning path · Next: Project 9