Proven Sudoku
Techniques / Brute force and theory
Exact Cover and Dancing Links
Also called Algorithm X, DLX, Knuth's Algorithm X, Exact cover.
New to this shorthand? How to read a sudoku grid explains r4c7, houses, candidates and the rest.
What it means
A sudoku can be rewritten as a tidy tick box puzzle. Each need gets ticked once. Computers are very fast at that shape. It is how a program checks a board has just one answer.
The exact rule, for stronger players
The rule, stated exactly: Sudoku is an exact cover problem: 729 candidate placements, 324 constraints (81 cell, 81 row-digit, 81 column-digit, 81 box-digit), and a solution is a subset of placements covering each constraint exactly once.
What it removes: Not an elimination technique. It computes the solution set, which is what proves uniqueness.
Why it works: The four constraint families encode the rules exactly. Any exact cover is a valid grid and any valid grid is an exact cover, so the reduction is faithful.
Worked examples
None yet. This pattern does not turn up in our daily boards, so there is no real example to show. We would rather wait than draw a fake one.
Related brute force
- Minimal Puzzles and the 17-Clue ResultA puzzle is minimal when you cannot take away any clue without giving it a second answer.
- SAT and Constraint Programming EncodingsThe puzzle is turned into a long list of yes or no questions.
- Unavoidable Sets and Puzzle GenerationAn unavoidable set is a group of squares you could rearrange to get a second answer.
- Difficulty Rating EnginesPrograms give a puzzle a score.
How often does it come up?
Our rough estimate: not a solving technique. It is how a computer proves a published board has exactly one solution, which is a different job from solving one by hand.