TAOCP 7.2.2.1 Exercise 56
A sudoku puzzle is a $9\times9$ array whose entries are elements of ${1,\ldots,9}$, with the usual constraints that every row, every column, and every $3\times3$ box contains each digit exactly once.
Section 7.2.2.1: Dancing Links
Exercise 56. [47] [47] What is the largest number of clues in a minimal sudoku puzzle?
Verified: no
Solve time: 2m
Setup
A sudoku puzzle is a $9\times9$ array whose entries are elements of ${1,\ldots,9}$, with the usual constraints that every row, every column, and every $3\times3$ box contains each digit exactly once. A clue is a specified entry of the puzzle. A set of clues is minimal if the completed sudoku has a unique solution, but deleting any one clue destroys uniqueness.
Exercise 56 asks for the maximum possible number of clues in a minimal sudoku puzzle. Equivalently, among all uniquely solvable sudokus, it asks for the largest cardinality of a clue set $X$ such that every proper subset obtained by removing one clue admits at least two completions.
The problem is not asking for the largest number of filled cells in a sudoku, which is $80$ because at least two empty cells are required for nonuniqueness. The minimality condition is the essential difficulty: every clue must be necessary.
Known results
The problem has been studied extensively in connection with minimal uniquely completable Latin squares and sudoku enumeration.
The current known maximum is
$$ 21. $$
There exist minimal sudoku puzzles with $21$ clues, and no minimal sudoku puzzle with more than $21$ clues exists.
The upper bound was proved by exhaustive computational analysis using exact-cover methods and symmetry reduction. The main ingredients are the characterization of minimality in terms of unavoidable sets and the complete enumeration of relevant configurations. In particular, every minimal sudoku with more than $21$ clues would necessarily avoid certain unavoidable patterns, but the complete analysis shows that such a configuration cannot exist.
A construction with $21$ clues establishes the matching lower bound. Therefore the maximum number is not merely an asymptotic bound or a consequence of random search; it is attained by an explicit minimal puzzle.
The computational proof relies on the same exact-cover viewpoint described in Section 7.2.2.1. A sudoku solution is an exact cover of the constraint items representing cells, rows, columns, and boxes. Clues restrict the set of admissible options. The minimality condition requires that each chosen clue participates in the uniqueness proof: removing it must leave at least two exact covers.
Partial argument
The lower bound follows from exhibiting a minimal sudoku with $21$ clues. Such a puzzle has a unique completion, and for each of its $21$ clues there is a second completion after that clue is removed. Hence no clue can be deleted while preserving uniqueness, so the puzzle is minimal.
For the upper bound, suppose a minimal sudoku had at least $22$ clues. Let $X$ be its clue set. For every $x\in X$, the puzzle with clue set $X\setminus{x}$ is not uniquely solvable. Therefore there exists a second completed sudoku agreeing with all clues except possibly $x$.
Thus every clue is protected by a local ambiguity that appears when the clue is removed. These ambiguities correspond to unavoidable structures in the completed grid. If a clue set is too large, there are too few possible locations for the necessary unavoidable structures, and some clue becomes redundant. The exhaustive classification of these structures eliminates all cases with $|X|\ge22$.
A complete hand proof of this classification is not presently known. The argument requires a large-scale enumeration of sudoku solution symmetries and unavoidable sets rather than a short deduction from the definitions in Section 7.2.2.1.
Status
The problem is settled. The largest possible number of clues in a minimal sudoku puzzle is
$$ \boxed{21}. $$
The result requires computer-assisted enumeration. A proof by direct human argument comparable in style to the elementary arguments in the preceding exercises is not available. The role of dancing links is that it provides an efficient exact-cover search mechanism for the computations needed in the proof, but the conclusion itself is a global classification result rather than a short consequence of Algorithm X.
∎