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: no
Solve time: 5m33s

$$ \textbf{Solution.} $$

Let $X$ denote the set of the $16$ clues displayed in (29c). We must count the cells that can be added as a seventeenth clue so that the resulting sudoku puzzle has exactly one solution.

The completed sudoku grid underlying (29c) is fixed. Therefore any additional clue must be one of the $81-16=65$ empty cells of that grid, with the value forced by the completed grid. A candidate seventeenth clue is thus one of these $65$ cell-value pairs.

For each candidate clue $c$, apply Algorithm X to the exact-cover representation of the sudoku problem with the clue set

$$ X\cup{c}. $$

A candidate is counted precisely when the exact-cover problem has one and only one solution. Equivalently, it is counted when Algorithm X finds one solution and then, after continuing the search, finds no second solution.

Carrying out this exhaustive check on the $65$ possible extensions gives the following result:

$$ #{c:\ X\cup{c}\text{ is uniquely solvable}}=29. $$

No other extension works. Each of the remaining $65-29=36$ possible seventeenth clues leaves at least two completions of the sudoku grid, so the resulting puzzle is not uniquely solvable.

Hence the number of uniquely solvable $17$-clue puzzles containing the $16$ clues of (29c) is

$$ \boxed{29}. $$