A sudoku is defined by having exactly one solution. Take a completed grid and start removing digits: for a while the puzzle stays solvable in only one way, and at some point it tips into having several. The question of how few clues you can leave before that happens turned out to be surprisingly hard.
Puzzles with seventeen clues had been found — thousands of them. Nobody could find one with sixteen, and nobody could prove one did not exist.
How it was settled
In 2012, Gary McGuire, Bastian Tugemann and Gilles Civario at University College Dublin proved there is no 16-clue sudoku with a unique solution. The method was exhaustive search: check every possible way of placing sixteen clues and confirm that none produces a unique puzzle.
The number of arrangements is far too large to check directly, so the work went into reducing it — using symmetry to collapse equivalent grids, and a fast checker that could reject a candidate quickly. It still took roughly seven million core-hours.
The answer is therefore not a theorem in the elegant sense. It is a computation, verified by others repeating it.
Why uniqueness matters
Because a puzzle with two solutions is not a puzzle. Solving relies on being able to reason that a digit must go in a cell, and that reasoning is only valid if the answer is forced.
It also has a practical use: it is the best check that a grid has been typed in correctly. If a solver reports more than one solution for a puzzle from a newspaper, the puzzle is fine and a digit was misread.
How solvers work
The straightforward approach is backtracking: find an empty cell, try each legal digit, recurse, and undo when you reach a contradiction. It always works and can be very slow.
The improvement that matters is choosing which cell to fill. Going left to right treats every cell as equally good. Choosing the empty cell with the fewest legal candidates instead — the most constrained one — prunes the search enormously, because every choice you make eliminates most of what remains.
The difference is not marginal. A hard 17-clue grid that takes seconds left-to-right solves in well under a millisecond with the heuristic. It is the same algorithm; only the order changed.
Are some grids genuinely harder?
For a human, yes, and difficulty ratings usually reflect which solving techniques a grid requires — whether naked pairs are enough, or whether you need X-wings and colouring.
For a computer the picture is different. What makes a grid slow is how much guessing the search has to do before a contradiction appears, which correlates with human difficulty only loosely. A puzzle rated fiendish for a person can be trivial for a solver, and occasionally the reverse.
How many sudokus are there?
Completed grids: 6,670,903,752,021,072,936,960. Accounting for symmetries — rotations, reflections, relabelling digits — that reduces to 5,472,730,538 essentially different ones.
Both numbers were computed rather than derived, in 2005 and 2006. The count of actual puzzles is larger still, since each completed grid yields many valid clue arrangements.
Questions people ask
Is there a puzzle needing guessing? For a properly-set sudoku, no — a unique solution can always be reached by deduction, though the deduction may be well beyond what most people would attempt.
What is the hardest known sudoku? "Everest" and similar constructed grids are designed to defeat solving techniques rather than to be enjoyable. They are curiosities.
Does a symmetrical clue pattern mean anything? Only aesthetics. Newspaper puzzles are usually symmetrical because it looks deliberate, which constrains the setter without affecting difficulty.
Can a sudoku have no solution? Yes, if the given digits already contradict each other. That is a mis-set puzzle rather than a hard one.
The sudoku solver uses the most-constrained-cell search and reports whether the grid has exactly one solution, which is the quickest way to find a mistyped clue.