The Mathematics of Sudoku

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?

§ 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.

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.

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³¹.

Product of all 81 entries ≈ 1.5 × 10³¹

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.

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.

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.

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.

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.

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.

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

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.