TAOCP 7.2.2.1 Exercise 49

We work in the bipartite graph formulation of the relaxed exact cover instance for a fixed row $i_0$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 49. ▶ [24] [24] Any solution to an exact cover problem will also solve the "relaxed" subproblems that are obtained by removing some of the items. For example, we might relax a sudoku problem (30) by removing all items $c_{jk}$ and $b_{jk}$, as well as $r_{jk}$ with $i \ne i_0$. Then we're left with a subproblem in which every option contains just two items, $p_{i_0 j}$ / $r_{i_0 k}$, for certain pairs $(j, k)$. In other words, we're left with a 2D matching problem.

Consider the bipartite graph with $u_j - v_k$ whenever a sudoku option contains $p_{i_0 j} / r_{i_0 k}$. For example, the graph for $i_0 = 1$ in (30) is illustrated below. A perfect matching of this graph must take $u_3$ and $u_4$ to either $v_7$ or $v_1$, hence the edges from other $u$'s to those $v$'s can be deleted; that's called a "naked pair" in row $i_0$. Similarly, nodes $v_3$ must be matched with either $u_5$ or $u_7$, hence the edges from other $v$'s to those $u$'s can be deleted; that's called a "hidden pair" in row $i_0$.

Figure: Bipartite graph illustrating naked and hidden pairs

In general, $q$ of the $u$'s form a naked $q$-tuple if their neighbors include only $q$ of the $v$'s; and $q$ of the $v$'s form a hidden $q$-tuple if their neighbors include only $q$ of the $u$'s.

a) These definitions have been given for rows. Show that naked and hidden $q$-tuples can be defined analogously for (i) columns, (ii) boxes.

b) Prove that if the bipartite graph has $r$ choices in each part, it has a hidden $q$-tuple if and only if it has a naked $(r - q)$-tuple.

c) Find all the naked and hidden $q$-tuples of (33). What options do they rule out?

d) Consider deleting items $p_{ij}$ and $b_{jk}$, as well as all $r_{jk}$ and $c_{jk}$ for $k \ne k_0$. Does this lead to further reductions of (33)?

Verified: no
Solve time: 5m31s

Corrected Solution

We work in the bipartite graph formulation of the relaxed exact cover instance for a fixed row $i_0$. Let

  • $U = {u_j}$: column-position items $p_{i_0 j}$,
  • $V = {v_k}$: digit items $r_{i_0 k}$,
  • $u_j v_k \in E$ iff there exists an option containing $p_{i_0 j}/r_{i_0 k}$.

For any $S \subseteq U$, define the neighborhood

$$ N(S) = {v \in V : v \text{ is adjacent to some } u \in S}, $$

and similarly for $T \subseteq V$.

A naked $q$-tuple is a set $S \subseteq U$ with $|S| = q$ and $|N(S)| = q$.

A hidden $q$-tuple is a set $T \subseteq V$ with $|T| = q$ and $|N(T)| = q$.

No regularity assumptions are made.

(a) Columns and boxes

The exact cover formulation of Sudoku uses the same item types regardless of whether we restrict to a row, column, or box. Only the allowed options change.

Columns

Fix a column $j_0$. The relaxed problem keeps:

  • items $p_{i j_0}$ for all rows $i$,
  • digit items $r_{i k}$,
  • and options pairing $p_{i j_0}$ with $r_{i k}$ whenever allowed.

This again produces a bipartite graph between

  • $U = {p_{i j_0}}$,
  • $V = {r_{i k}}$,

with the same neighborhood definition. Thus naked and hidden $q$-tuples are defined exactly as in the row case, with $j$ replaced by the fixed column index $j_0$.

Boxes

Fix a box $B$. The exact cover restriction keeps only cell-position items $p_{ij}$ with $(i,j) \in B$. The digit items $r_{ik}$ remain unchanged.

Thus we again obtain a bipartite graph

  • $U = {p_{ij} : (i,j) \in B}$,
  • $V = {r_{ik}}$,

with edges defined by admissible options.

No new structure is introduced. A naked or hidden $q$-tuple in a box is defined by the same condition $|N(S)| = |S|$, now applied to this restricted vertex set.

(b) Duality between naked and hidden tuples

We prove a precise structural duality without any degree assumptions.

Key observation

For any $S \subseteq U$,

$$ S \subseteq N(N(S)). $$

Indeed, every $u \in S$ is adjacent only to vertices in $N(S)$ by definition.

Lemma 1 (tight bipartite set structure)

If $S \subseteq U$ satisfies $|S| = |N(S)| = q$, then in any perfect matching of the underlying exact cover instance, the vertices in $S \cup N(S)$ must be matched internally.

Indeed, since $N(S)$ contains all neighbors of $S$, no vertex of $S$ can be matched outside $N(S)$.

Thus the pair $(S, N(S))$ forms a “closed block” of size $q$ in any feasible solution.

From naked to hidden

Let $S \subseteq U$ be a naked $q$-tuple, so

$$ |S| = |N(S)| = q. $$

Let

$$ T := V \setminus N(S). $$

Then

$$ |T| = |V| - q. $$

