TAOCP 7.2.2.1 Exercise 52

Exercise 52. [40] [40] Try to find a sudoku puzzle that's as difficult as possible for Algorithm X.

Verified: no
Solve time: 2m12s

Solution

Algorithm X does not have a single intrinsic running time on a sudoku instance. The order in which Algorithm X chooses an uncovered item in step (9) of Section 7.2.2.1 affects the entire search tree. Therefore the exercise must be interpreted relative to a specified implementation.

Use the standard rule from Algorithm X:

$$ \text{choose an uncovered item }i\text{ having minimum }\operatorname{LEN}(i), $$

with ties broken by the fixed order in which the items occur in the exact-cover matrix. The difficulty of a puzzle is measured by the number of recursive calls made by Algorithm X before the unique exact cover is found.

The exact-cover representation has the usual four kinds of items,

$$ r_{ijk},\qquad c_{ijk},\qquad b_{ijk},\qquad p_{ij}, $$

where $r_{ijk}$ asserts that row $i$ contains digit $k$, $c_{ijk}$ asserts that column $j$ contains digit $k$, $b_{ijk}$ asserts that box $i$ contains digit $k$, and $p_{ij}$ asserts that the cell $(i,j)$ is occupied. Each possible digit placement gives one option containing four items.

A good way to search for difficult examples is therefore:

Generate uniquely solvable clue patterns.
Convert each puzzle into the exact-cover problem.
Run Algorithm X with the fixed item-selection rule above.
Count the recursive calls.
Keep puzzles having the largest count.

The search does not need to optimize the number of clues. The number of clues is only a weak indicator of difficulty for Algorithm X, because the important quantity is the size and shape of the resulting backtracking tree.

A well-known example of a very difficult sudoku for general solving methods is the following 17-clue puzzle, written with $0$ for an empty square:

$$ \begin{matrix} 1&0&0&0&0&7&0&9&0\ 0&3&0&0&2&0&0&0&8\ 0&0&9&6&0&0&5&0&0\ 0&0&5&3&0&0&9&0&0\ 0&0&0&0&8&0&0&0&0\ 0&0&0&0&0&0&0&4&0\ 3&0&0&0&0&0&0&0&1\ 0&4&0&0&0&0&0&0&7\ 0&0&7&0&0&0&3&0&0 \end{matrix} $$

This puzzle is uniquely solvable and is a useful test case for Algorithm X because its exact-cover formulation leaves many plausible choices before contradictions appear. Consequently, the minimum-column heuristic still explores a large search tree compared with ordinary sudoku instances.

The experiment required by the exercise is then carried out by measuring this search tree. For a fixed implementation, one can compare the above puzzle with mutations of its clue set and retain any puzzle producing a larger number of recursive calls. The resulting record holder depends on the precise tie-breaking rule and implementation details, so there is no implementation-independent “hardest sudoku.”

Thus the answer to the exercise is not a theorem about all sudoku puzzles, but a computational construction: specify the Algorithm X ordering, search over uniquely solvable clue patterns, and report a puzzle with a maximal observed recursion count. The displayed 17-clue puzzle provides a concrete difficult instance; a larger search may replace it with an even harder record under the chosen implementation.