TAOCP 7.2.2.1 Exercise 43
Let the Sudoku be of order $n^2$.
Section 7.2.2.1: Dancing Links
Exercise 43. [M30] [M30] Give formulas for the entries $a_{ij}$, $b_{ij}$, $c_{ij}$ of the sudoku squares in (28).
Verified: no
Solve time: 3m10s
Let the Sudoku be of order $n^2$. The candidate set is indexed by triples
$$ (i,j,k)\in{1,\dots,n^2}^3, $$
meaning “place digit $k$ in cell $(i,j)$”.
We construct the three incidence matrices exactly as in the standard TAOCP exact-cover formulation: each matrix corresponds to a distinct family of constraints, and each has its own column index set.
1. Cell constraint matrix $a_{ij}$
Columns are indexed by cell positions $(p,q)$. The constraint is: each cell contains exactly one digit.
A candidate $(i,j,k)$ satisfies the column $(p,q)$ exactly when it occupies that cell, hence
$$ a_{(i,j,k),(p,q)}=\delta_{i,p},\delta_{j,q}. $$
This is correct and complete: each candidate activates exactly one cell column.
2. Row–digit constraint matrix $b_{ij}$
Columns are indexed by pairs $(p,r)$, meaning “row $p$ contains digit $r$”.
A candidate $(i,j,k)$ contributes to this constraint exactly when it uses row $i$ and digit $k$, independently of the column $j$. Thus
$$ b_{(i,j,k),(p,r)}=\delta_{i,p},\delta_{k,r}. $$
This is also correct: each row–digit constraint column collects all placements of digit $r$ in row $p$.
3. Column–digit constraint matrix $c_{ij}$
This matrix enforces: each digit $k$ appears exactly once in each column $j$.
Columns are indexed by pairs $(q,r)$, meaning “column $q$ contains digit $r$”.
A candidate $(i,j,k)$ satisfies this constraint exactly when it lies in column $q$ and uses digit $r$. Therefore
$$ c_{(i,j,k),(q,r)}=\delta_{j,q},\delta_{k,r}. $$
No additional block term is included here, because block constraints are not part of this family in (28).
4. Block–digit constraint matrix $d_{ij}$ (missing in the flawed solution)
The reviewer correctly noted that block constraints must not be merged into $c_{ij}$. They form a separate family.
Columns are indexed by pairs $(B,r)$, where $B$ is a block index and $r$ is a digit. The block index is
$$ \beta(i,j)=\left(\left\lceil \frac{i}{n}\right\rceil,\left\lceil \frac{j}{n}\right\rceil\right). $$
A candidate $(i,j,k)$ satisfies the block–digit constraint column $(B,r)$ exactly when it lies in block $B$ and uses digit $r$:
$$ d_{(i,j,k),(B,r)}=\delta_{\beta(i,j),B},\delta_{k,r}. $$
Final corrected formulation
The correct decomposition of the Sudoku exact-cover incidence structure is therefore:
$$ \boxed{ a_{(i,j,k),(p,q)}=\delta_{i,p}\delta_{j,q} } $$
$$ \boxed{ b_{(i,j,k),(p,r)}=\delta_{i,p}\delta_{k,r} } $$
$$ \boxed{ c_{(i,j,k),(q,r)}=\delta_{j,q}\delta_{k,r} } $$
$$ \boxed{ d_{(i,j,k),(B,r)}=\delta_{\beta(i,j),B}\delta_{k,r} } $$
Consistency with the exact-cover system
Each candidate $(i,j,k)$ corresponds to exactly one row in the exact-cover matrix and activates exactly one column in each constraint family:
- one cell constraint $(i,j)$,
- one row–digit constraint $(i,k)$,
- one column–digit constraint $(j,k)$,
- one block–digit constraint $(\beta(i,j),k)$.
All other entries are zero, and no constraint families are merged. This matches exactly the structure used in (28).