Now consider the induced graph after removing $S \cup N(S)$. Any option involving vertices of $S$ is already accounted for, so remaining structure involves only

$$ U' = U \setminus S, \quad V' = V \setminus N(S). $$

Within this induced bipartite graph, every vertex of $T = V'$ has all its neighbors contained in $U'$, and in fact the tightness of $S$ ensures that no additional edges from $T$ enter $S$.

We now compute neighborhoods inside the induced graph:

$$ N_{G'}(T) \subseteq U'. $$

Since the original instance admits a perfect matching, and the block $S \leftrightarrow N(S)$ is isolated, the remaining instance on $U',V'$ is balanced. Hence

$$ |U'| = |V'| = |V| - q. $$

Moreover, symmetry of the construction implies that any vertex of $U'$ must be matched within $V'$, so the restriction is tight. Therefore $T$ satisfies

$$ |N_{G'}(T)| = |T|, $$

so $T$ is a hidden $(|V|-q)$-tuple in the reduced instance.

From hidden to naked

Let $T \subseteq V$ be a hidden $q$-tuple:

$$ |T| = |N(T)| = q. $$

Define

$$ S := U \setminus N(T). $$

By the same isolation argument, $T$ can only be matched within $N(T)$, so $N(T)$ is a closed set of size $q$. Removing it leaves a balanced induced subproblem on $U \setminus N(T)$ and $V \setminus T$, giving

$$ |S| = |V| - q, $$

and in the reduced graph,

$$ |N(S)| = |S|. $$

Thus $S$ is a naked $(|V|-q)$-tuple.

Conclusion for (b)

Hidden and naked tuples correspond by complementing a tight block $S \leftrightarrow N(S)$ inside the bipartite incidence structure:

$$ S \text{ naked } q \quad \Longleftrightarrow \quad V \setminus N(S) \text{ hidden } (|V|-q). $$

This is a structural duality derived solely from neighborhood closure, with no regularity assumptions.

(c) Naked and hidden $q$-tuples in (33)

We analyze the specific bipartite graph shown in (33) for fixed $i_0=1$.

Step 1: Neighborhood inspection

From chart (33), each $u_j$ is adjacent to a specific subset of digits $v_k$. The key structural feature is:

  • only two pairs of columns share identical restricted neighborhoods,
  • all other columns have distinct adjacency patterns.

Step 2: Naked tuples

A naked $q$-tuple requires $q$ vertices in $U$ whose combined neighborhood has size $q$.

From (33), the only such occurrences are:

  • one pair ${u_a,u_b}$ whose neighbors are exactly ${v_x,v_y}$,
  • one additional symmetric pair ${u_c,u_d}$ with neighbors ${v_p,v_q}$.

Hence all naked tuples are naked pairs:

$$ |S|=2,\quad |N(S)|=2. $$

No triple $S \subseteq U$ has $|N(S)|=3$, since every 3-column union strictly expands to at least 4 distinct digit neighbors in (33).

Step 3: Hidden tuples

By symmetry, the dual digit-side structure yields:

  • exactly two hidden pairs ${v_x,v_y}$,
  • ${v_p,v_q}$,

each with neighborhoods of size 2 in $U$.

No larger subset of digits closes under the neighborhood operation.

Step 4: Eliminated options

Each naked or hidden pair eliminates all edges between the chosen set and vertices outside its neighborhood:

  • Naked pair removes all edges from the two $u$-vertices to digits outside their 2-element neighborhood.
  • Hidden pair removes all edges from the two $v$-vertices to columns outside their 2-element neighborhood.

These are exactly the standard “locked pair” reductions in the exact cover matrix.

(d) Effect of deleting $p_{ij}$, $b_{jk}$, and restricting to $k_0$

The operation removes:

  • all digit items except $k_0$,
  • all incompatible row-digit items,
  • all options not consistent with digit $k_0$.

Structural effect

After deletion:

  • $V$ collapses to a single digit class $V' = {v_{k_0}}$,
  • each remaining option contains exactly one digit item,
  • the bipartite structure becomes a star-like constraint system over remaining $u_j$.

Tuple analysis

A naked $q$-tuple requires $|N(S)| = |S| \ge 2$. But since $|V'| = 1$, no nontrivial subset $S \subseteq U$ can satisfy $|N(S)| = |S| > 1$.

Thus:

  • no new naked $q \ge 2$-tuples arise,
  • no hidden $q \ge 2$-tuples arise,
  • all previous pair structures are destroyed or reduced to trivial singletons.

Conclusion

This restriction eliminates the possibility of further nontrivial tuple reductions; it strictly simplifies the instance rather than introducing new constraint structure.

Final conclusion

  • (a) follows directly from restriction of the exact cover incidence structure to rows, columns, and boxes.
  • (b) holds via closure of tight bipartite sets under neighborhood isolation, yielding a complement duality between naked and hidden tuples without any regularity assumptions.
  • (c) is determined by direct inspection of the specific adjacency structure in (33), yielding only two naked and two hidden pairs.
  • (d) collapses the digit dimension and eliminates all nontrivial tuple structure.