notes.html
problem 96 · 56 lines
<article>
<h3>Problem Analysis</h3>
<p>
Sudoku is a textbook <a class="reference-source" href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem" rel="noopener noreferrer" target="_blank">constraint-satisfaction problem</a> (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.
</p>
<p>
The single observation that makes every approach below work is that constraints <em>propagate</em>: 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 <em>n</em>x<em>n</em> board is <a class="reference-source" href="https://en.wikipedia.org/wiki/NP-completeness" rel="noopener noreferrer" target="_blank">NP-complete</a>, 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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Backtracking" rel="noopener noreferrer" target="_blank">backtracking</a> with candidate propagation, a reduction to <a class="reference-source" href="https://en.wikipedia.org/wiki/Exact_cover" rel="noopener noreferrer" target="_blank">exact cover</a> solved by <a class="reference-source" href="https://en.wikipedia.org/wiki/Dancing_Links" rel="noopener noreferrer" target="_blank">Dancing Links</a>, and <a class="reference-source" href="https://en.wikipedia.org/wiki/Constraint_propagation" rel="noopener noreferrer" target="_blank">constraint propagation</a> driven to a fixpoint before guessing. All three are <a class="reference-source" href="https://en.wikipedia.org/wiki/Depth-first_search" rel="noopener noreferrer" target="_blank">depth-first searches</a> 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.
</p>
<h3>Solution Approach</h3>
<h4>Backtracking with MRV and Forward Checking (Python and C, index 0)</h4>
<p>
The first solution attacks the grid directly with <a class="reference-source" href="https://en.wikipedia.org/wiki/Depth-first_search" rel="noopener noreferrer" target="_blank">depth-first</a> <a class="reference-source" href="https://en.wikipedia.org/wiki/Backtracking" rel="noopener noreferrer" target="_blank">backtracking</a>, in five stages.
</p>
<p>
<strong>Stage 1 - Candidates for one cell.</strong> For an empty cell <code>(row, col)</code> 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: <code>box_row = row - row % 3</code>. Python uses a real <code>set</code> with <code>discard</code>; C uses a length-10 boolean array <code>possible[]</code> indexed by digit, then collapses the marked entries into a compact array. Both compute the same set, but the C version avoids hashing entirely.
</p>
<p>
<strong>Stage 2 - Build the working set once.</strong> I scan all 81 cells and, for each empty one, store a <code>(row, col, candidates)</code> triple. Doing this once per puzzle means the recursion never has to rescan the raw grid to recompute candidates.
</p>
<p>
<strong>Stage 3 - MRV selection.</strong> Before each recursive step I sort the empty-cell list by candidate-set size, ascending, and take the first element. This is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem#Variable_and_value_ordering" rel="noopener noreferrer" target="_blank">minimum remaining values</a> (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.
</p>
<p>
<strong>Stage 4 - Propagate on assignment.</strong> When I tentatively place digit <code>d</code>, I remove it from the candidate sets of every remaining cell in the same row, column, or box. This is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Look-ahead_(backtracking)" rel="noopener noreferrer" target="_blank">forward checking</a> step. Crucially I produce a <em>new</em> candidate list rather than mutating the old one: Python's <code>update_possibilities</code> returns a fresh list of tuples, and C copies the remaining cells with <code>memcpy</code> before editing the copy. That makes undoing a choice on <a class="reference-source" href="https://en.wikipedia.org/wiki/Backtracking" rel="noopener noreferrer" target="_blank">backtracking</a> free - I simply drop the modified copy.
</p>
<p>
<strong>Stage 5 - Recurse and backtrack.</strong> 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 <code>grid[row][col] = 0</code> 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.
</p>
<h4>Exact Cover via Algorithm X and Dancing Links (Python and C, index 1)</h4>
<p>
The second solution reformulates the puzzle as an <a class="reference-source" href="https://en.wikipedia.org/wiki/Exact_cover" rel="noopener noreferrer" target="_blank">exact cover</a> problem and solves it with <a class="reference-source" href="https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X" rel="noopener noreferrer" target="_blank">Algorithm X</a>. An <a class="reference-source" href="https://en.wikipedia.org/wiki/Exact_cover" rel="noopener noreferrer" target="_blank">exact cover</a> 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 <em>column</em> is one of 324 constraints (81 "cell <code>(r,c)</code> is filled", 81 "row <code>r</code> contains digit <code>d</code>", 81 "column <code>c</code> contains digit <code>d</code>", 81 "box <code>b</code> contains digit <code>d</code>"), and each matrix <em>row</em> 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.
</p>
<p>
<a class="reference-source" href="https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X" rel="noopener noreferrer" target="_blank">Algorithm X</a> 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. <a class="reference-source" href="https://en.wikipedia.org/wiki/Dancing_Links" rel="noopener noreferrer" target="_blank">Dancing Links</a> (Knuth's technique, abbreviated DLX) stores every 1 as a node threaded into two <a class="reference-source" href="https://en.wikipedia.org/wiki/Doubly_linked_list" rel="noopener noreferrer" target="_blank">circular doubly-linked lists</a> - 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 <code>x</code> with <code>x.left.right = x.right; x.right.left = x.left</code> leaves <code>x</code>'s own pointers untouched, so the very same node can later splice itself back in with <code>x.left.right = x; x.right.left = x</code>. "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.
</p>
<p>
I keep the node mesh in seven parallel integer arrays (<code>left</code>, <code>right</code>, <code>up</code>, <code>down</code>, <code>column</code>, <code>size</code>, <code>row_id</code>) 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 <code>size</code> (Knuth's S heuristic), the DLX analogue of <a class="reference-source" href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem#Variable_and_value_ordering" rel="noopener noreferrer" target="_blank">minimum remaining values</a>: 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 <code>row_id</code> back into its <code>(row, col, digit)</code> and write the digits into the grid.
</p>
<h4>Constraint Propagation to a Fixpoint (Python and C, index 2)</h4>
<p>
The third solution, following <a class="reference-source" href="https://norvig.com/sudoku.html" rel="noopener noreferrer" target="_blank">Peter Norvig's well-known essay</a>, 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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Constraint_propagation" rel="noopener noreferrer" target="_blank">constraint-propagation</a> fixpoint - a state where no further deduction is possible.
</p>
<p>
<strong>The two propagation rules.</strong> Everything is expressed through one primitive, <code>eliminate(cell, digit)</code>, which removes a digit from a cell's candidate set and enforces two consequences. (1) <em>Naked single</em>: 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) <em>Hidden single</em>: 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 <code>eliminate</code> (via <code>assign</code>, which fixes a cell by eliminating all its <em>other</em> 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.
</p>
<p>
<strong>Search only when stuck.</strong> Seeding the grid is just <code>assign</code>-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 <a class="reference-source" href="https://en.wikipedia.org/wiki/Constraint_satisfaction_problem#Variable_and_value_ordering" rel="noopener noreferrer" target="_blank">minimum remaining values</a> 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.
</p>
<p>
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 <code>assign</code>/<code>eliminate</code> pair; the only structural difference is that C copies an 81-int array on each guess where Python slices a list.
</p>
<p>
All three solutions parse the puzzle file the same way: Python expresses parsing as a <a class="reference-source" href="https://en.wikipedia.org/wiki/Generator_(computer_programming)" rel="noopener noreferrer" target="_blank">generator</a> over the file lines, while C uses <code>strtok_r</code> 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.
</p>
</article>