The Mathematics of Sudoku
Mathematics · Combinatorics · Algorithms
On counting, solving, and seeing a puzzle as a graph
Contents
Take a 9×9 grid. Fill it so that every row, every column, and every bold-bordered 3×3 box contains each of the digits 1 through 9 exactly once. The rule is that simple. And yet the mathematics hiding inside that rule can occupy you for weeks.
We are not here to learn how to beat the person next to you on the subway — though we will pick up some powerful techniques along the way. The real questions are mathematical: how many distinct completed grids are there? What is the minimum number of given clues that guarantees a unique solution? Can a human being, armed only with pencil and paper, solve any Sudoku puzzle whatsoever?
4
0
6
3
8
0
0
2
0
5
0
3
7
0
4
0
0
0
0
0
0
9
0
0
8
4
3
2
3
0
0
1
0
9
0
0
0
4
0
0
0
0
5
7
1
0
5
0
6
4
7
0
0
0
9
0
1
4
0
8
3
0
0
0
6
4
0
0
0
0
0
7
8
0
5
1
0
3
0
9
2
Sample puzzle from the introduction
§ 1Counting Sudokus
In how many distinct ways can an empty 9×9 Sudoku grid be completed? Start with a rough ceiling. Each of the 81 cells can hold at most 9 digits, so the total number of ways to fill the grid — ignoring every constraint — is at most 9⁸¹, approximately 2 × 10⁷⁷. That is astronomically large and hopelessly loose.
First upper bound
9⁸¹ ≈ 2 × 10⁷⁷
Comparable to atoms in the observable universe
Now apply the row constraint: filling left to right, the first cell of each row has 9 options, the second has 8, and so on down to 1. Each row contributes 9! = 362,880 arrangements, and nine independent rows give (9!)⁹ ≈ 1.1 × 10⁵⁰. Still enormous, but fifty orders of magnitude tighter.
We can do the same for columns and boxes. For columns, the more rows already filled above a cell, the fewer unused digits remain in that column. For boxes, each 3×3 block depletes its options in the same 9–8–7–…–1 pattern as you work through its nine cells. Drawing the per-cell maxima for each constraint separately makes the argument concrete.
9
8
7
6
5
4
3
2
1
9
8
7
6
5
4
3
2
1
9
8
7
6
5
4
3
2
1
9
8
7
6
5
4
3
2
1
9
8
7
6
5
4
3
2
1
9
8
7
6
5
4
3
2
1
9
8
7
6
5
4
3
2
1
9
8
7
6
5
4
3
2
1
9
8
7
6
5
4
3
2
1
Row constraint
9
9
9
9
9
9
9
9
9
8
8
8
8
8
8
8
8
8
7
7
7
7
7
7
7
7
7
6
6
6
6
6
6
6
6
6
5
5
5
5
5
5
5
5
5
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
Column constraint
9
8
7
9
8
7
9
8
7
6
5
4
6
5
4
6
5
4
3
2
1
3
2
1
3
2
1
9
8
7
9
8
7
9
8
7
6
5
4
6
5
4
6
5
4
3
2
1
3
2
1
3
2
1
9
8
7
9
8
7
9
8
7
6
5
4
6
5
4
6
5
4
3
2
1
3
2
1
3
2
1
Box constraint
For each cell, the actual number of viable choices cannot exceed any one of these three figures — it is bounded by all three simultaneously. Taking the cell-by-cell minimum across the three tables gives the tightest ceiling we can derive from independent constraints. Multiplying all 81 of those minima together yields approximately 1.5 × 10³¹.
Combined minimum — choices per cell
9
8
7
6
5
4
3
2
1
6
5
4
6
5
4
3
2
1
3
2
1
3
2
1
3
2
1
6
6
6
6
5
4
3
2
1
5
5
4
5
5
4
3
2
1
3
2
1
3
2
1
3
2
1
3
3
3
3
3
3
3
2
1
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
Product of all 81 entries ≈ 1.5 × 10³¹
The Exact Count (Felgenhauer & Jarvis, 2005)
Using a C++ brute-force program, Bertram Felgenhauer and Frazer Jarvis determined that the exact number of completed 9×9 Sudoku grids is 6,670,903,752,021,072,936,960 — approximately 6.7 × 10²¹. Our best hand-computed upper bound was still a billion times larger.
The gap between our upper bound and the true count arises because for each cell we used only one constraint at a time. In reality, the row, column, and box constraints interact — and their combined effect eliminates far more possibilities than any single constraint alone.
§ 2How Many Clues?
A friend hands you a hand-crafted Sudoku puzzle. After staring at it for a while, you start to wonder: does it even have a solution? And if it does, is that solution unique? The answer to both questions is, in general, very hard to determine without a computer.
Uniqueness
Perhaps surprisingly, a 9×9 Sudoku with only four empty cells need not have a unique solution. Here is a concrete demonstration: two rows with four blanks arranged in a 2×2 pattern across two boxes.
3
4
1
2
7
6
5
9
8
5
6
2
1
8
9
3
4
7
Solution A
3
4
2
1
7
6
5
9
8
5
6
1
2
8
9
3
4
7
Solution B
The highlighted cells are the four blanks. Swapping 1↔2 in those positions satisfies every row, column, and box constraint in both arrangements.
On the other hand, any solvable Sudoku with at most three empty cells is guaranteed to have exactly one solution. The argument is clean: among three empty cells, at least one must be the sole blank in its row or column. Since the other eight entries are fixed, that cell is forced.
The 17-Clue Conjecture
The minimum number of filled cells needed to guarantee a unique solution to a 9×9 Sudoku is conjectured to be 17. Puzzles with exactly 17 clues and unique solutions have been found, and an extensive computer search makes it highly unlikely that a uniquely solvable puzzle with 16 or fewer clues exists.
Existence
Can we decide systematically whether a given partial grid has at least one completion? Yes — but it often requires a great deal of work. The algorithms in the next sections provide exactly this: a method guaranteed to find a solution if one exists, or to certify that none does.
§ 3Solving Algorithms — Backtracking
An algorithm must terminate. “Stare at it and try things” does not qualify — you might never finish. A proper Sudoku-solving algorithm must always halt and report: either a solution, or a proof that none exists.
The Simple Algorithm
The counting argument suggests a direct approach: list the empty cells in order, try digits 1 through 9 for each, backtrack when you hit a dead end. Simple in description; exhaustive by nature.
Simple Solving Algorithm
Enumerate all empty cells in typewriter order (left to right, top to bottom).
Set the first cell as the current cell.
Enter 1 in the current cell. If this violates the Sudoku condition, try 2, then 3, and so on, until:
a. The entry does not violate — proceed.
b. You have tried 9 and still have a violation — backtrack.
If this was the last cell, the puzzle is solved. Otherwise, advance to the next cell and repeat.
This algorithm is correct: if a solution exists, systematic backtracking will find it. In practice, though, it is slow. A MATLAB implementation runs at roughly human speed on most puzzles, and sometimes far slower. Executing this on paper is nearly impossible; the volume of entries and erasures is prohibitive. Something better is needed.
Two Human-Friendly Techniques
Candidate-Checking: Scan each empty cell and list all digits that could legally go there given the filled cells in its row, column, and box. If only one candidate remains, write it in. Cycle through all empty cells; repeat whenever you place a digit.
Place-Finding: For each digit 1–9, examine each row, column, and box: if that digit can be placed in exactly one empty cell within the unit, place it. Once a full sweep yields nothing new, this method is exhausted.
Alternating between these two techniques solves the majority of newspaper and magazine puzzles efficiently. But genuinely hard Sudokus can stump both methods simultaneously. A more powerful tool is needed.
§ 4Crook's Pencil-and-Paper Algorithm
James Crook, professor emeritus of Computer Science at Winthrop University, published a pencil-and-paper algorithm in 2009 capable of solving any Sudoku puzzle. It weaves together backtracking, candidate-checking, place-finding, and the concept of preemptive sets — a clever structure that eliminates candidates in bulk.
Definition — Mark-up
The _mark-up_of an empty cell is the set of digits that may legally occupy it, given the entries already present in that cell's row, column, and box.
A marked-up 3×3 box
2
9
5
4,7
3
1
8
4,7
6
The two peach cells can each only hold 4 or 7 — every other digit already appears elsewhere in this box. Their mark-ups are identical: { 4, 7 }.
We don't yet know which cell gets 4 and which gets 7 — but we know with certainty that 4 and 7 are confined to those two cells. That is a preemptive pair, and it is enough to eliminate 4 and 7 from all other cells sharing the same row, column, or box.
Definition — Preemptive Set
A preemptive set is a collection of m digits (2 ≤ m ≤ 8) together with m cells such that no digit outside the collection can occupy any of those cells.
Theorem — Occupancy Theorem
If a preemptive set lies entirely within a single row, column, or box, then no digit belonging to the set can appear outside the set in that row, column, or box.
The occupancy theorem is the key: once a preemptive set is found, its digits can be crossed out of the mark-ups of every other cell in the same unit. This often cascades — eliminations trigger placements, which reveal new preemptive sets, which enable further eliminations.
Crook's Algorithm
Apply candidate-checking and place-finding alternately until neither makes progress.
Mark up all remaining empty cells.
Search each row, column, and box for preemptive sets. Apply the occupancy theorem. Return to step 1 if mark-ups changed.
Check: solved? Condition violated? Neither? Continue to step 5.
Choose an empty cell; enter a digit from its mark-up. Assign a color to this choice; log it on a separate sheet.
Continue with preemptive sets using the current color. Stop when solved, condition violated, or a mark-up is empty.
If empty mark-up: the guess was wrong. Erase everything in this color. If mark-up is still non-empty, return to step 5. Otherwise, erase the previous color and repeat.
The color-coding system is how backtracking is managed on paper. Each speculative branch receives a different pen; an incorrect branch is erased completely. In practice, copying the board to a fresh sheet before each guess is more convenient than erasing.
§ 5Sudokus as Graphs
Graph theory was not invented for Sudoku — it predates the puzzle by centuries. Euler laid its foundations in 1735 with the Königsberg Bridge problem. Today, graph algorithms power GPS routing, power-grid design, and network flow optimization. Sudoku turns out to be a natural inhabitant of this ancient landscape.
Definition — Graph
A graph is a collection of points called vertices, together with lines connecting some pairs of them, called edges.
Encoding a Sudoku as a Graph
Assign one vertex to each of the 81 cells. Connect two vertices with an edge whenever their cells share a row, column, or box — that is, whenever the two cells cannot hold the same digit. Now assign a color to each digit 1–9. Filling in the Sudoku correctly is exactly equivalent to coloring the vertices of this graph so that no two adjacent vertices share a color. This is the graph coloring problem.
The power of this representation is the centuries of graph-theoretic knowledge it unlocks. In 2007, Herzberg and Murty developed a method — using chromatic polynomials — to count the number of valid colorings of a partially colored graph. Since a Sudoku puzzle is exactly that, their result immediately tells us how many solutions a given puzzle has, without any special Sudoku-specific analysis.
Famous Problems in Graph Theory
Interactive — Graph Coloring on a Sudoku
Select a color (= a digit), then click an empty cell. Adjacent cells — same row, column, or box — cannot share a color. Try to violate the rule and see what happens.
4
6
3
8
2
5
3
7
4
9
8
4
3
2
3
1
9
4
5
7
1
5
6
4
7
9
1
4
8
3
6
4
7
8
5
1
3
9
2
Choose a color above, then click an empty cell.
A solver who masters Crook's algorithm gains something more than solved puzzles: the certainty that no Sudoku can defeat them, provided they are willing to be systematic. But the richer reward is the view from outside the puzzle — the glimpse of combinatorics, algorithmic thinking, and graph theory that the humble 9×9 grid opens up. These are not niche mathematical curiosities. They are the foundations of modern computing.
Euler would have enjoyed this.
Sources & References
Cornell Mathematics Explorers' Club (2009) · The Mathematics of Sudoku · P. MeerkampFelgenhauer, B. & Jarvis, F. (2005) · Enumerating possible Sudoku gridsCrook, J. F. (2009) · A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles · Notices of the AMS
readers loved this