TAOCP 7.2.2.1 Exercise 50

Exercise 50. [20] [20] How many uniquely solvable 17-clue puzzles contain the 16 clues of (29c)?

Verified: yes
Solve time: 1m05s

Solution

Let $P$ be the 16-clue Sudoku instance (29c), and let $S$ denote its unique completed grid. By assumption in (29c), every clue in $P$ agrees with $S$, and $S$ is the only solution satisfying $P$.

A 17-clue puzzle containing $P$ is obtained by adding one additional clue, which is a single assignment of a value to a cell. Let this additional clue be $(i,j) \mapsto v$.

If the added clue is consistent with $S$, then it must satisfy $S_{ij} = v$. In this case, every solution of the augmented puzzle must still satisfy all constraints of $P$, hence must equal $S$ by uniqueness of $P$. Therefore the augmented puzzle remains uniquely solvable.

If the added clue is not consistent with $S$, then it contradicts the unique solution of $P$, so the resulting instance has no solution and is not a valid uniquely solvable puzzle.

Hence the valid 17-clue puzzles containing $P$ are in bijection with the empty cells of $P$, since each empty cell $(i,j)$ admits exactly one value $S_{ij}$ that can be added as a clue.

The number of empty cells in a Sudoku grid is $81 - 16 = 65$. Therefore there are exactly $65$ choices for the additional clue, and each produces a uniquely solvable 17-clue puzzle containing (29c).

Thus the required number is

$\boxed{65}.$

This completes the proof. ∎