Most people meet sudoku as a finished product: a grid with some digits already filled in and a difficulty label at the top. Few stop to ask where that grid came from. Who decided which cells to reveal? Why does every decent puzzle have exactly one answer? Why can a puzzle labelled “easy” stall you for twenty minutes while a sparse-looking one falls apart quickly? Behind these questions is a surprisingly deep piece of mathematics, including a famous computer proof that took a year of supercomputer time. This article walks through it in plain language and then turns it into practical advice for choosing and solving puzzles.
How many sudoku grids exist?
Start with completed grids: 9×9 tables in which every row, every column and every 3×3 box contains the digits 1 to 9 exactly once. Bertram Felgenhauer and Frazer Jarvis counted them by computer and published the result in Mathematical Spectrum in 2006. There are exactly 6,670,903,752,021,072,936,960 of them, roughly 6.67 × 1021.
Many of these grids are really the same grid in disguise. You can relabel the digits (turn every 1 into a 7 and so on), swap rows inside a band of three, swap whole bands, do the same with columns, or transpose the grid. Ed Russell and Frazer Jarvis counted the grids that remain genuinely distinct after all these transformations, using Burnside’s lemma from group theory. According to McGuire and colleagues, the calculation itself took about one second of computer time. The answer is 5,472,730,538 “essentially different” grids.
| What is counted | Number | Source |
|---|---|---|
| Completed 4×4 grids (2×2 boxes) | 288 | McGuire, Tugemann & Civario |
| Completed 9×9 grids | 6,670,903,752,021,072,936,960 | Felgenhauer & Jarvis (2006) |
| Essentially different 9×9 grids | 5,472,730,538 | Russell & Jarvis (2007) |
The 17-clue minimum: why 16 is impossible
A puzzle is a completed grid with most digits erased. If you erase too many, the remaining clues no longer pin down a single answer. So how few clues can a proper puzzle have? Enthusiasts found tens of thousands of puzzles with 17 clues. Gordon Royle collected them, and his list eventually held 49,151 different 17-clue puzzles. Nobody ever found a valid 16-clue one, but “nobody found one” is not a proof.
The proof came from Gary McGuire, Bastian Tugemann and Gilles Civario. Their preprint appeared in January 2012, and the peer-reviewed version was published in Experimental Mathematics in 2014. Their approach was simple to state and enormously hard to carry out: search every possible solution grid, one by one, for a hidden 16-clue puzzle.
The key idea is the unavoidable set. Imagine four cells in two rows, two columns and two boxes holding the pattern 3-8 / 8-3. If you swap the 3s and 8s in those four cells, you get another perfectly valid grid. So if none of those four cells is given as a clue, the puzzle has two solutions. Every completed grid contains many such sets, some small and some large, and any proper puzzle must place at least one clue in each of them. Mathematically this is a hitting set problem, and the team wrote a very fast program, called checker, that lists every 16-cell hitting set of a grid and tests whether any of them gives a unique solution.
They then ran it on all 5,472,730,538 essentially different grids. The search ran from January to December 2011 on the Stokes cluster at the Irish Centre for High-End Computing. It used about 7.1 million core hours, averaging around 3.6 seconds per grid. The authors note that their original 2006 version of the program would have needed an estimated 300,000 processor-years. Better algorithms brought that down to about 800. No 16-clue puzzle turned up, so 17 is the true minimum.
There is also a simpler fact with a one-line proof: a proper puzzle must show at least eight of the nine digits. If two digits, say 4 and 6, were both missing from the clues, you could swap every 4 and 6 in the solution and get a second valid answer.
Why one solution matters (and why you never need to guess)
As Peter Norvig puts it in his well-known essay on sudoku solving: “Puzzles that appear in books and newspapers always have one unique solution.” This is more than a convention. Uniqueness is what makes sudoku a puzzle of logic rather than a puzzle of luck.
When a puzzle has exactly one solution, every cell is forced by the clues. That means a chain of reasoning exists from the starting position to the end, even if it is long and hard to find. If a puzzle had two solutions, you would eventually reach a point where both 2 and 5 fit in a cell and nothing in the grid could tell you which one to choose. You would have to guess, and half the time the “correct” answer printed in the back of the book would disagree with your perfectly logical result.
Norvig’s essay also shows why uniqueness must be checked on purpose. His simple random generator fills cells until at least 17 squares and 8 different digits are present. It is fast, but he points out that the result is not guaranteed to have a unique solution: some of his random puzzles have several solutions and a small share have none at all.
Symmetry and hand-made puzzles
The puzzle we now call sudoku first appeared in the United States. It is generally credited to Howard Garns and was published by Dell Magazines in 1979 under the name Number Place. The Japanese publisher Nikoli says on its website that it found the puzzle in an American magazine and introduced it to Japanese readers in 1984, later shortening the long Japanese title to “Sudoku”. According to Nikoli, the puzzle was slow to catch on until 1986, when the editors added a rule that the clues must be arranged in a symmetrical pattern. After that it became a hit.
The most common pattern is 180-degree rotational symmetry. If you turn the grid upside down, the clue cells land on clue cells. This has no effect on the logic; it is purely aesthetic. It also has a small cost: the fewest clues in a puzzle with this symmetry is believed to be 18, not 17.
Nikoli still makes its puzzles by hand. On its page explaining why, chief editor Nobuhiko Kanamoto says: “Good Sudoku authors are always considering a solver’s feelings.” A human setter can plan a satisfying route: a gentle opening, a clever middle step and a clean finish. A computer can produce endless valid puzzles, but whether they have that sense of design depends on how carefully they are filtered.
How computer generators usually work
Most sudoku sites, apps and books rely on generators. The details vary, but the usual method looks like this:
- Build a full grid. A randomized backtracking solver fills an empty board, which produces a random valid solution.
- Remove clues. Cells are erased one at a time (or in symmetric pairs if symmetry is wanted).
- Check uniqueness after each removal. A solver counts solutions and stops as soon as it finds two. If more than one exists, the last clue goes back.
- Grade the result. A second solver that imitates human techniques works through the puzzle, from easy steps to hard ones, and records the hardest technique needed.
The puzzles on Ozerlyn Games follow these principles: every puzzle has a unique solution and is assigned to a difficulty level, so it can be solved by logic alone.
Difficulty comes from technique, not from clue count
It is tempting to assume that fewer clues means a harder puzzle. As a rough rule there is some truth in it, but it is unreliable. In a 2012 study in Scientific Reports, María Ercsey-Ravasz and Zoltán Toroczkai measured puzzle hardness with a mathematical model and found that their tested 17- and 18-clue puzzles were easier than the hardest puzzles with 21 or 22 clues. Hardness, they concluded, depends on where the clues are placed, not only on how many there are.
Here is a comparison in words. Puzzle A has only 24 clues, but they are spread so that, at every stage, some digit has only one possible place in a row, column or box. You just keep finding hidden singles until the grid is full. Puzzle B has 30 clues, yet after a dozen easy placements every remaining cell has two or three candidates and no single is left. To continue you need an X-Wing or a chain. Puzzle A is easy and Puzzle B is hard, despite the clue counts.
That is why serious rating systems measure the techniques required. The best-known is the Sudoku Explainer (SE) rating, which scores a puzzle by the hardest step needed to solve it: singles score low, pairs and X-Wings higher, and chains and forcing nets higher still. Our article What is the sudoku SE rating? explains the scale in detail, and the SE rating calculator lets you score any puzzle yourself.
What this means for you as a player
- Choose puzzles by rating, not by how empty they look. A sparse grid is not necessarily hard, and a busy one is not necessarily easy.
- If an “easy” puzzle feels hard, you are probably looking only for naked singles (cells with one candidate). Easy puzzles often depend on hidden singles instead: ask “where can the 7 go in this box?” rather than “what can go in this cell?”
- If you feel you have to guess, you have missed something. With a unique solution there is always a logical next step. Re-check your pencil marks before trying anything risky.
- Uniqueness is a tool. Advanced players use the fact that a puzzle has one solution to rule out patterns like the 3-8 / 8-3 rectangle above. That is the idea behind the “unique rectangle” technique.
To put this into practice, play a puzzle at your level on our online sudoku page, or print a few from printable sudoku and solve them with a pencil. Pay attention to the hardest step in each one.
Sources
- Gary McGuire, Bastian Tugemann, Gilles Civario: There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration, Experimental Mathematics 23(2), 2014, pp. 190–217.
- The same paper as a free preprint: arXiv:1201.0749 (includes the grid counts, Royle’s 49,151-puzzle list and the computing details).
- Bertram Felgenhauer, Frazer Jarvis: Mathematics of Sudoku I, Mathematical Spectrum 39(1), 2006. Summary of the method: Cornell University, “Counting Sudoku solutions”.
- Ed Russell, Frazer Jarvis: Mathematics of Sudoku II, Mathematical Spectrum 39(2), 2007. Overview: Mathematics of Sudoku (Wikipedia).
- María Ercsey-Ravasz, Zoltán Toroczkai: The Chaos Within Sudoku, Scientific Reports 2, 725, 2012.
- Peter Norvig: Solving Every Sudoku Puzzle.
- Nikoli: Sudoku (history of the puzzle) and Why hand made?
- Sudoku (Wikipedia): history, Howard Garns and Dell’s Number Place.