aldus.nexus

Sudoku

Play with pencil marks and hints that explain themselves, then race plain backtracking, constraint propagation and Knuth's dancing links on the same puzzle.

- pen 00:00

The numbers

search depth through each search% of its own run
nodes and backtrackslog scale
solve time, this puzzlemedian of plain runs
digits placed, by puzzle grademedian over the library

How it works

Sudoku is a constraint satisfaction problem: 81 variables, each a digit from 1 to 9, and 27 groups (nine rows, nine columns, nine boxes) whose digits must all differ. Every puzzle here has exactly one solution, checked by counting solutions and stopping at two.

Plain backtracking

Walk the empty cells in reading order. Put the smallest digit that doesn't clash; if nothing fits, step back to the previous cell and try its next digit. It always finds the answer, but it learns nothing as it goes. The puzzle called brute force's nightmare has 987654321 as its top row, so trying 1 first is wrong for the first nine cells, and it takes 69,175,316 placements. Like the bogosort in Sorting, it is honest and hopeless.

Propagation and MRV

After every placement, fill in whatever is now forced: a naked single (a cell with one candidate left) or a hidden single (a digit with one place left in a group). Only then guess, and guess in the cell with the fewest candidates, the minimum remaining values rule, so a wrong guess fails fast. Most puzzles in the library need no guesses at all; the famous monsters need tens to a few hundred. Wave function collapse does the same dance: pick the most constrained spot, propagate, back up when stuck.

Exact cover and dancing links

Knuth's Algorithm X sees sudoku as exact cover. Each of the 729 rows is one digit in one cell, and each fills four of the 324 columns: that cell, that digit in its row, in its column and in its box. A solution is a set of rows that fills every column exactly once. Pick the column with fewest rows, try each row in turn, and cover every column that row fills, removing all the rows that clash. A column with one row is a naked single if it is a cell column, a hidden single if it is a digit column, so the size rule finds both for free.

Dancing links makes covering cheap. The matrix's 1s sit in circular doubly linked lists, and removing a node x is two assignments, L[R[x]] = L[x] and R[L[x]] = R[x]. Node x still remembers its neighbours, so R[L[x]] = x and L[R[x]] = x put it back exactly. Undo the covers in reverse order and the links dance back into place, with no copying. Watch the column bars above shrink and spring back.

Hard for whom?

People grade a puzzle by the hardest trick it needs: singles, then pointing pairs and box-line reductions, naked and hidden pairs, triples, X-wings and Y-wings; past those it is fiendish. Computers grade by the size of the search tree. The two disagree: brute force's nightmare needs nothing beyond singles, yet plain backtracking grinds through 69 million placements; AI Escargot defeats every trick in the hint button, yet dancing links settles it in about 150 nodes. Searching trees of choices, and how much ordering matters, is the theme of Minimax too.

four pointer assignments, run forwards and then backwards, turn a hopeless search into a few hundred moves, and the same sizes that guide it are the singles people spot by eye.

729 rows × 324 columnsa row is a digit in a cell; its four 1s are the cell, and the digit in that row, column and box
L[R[x]] ← L[x],  R[L[x]] ← R[x]remove x from its list; x keeps its own links, so R[L[x]] ← x, L[R[x]] ← x restores it
c = argmin S[c]branch on the column with fewest rows left: size 1 is a forced move, size 0 a dead end
nodes ≤ 9ethe worst case for e empty cells; propagation and good ordering cut it by many orders of magnitude