Problem Analysis
Sudoku is a textbook constraint-satisfaction problem (a CSP - a set of variables, each drawn from a domain of allowed values, subject to constraints that forbid certain combinations). Here the 81 cells of the 9x9 grid are the variables, the digits 1-9 are the domain, and the constraints say that each digit appears exactly once in every row, column, and 3x3 box. Some cells are pre-assigned (the clues); the task is to fill the rest without violating any constraint. There is no arithmetic shortcut - the entire problem is structural, and progress comes only from systematically eliminating illegal assignments.
The single observation that makes every approach below work is that constraints propagate: the instant you fix a digit in a cell, every other empty cell sharing its row, column, or box loses that digit as a candidate. This shrinks the search space dramatically. In the general case, deciding Sudoku on an nxn board is NP-complete, so no polynomial-time algorithm is known and the worst case is exponential in the number of empty cells. What makes these fifty puzzles tractable is that each has a unique solution reachable by aggressive pruning, so the effective branching factor stays close to one. I solved the problem three different ways: direct backtracking with candidate propagation, a reduction to exact cover solved by Dancing Links, and constraint propagation driven to a fixpoint before guessing. All three are depth-first searches over partial assignments; they differ in how they represent the constraints, how much they deduce before branching, and how cheaply they undo a tentative choice.
Solution Approach
Backtracking with MRV and Forward Checking (Python and C, index 0)
The first solution attacks the grid directly with depth-first backtracking, in five stages.
Stage 1 - Candidates for one cell. For an empty cell (row, col) I start with {1..9} and discard every digit already present in its row, column, and 3x3 box. The box origin is found by snapping the coordinate down to the nearest multiple of three: box_row = row - row % 3. Python uses a real set with discard; C uses a length-10 boolean array possible[] indexed by digit, then collapses the marked entries into a compact array. Both compute the same set, but the C version avoids hashing entirely.
Stage 2 - Build the working set once. I scan all 81 cells and, for each empty one, store a (row, col, candidates) triple. Doing this once per puzzle means the recursion never has to rescan the raw grid to recompute candidates.
Stage 3 - MRV selection. Before each recursive step I sort the empty-cell list by candidate-set size, ascending, and take the first element. This is the minimum remaining values (MRV) heuristic - always branching on the most constrained cell does the heavy lifting. A cell with zero candidates is an immediate dead end (prune now); a cell with one candidate is a forced move (no branching at all). This keeps the search tree narrow.
Stage 4 - Propagate on assignment. When I tentatively place digit d, I remove it from the candidate sets of every remaining cell in the same row, column, or box. This is the forward checking step. Crucially I produce a new candidate list rather than mutating the old one: Python's update_possibilities returns a fresh list of tuples, and C copies the remaining cells with memcpy before editing the copy. That makes undoing a choice on backtracking free - I simply drop the modified copy.
Stage 5 - Recurse and backtrack. An empty working set means the grid is full - success. Otherwise I try each candidate of the chosen cell, writing it into the grid in place. If recursion succeeds the answer bubbles up; if a candidate leads nowhere I reset grid[row][col] = 0 and try the next. The C version adds one optimisation: after propagation it scans the copied cells and skips the recursive call entirely if any cell has dropped to zero candidates - a fail-fast check that saves a function call on doomed branches. Python relies on the same condition being detected one level deeper.
Exact Cover via Algorithm X and Dancing Links (Python and C, index 1)
The second solution reformulates the puzzle as an exact cover problem and solves it with Algorithm X. An exact cover takes a 0/1 matrix and asks for a subset of its rows that, summed, place exactly one 1 in every column. I encode Sudoku into that shape: each column is one of 324 constraints (81 "cell (r,c) is filled", 81 "row r contains digit d", 81 "column c contains digit d", 81 "box b contains digit d"), and each matrix row is a single placement of a digit in a cell, marking the exactly four constraints it discharges. A clue emits only the one row matching its given digit; an empty cell emits all nine. A solved grid is then precisely a choice of 81 rows covering all 324 columns once each.
Algorithm X is the obvious recursion on this matrix: pick an uncovered column, try each row that covers it, recurse, undo on failure. Its efficiency comes entirely from how the matrix is stored. Dancing Links (Knuth's technique, abbreviated DLX) stores every 1 as a node threaded into two circular doubly-linked lists - one along its row, one down its column - with a header node per column tracking how many 1s remain. The defining trick is that unlinking a node x with x.left.right = x.right; x.right.left = x.left leaves x's own pointers untouched, so the very same node can later splice itself back in with x.left.right = x; x.right.left = x. "Covering" a column unlinks it and every row touching it; "uncovering" reverses it exactly - the structure dances its rows in and out of existence as the search descends and backtracks, with no allocation and no copying.
I keep the node mesh in seven parallel integer arrays (left, right, up, down, column, size, row_id) indexed by node id - identical in Python and C, which makes the port line-for-line faithful. The recursion always covers the column with the smallest size (Knuth's S heuristic), the DLX analogue of minimum remaining values: branching on the most constrained obligation minimises fan-out. When the header ring is empty every constraint is met; I then decode each chosen row's row_id back into its (row, col, digit) and write the digits into the grid.
Constraint Propagation to a Fixpoint (Python and C, index 2)
The third solution, following Peter Norvig's well-known essay, deduces as much as possible before ever guessing. Each cell holds a set of candidate digits, and the solver maintains its invariant by propagating two logical rules to a constraint-propagation fixpoint - a state where no further deduction is possible.
The two propagation rules. Everything is expressed through one primitive, eliminate(cell, digit), which removes a digit from a cell's candidate set and enforces two consequences. (1) Naked single: if the removal leaves the cell with exactly one candidate, that value is forced, so I eliminate it from all 20 of the cell's peers (the cells sharing its row, column, or box). (2) Hidden single: if, within any unit the cell belongs to, the just-removed digit now has only one cell where it can legally go, I place it there. Both consequences call back into eliminate (via assign, which fixes a cell by eliminating all its other candidates), so a single removal can cascade across the whole grid until the fixpoint is reached. A cell emptied of all candidates, or a unit with nowhere for a digit, signals a contradiction and the propagation fails.
Search only when stuck. Seeding the grid is just assign-ing each clue, which triggers the cascade; for the easier puzzles this alone solves the grid with no guessing. When propagation stalls with cells still ambiguous, I pick the unsolved cell with the fewest candidates (the same minimum remaining values idea) and try each candidate on a fresh copy of the state, recursing. Because every guess is immediately propagated to a new fixpoint, contradictions surface almost at once and the tree stays shallow.
Like the exact-cover solver, I represent each candidate set as a 9-bit integer mask, so "remove a digit" is one bit-clear, "is this digit still possible" is one bit-test, and "how many candidates remain" is a population count. Python and C share the same bit layout and the same mutually-recursive assign/eliminate pair; the only structural difference is that C copies an 81-int array on each guess where Python slices a list.
All three solutions parse the puzzle file the same way: Python expresses parsing as a generator over the file lines, while C uses strtok_r to split the in-memory buffer on newlines and accumulates rows until it has nine. Each then reads the three-digit top-left number off every solution and sums across all fifty.