TAOCP 7.2.2.1 Exercise 49

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$.

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: 2m19s

---

Solution

Parts (a) and (b) can be proved from the definitions given in the statement. Parts (c) and (d) require the actual data in chart (33), because the required tuples and reductions depend on the particular sudoku exact-cover instance displayed there. The chart is not included in the supplied section context, so those parts cannot be determined uniquely from the information available.

For part (a), the definitions of naked and hidden $q$-tuples depend only on the bipartite relation between two classes of choices. In a sudoku row, the two classes are the cells in that row and the possible values for those cells. In a column, the two classes are the cells in that column and the possible values for those cells. In a box, the two classes are the cells in that box and the possible values for those cells.

For a column, construct the bipartite graph whose left vertices are the cells in the chosen column and whose right vertices are the possible values that may occur in those cells. A set of $q$ left vertices is a naked $q$-tuple when its neighbors contain only $q$ right vertices. A set of $q$ right vertices is a hidden $q$-tuple when its neighbors contain only $q$ left vertices.

For a box, construct the bipartite graph whose left vertices are the cells in the chosen box and whose right vertices are the possible values that may occur in those cells. The same two definitions apply without modification. Thus the row definitions extend directly to columns and boxes.

For part (b), suppose the bipartite graph has $r$ vertices in each part. Let $U$ and $V$ be the two parts, with $|U|=|V|=r$.

Assume first that the graph has a hidden $q$-tuple. Then there is a set $T\subseteq V$ with $|T|=q$ whose neighborhood satisfies

$N(T)=S,\qquad |S|=q.$

Every vertex of $T$ is adjacent only to vertices of $S$. Therefore every vertex of $U\setminus S$ has no neighbor in $T$. Hence the neighbors of the $r-q$ vertices in $U\setminus S$ are contained in

$V\setminus T.$

Because

$|U\setminus S|=r-q,\qquad |V\setminus T|=r-q,$

the set $U\setminus S$ is a naked $(r-q)$-tuple. Thus a hidden $q$-tuple implies a naked $(r-q)$-tuple.

Conversely, assume that the graph has a naked $(r-q)$-tuple. Then there exists a set $S\subseteq U$ with

$|S|=r-q$

whose neighborhood satisfies

$N(S)=T,\qquad |T|=r-q.$

Every vertex of $S$ is adjacent only to vertices of $T$. Therefore the remaining vertices

$U\setminus S$

have no neighbors in $T$. Since

$|U\setminus S|=q,\qquad |V\setminus T|=q,$

the vertices in $V\setminus T$ can be adjacent only to the vertices in $U\setminus S$. Hence

$N(V\setminus T)=U\setminus S,$

and $V\setminus T$ is a hidden $q$-tuple.

Therefore the graph has a hidden $q$-tuple if and only if it has a naked $(r-q)$-tuple.

This completes the proof. ∎

For parts (c) and (d), the missing chart (33) is necessary. The complete solution requires the candidate sets represented by that chart in order to construct the bipartite graphs, enumerate all naked and hidden $q$-tuples, identify the ruled-out options, and test the further reductions obtained after deleting the specified exact-cover items.