Solvers, CSP & graph methods

A teaching solver applies named human strategies (constraint propagation) and stops to explain. A backtracker assigns a candidate and recurses. Both can finish a grid; only the first matches how most people want to learn.

Live pencil marks are often a 9×9×9 boolean cube or 81 bitmasks. Naked/hidden subset tests become bit intersection and popcount checks.

Engines usually try cheap rules first (singles, pairs, pointing) and only then fish, chains, or bifurcation. The first rule that eliminates something updates the matrix and the loop restarts.

A fixed 9×9 instance is tiny. Deciding satisfiability for n×n Sudoku (or generalized Nonograms) is NP-complete. That is a complexity statement about families of instances — not a claim that your daily 9×9 needs an exponential search.

Some uniqueness checkers translate cell-digit variables into CNF and hand them to a SAT solver (including SMT tools such as Z3). Useful for authors verifying a grid; heavy for teaching UI.

Guessing a digit and forking the state space is easy to code and expensive to explore (branching factor stacks). Prefer forced eliminations; reserve bifurcation for proof search or generation.

Strong links (“if A is false then B is true”) and weak links (“if A is true then B is false”) alternate along candidates. A well-formed chain eliminates at the endpoints. Related patterns include forcing chains, remote pairs, and Medusa-style coloring.

Size-2 fish is X-Wing; larger fish (swordfish, jellyfish) restrict a digit to n lines with candidates in n crossing lines, then eliminate along those crossings. Skyscraper and 2-string kite are short chain views of related geometry — worked examples live in the Advanced Sudoku patterns guide.

Y-Wing / XYZ-Wing use small pivots and arms. Empty Rectangle ties a box pattern to an external conjugate. BUG+1 appears on near-finished grids where one trivalue cell breaks a universal bivalue deadly pattern — that extra digit is forced under uniqueness. Deeper named sets (Sue de Coq, Exocet, Medusa) sit in Advanced Sudoku patterns.

Edges of the dot grid form an undirected graph; a solution is a 2-regular connected subgraph (a single cycle) consistent with clue degrees. Search prunes partial states that violate degree or clue counts.

Each row/column filter enumerates placements compatible with its clue; information passes until a fixed point — or the solver reports under-constrained / contradictory lines.