Why a Good Sudoku Has Exactly One Solution
What a unique solution means in sudoku, why logic-only solving depends on it, the 17-clue proof of 2012, and how puzzle makers check that a grid has one answer.
A good sudoku has exactly one solution because that is what makes it a logic puzzle. When only one completed grid fits the clues, the digit in every empty square can be proved from the clues, so the whole grid can be worked out step by step. With two solutions, some squares can never be proved and you have to guess. On a 9x9 grid, a unique solution needs at least 17 clues, a result proved in 2012.
This post is for solvers of any level who want to know why the one-solution rule exists, how much it takes to guarantee it, and how puzzle makers check it.
What "one solution" means in sudoku
In sudoku, a unique solution means there is exactly one way to fill every empty square so that each row, column and box holds each digit once. Such a grid is called a proper puzzle. The mathematicians who settled the 17-clue question put it plainly: "it is always understood that any proper (valid) sudoku puzzle must have only one completion" (McGuire, Tugemann and Civario).
Two related terms are worth knowing:
- Proper: the clues allow exactly one completed grid. Not zero (a broken puzzle) and not two or more (an ambiguous one).
- Minimal: a proper puzzle in which every clue is needed. Remove any one of them and a second solution appears.
A proper puzzle does not have to be minimal. A setter may leave in extra clues to make a puzzle easier or to keep a symmetrical pattern.
A sudoku with two solutions, and why it happens
The easiest way to see the problem is a 4x4 sudoku (digits 1 to 4, boxes of 2x2) with four squares left open.
Rows 1 and 3 each need a 1 and a 2. Columns 1 and 2 each need a 1 and a 2. Both arrangements work:
| Row 1, columns 1 and 2 | Row 3, columns 1 and 2 | |
|---|---|---|
| Solution A | 1, 2 | 2, 1 |
| Solution B | 2, 1 | 1, 2 |
The four open squares sit in two rows, two columns and two boxes, and hold only two digits. Swapping those two digits keeps every row, column and box valid, so the clues cannot tell the two grids apart. Sudoku solvers call this shape a deadly pattern; mathematicians call a set of squares like it an unavoidable set, because any proper puzzle must give at least one clue inside it. Add a single clue there, say a 1 in row 1, column 1, and only Solution A remains.
The same thing happens on a 9x9 grid. The 17-clue paper points out that in some completed grids, removing just four digits in this pattern leaves a 77-clue puzzle with two solutions. Many clues do not guarantee uniqueness; the right clues do.
Why logic-only solving depends on a unique solution
Uniqueness is what makes logic-only solving possible at all. A sound deduction, such as "this row needs a 5 and only this square can take it", is true in every grid that fits the clues. So logic can only ever prove digits that are the same in every solution.
If a puzzle has two solutions, the squares where they differ can never be proved. In the 4x4 example, nothing about the clues says whether row 1, column 1 is a 1 or a 2. A solver who has placed every provable digit reaches a point where no move can be justified, and the only way forward is a guess. Even then, either choice gives a valid grid, which makes the "solve" feel empty.
With one solution the picture changes. Each empty square has exactly one digit in every grid that fits the clues, so in principle each square can be proved. Whether a human can find the proof easily is a separate question, and it is what difficulty is about: an Easy puzzle needs only singles, an Expert one may need X-Wing or a chain. The sudoku strategies guide sets out those techniques in order.
How many clues does a sudoku need?
There is no clue count that makes a sudoku unique by itself; it depends on where the clues sit. But there are firm limits at both ends.
At least 8 different digits. Suppose the clues contain no 7s and no 9s at all. Take any solution and swap every 7 with every 9. Each row, column and box still holds 1 to 9 once, and every clue is unchanged, so this is a second solution. A proper 9x9 puzzle therefore has to show at least eight of the nine digits among its clues. This is the simple argument for why seven clues can never be enough, and the 17-clue paper uses it too.
At least 17 clues. The real minimum is far higher, as the next section explains.
No safe upper count. As the 4x4 example shows, a grid can be almost full and still ambiguous if the gaps form an unavoidable set.
For comparison, the 17-clue paper notes that newspapers and magazines usually give around 25 clues, and that Nikoli, the Japanese publisher that named sudoku, never prints one with more than 32. The number of clues says little about difficulty. A 30-clue puzzle can be hard and a 24-clue puzzle easy, because difficulty depends on which techniques the next step needs.
The 17-clue proof: no 16-clue sudoku exists
The smallest number of clues a 9x9 sudoku can have and still have one solution is 17. For years this was a strong suspicion: puzzle fans had collected about 50,000 different 17-clue puzzles, most of them found by the University of Western Australia mathematician Gordon Royle, and nobody had ever found a proper one with 16.
Gary McGuire of University College Dublin, with Bastian Tugemann and Gilles Civario, turned the suspicion into a proof. Their paper, posted on 1 January 2012 and published in Experimental Mathematics in 2014, describes the method (arXiv):
- Cut the work down. There are about 6.67 x 10^21 completed 9x9 grids, but many are just relabellings, rotations or reshufflings of others. Up to those symmetries there are 5,472,730,538 essentially different grids, and a 16-clue puzzle in one would mean a 16-clue puzzle in all its relatives. So each of those 5.47 billion grids needs checking only once.
- Find the unavoidable sets in each grid. Every proper puzzle must put at least one clue in each unavoidable set, like the four squares in the 4x4 example.
- List every way 16 clues could hit all of those sets. This is a "hitting set" problem, and their program, called checker, enumerated the candidates.
- Test each candidate to see whether it really has one solution.
The search ran from January to December 2011 on the Stokes machine at the Irish Centre for High-End Computing and took about 7.1 million core hours, roughly 800 processor-years. It found no 16-clue puzzle with a unique solution. If one had existed, the method would have found it.
Smaller sudokus have their own minimums, listed in the same paper:
| Grid | Box shape | Completed grids | Fewest clues |
|---|---|---|---|
| 4x4 | 2x2 | 288 | 4 |
| 6x6 | 2x3 | 28,200,960 | 8 |
| 8x8 | 2x4 | 29,136,487,207,403,520 | 14 |
| 9x9 | 3x3 | 6,670,903,752,021,072,936,960 | 17 |
The 6x6 grid, with its 8-clue minimum, has its own guide.
How puzzle makers check that a sudoku has one solution
Puzzle makers check uniqueness with a solver program that counts solutions. The program does not need to find them all: it searches until it finds a second solution and then stops, because two is enough to reject the puzzle. A puzzle passes only when the search ends having found exactly one.
A common way to make a sudoku goes like this:
- Start from a completed, valid grid.
- Remove a clue.
- Run the solver. If the puzzle still has one solution, keep the removal. If a second solution appears, put the clue back.
- Repeat until the puzzle has the number of clues you want, or until no clue can go.
- Grade the result by solving it the way a person would, simplest technique first, and note the hardest technique it needed.
The last step matters as much as the uniqueness check. A puzzle with one solution can still need a technique far beyond a beginner, so a fair Easy puzzle is one that is both unique and solvable with simple steps. Puzzle Picnic does both checks: the app makes each puzzle from a seed, a solver checks it has exactly one solution, and the difficulty depends on which techniques it needs. The full process is in how a puzzle is made from a seed, and what "logic-only" means in practice is in no guessing required.
Using uniqueness as a solving technique
Because a proper sudoku has only one solution, experienced solvers sometimes use that fact as a clue in its own right. The best-known example is the Unique Rectangle.
Picture four squares in two rows, two columns and two boxes, three of which can only be 4 or 7, with the fourth holding 4, 7 and something else. If the fourth square were also just 4 or 7, the four squares would form a deadly pattern, and the puzzle would have two solutions. Since the puzzle has one, the fourth square cannot be 4 or 7, and you can remove both from its notes.
As Andrew Stuart's SudokuWiki warns, this only works if your source guarantees one solution. In a puzzle that might be ambiguous, the deduction is unsafe. It is also optional: Puzzle Picnic's grading solver does not use uniqueness tricks at all, so every sudoku in the app can be finished without one.
Frequently asked questions
Can a sudoku have more than one solution?
Yes, a badly made one can. If the clues leave a pattern of squares whose digits can be swapped, such as four squares in two rows, two columns and two boxes holding the same two digits, the grid has two or more solutions. A proper sudoku, the kind newspapers and good apps publish, has exactly one.
What is the minimum number of clues in a sudoku?
A 9x9 sudoku with a unique solution needs at least 17 clues. Gary McGuire, Bastian Tugemann and Gilles Civario proved in 2012 that no 16-clue sudoku has a unique solution, by an exhaustive computer search. For a 6x6 sudoku the minimum is 8.
Does a sudoku with fewer clues mean a harder puzzle?
Not necessarily. Difficulty depends on which techniques the solve needs, not on the clue count. A sparse grid can fall to singles and a fuller one can need X-Wing.
What happens if I guess in a sudoku with one solution?
A guess can work, but it can also lead you far down a wrong path before a contradiction shows up, and then you have to undo every move since. Because a proper sudoku always has a provable next step, it is usually faster to look for that step. The how to play sudoku guide has a routine for when you feel stuck.
Where to go next
If you want to put the one-solution idea to work, the sudoku strategies guide shows the techniques that prove each digit, from singles to chains. If you are curious how history led to the 17-clue question, read the history of sudoku. You can also play a proper sudoku now on the Puzzle Picnic sudoku page.