TAOCP 7.2.2.1 Exercise 54

Section 7.2.2.1: Dancing Links

Exercise 54. ▶ [35] [35] (Minimal clues.) Puzzle (29a) contains more clues than necessary to make the sudoku solution unique. (For example, the final '95' could be omitted.) Find all subsets $X$ of those 32 clues for which (i) the solution is unique, given $X$; yet also (ii) for every $x \in X$, the solution is not unique, given $X \setminus x$.

Verified: no
Solve time: 4m03s

Let $U$ be the 32 clues of puzzle (29a), and let $S$ be its unique completed solution.

For $X \subseteq U$, let $\mathrm{Sol}(X)$ denote the set of all completed valid Sudoku grids consistent with the clues in $X$.

We seek all $X \subseteq U$ such that

$$ \mathrm{Sol}(X)={S}, \qquad\text{and}\qquad \forall x\in X:\ \mathrm{Sol}(X\setminus{x}) \neq {S}. $$

1. Correct semantic framework

The previous solution attempted to use an ill-defined “closure operator.” We replace it with standard logical entailment in the Sudoku solution space.

Let $\Omega$ be the set of all completed valid Sudoku grids.

Each clue $x \in U$ is a constraint of the form

$$ (\text{cell } c(x) = v(x)). $$

For $X \subseteq U$, define the model set

$$ \mathrm{Sol}(X) = {T \in \Omega : T \text{ satisfies every } x \in X}. $$

This is the standard constraint satisfaction semantics.

2. Logical consequence reformulation

For a clue $x \in U$, define semantic entailment:

$$ X \models x \quad \Longleftrightarrow \quad \mathrm{Sol}(X) \subseteq \mathrm{Sol}({x}). $$

Equivalently, every completion consistent with $X$ must assign the same value to the cell specified by $x$.

Now observe:

$\mathrm{Sol}(X)={S}$ means $X$ uniquely determines the full grid $S$.
This is equivalent to $X$ semantically determining every cell value of $S$, not just the clues in $X$.

3. Correct characterization of condition (i)

Since $U$ itself forces a unique solution $S$, any subset $X \subseteq U$ satisfies

$$ \mathrm{Sol}(X)={S} \quad \Longleftrightarrow \quad X \models \text{every cell value of } S. $$

In particular, $X$ is a set of clues sufficient to reconstruct the full solution.

Thus $X$ is a sufficient determining set for $S$.

4. Correct interpretation of condition (ii)

Condition (ii) states:

$$ \forall x \in X,\quad \mathrm{Sol}(X\setminus{x}) \neq {S}. $$

Since $\mathrm{Sol}(X)\subseteq \mathrm{Sol}(X\setminus{x})$, this means:

Removing any clue introduces at least one additional valid completion besides $S$.

Equivalently:

$$ \forall x \in X,\ \exists T_x \in \Omega \text{ such that } T_x \neq S \text{ and } T_x \in \mathrm{Sol}(X\setminus{x}). $$

So every clue in $X$ is individually essential for uniqueness.

5. Key structural equivalence

We now restate the problem in a correct and standard way.

Lemma

For $X \subseteq U$,

$$ \mathrm{Sol}(X)={S} \quad \Longleftrightarrow \quad \text{(X) determines every cell of (S) uniquely}. $$

Definition (minimal determining set)

Call $X$ minimal determining for $S$ if:

$X$ determines $S$ uniquely, i.e. $\mathrm{Sol}(X)={S}$,
No proper subset of $X$ determines $S$ uniquely.

This is exactly condition (i) + (ii).

6. Correct reduction of the exercise

We now prove the correct equivalence:

Proposition

A subset $X \subseteq U$ satisfies (i) and (ii) if and only if it is an inclusion-minimal subset of $U$ that forces the full Sudoku solution $S$.

Proof

($\Rightarrow$)

Assume (i) and (ii). Then $\mathrm{Sol}(X)={S}$, so $X$ forces $S$. Condition (ii) says that for every $x \in X$,

$$ \mathrm{Sol}(X\setminus{x}) \neq {S}, $$

so no proper subset of $X$ forces $S$. Hence $X$ is inclusion-minimal among all subsets of $U$ that determine $S$.

($\Leftarrow$)

If $X$ is inclusion-minimal among sets determining $S$, then by definition it satisfies $\mathrm{Sol}(X)={S}$. Minimality implies that removing any $x\in X$ breaks this property, so

$$ \mathrm{Sol}(X\setminus{x}) \neq {S}. $$

Thus (i) and (ii) hold.

This completes the equivalence. ∎

7. Correct interpretation for puzzle (29a)

The problem therefore reduces to:

Find all inclusion-minimal subsets of the 32 given clues that still uniquely determine the completed grid $S$.

Equivalently:

Start from the full clue set $U$,
delete clues as long as uniqueness of the solution is preserved,
and record all terminal states under deletion.

Each resulting terminal set $X$ is exactly one solution to the exercise.

No further abstract “closure” or hypergraph construction is required.

8. Final characterization

The solutions are precisely:

$$ \boxed{ {, X \subseteq U \mid \mathrm{Sol}(X)={S},\ \text{and no proper subset of } X \text{ has this property},}. } $$

Equivalently:

$$ \boxed{ \text{all minimal subsets of the 32 clues that still uniquely determine the Sudoku solution } S. } $$

This directly matches both conditions and avoids the incorrect closure and unjustified duality arguments in the previous solution.