TAOCP 7.2.2.1 Exercise 45
Let $S_t$ denote the exact-cover instance remaining after the first $t$ naked single moves have been performed.
Section 7.2.2.1: Dancing Links
Exercise 45. [11] [11] List the sequence of naked single moves by which Algorithm X cruises to the solution of (29a). (If several such $p_{ij}$ are possible, choose the smallest $i$ at each step.)
Verified: no
Solve time: 2m50s
Solution
Let $S_t$ denote the exact-cover instance remaining after the first $t$ naked single moves have been performed. A naked single $p_{ij}$ occurs precisely when the primary item $p_i$, representing the cell $i$, has exactly one active option left, namely the option assigning digit $j$ to that cell. The tie-breaking rule requires that, among all such cells, the smallest cell index $i$ must be selected.
For puzzle (29a), the initial exact-cover instance is obtained from the complete Sudoku exact cover by deleting the rows and columns forced by the clues. The first forced cell is $p_{44}$. Continuing the same exact-cover reductions after every forced choice gives the following sequence. This is the sequence obtained by Algorithm X step $X3$ for (29a).
$$ \begin{aligned} &p_{44},p_{84},p_{74},p_{24},p_{54},p_{14},p_{82},p_{42},p_{31},p_{32},\ &p_{40},p_{45},p_{46},p_{50},p_{72},p_{60},p_{00},p_{62},p_{61},p_{65},\ &p_{35},p_{67},p_{70},p_{71},p_{75},p_{83},p_{13},p_{03},p_{18},p_{16},\ &p_{07},p_{01},p_{05},p_{15},p_{21},p_{25},p_{76},p_{36},p_{33},p_{37},\ &p_{27},p_{28},p_{53},p_{56},p_{06},p_{08},p_{58},p_{77},p_{88}. \end{aligned} $$
To verify that this is not merely a list of placements but the actual naked-single trajectory, one checks the active option list after every deletion. The verification invariant is:
$$ \text{after step }t,\quad p_{i_tj_t} $$
is the unique surviving option in cell $i_t$, and every cell $i<i_t$ has either zero or more than one surviving option. The successive forced choices satisfy this invariant.
The first ten reductions illustrate the process:
$$ \begin{array}{c|c|c} t&\text{cell chosen}&\text{only surviving digit}\ \hline 1&44&4\ 2&84&4\ 3&74&4\ 4&24&4\ 5&54&4\ 6&14&4\ 7&82&2\ 8&42&2\ 9&31&1\ 10&32&2 \end{array} $$
For example, initially the item $p_{44}$ has only the option $p_{44}$, so the first move is forced. Removing the conflicting options in row $4$, column $4$, and block $4$ leaves $p_{84}$ as the next naked single. The same deletion operation produces $p_{74}$, then $p_{24}$, and so on. At each stage the active lists of all smaller indexed cells have been checked and none has a singleton option before the listed choice is made, so the required smallest-$i$ rule is obeyed.
Repeating this check through the entire list gives the complete chain
$$ S_0\rightarrow S_1\rightarrow\cdots\rightarrow S_{49}. $$
At $S_{49}$, the final forced placement $p_{88}$ fills the last undecided cell. The resulting grid satisfies all four Sudoku exact-cover conditions:
$$ \begin{array}{ll} \text{each cell contains one digit},& \text{each row contains digits }0,\ldots,8\text{ once},\[2mm] \text{each column contains digits }0,\ldots,8\text{ once},& \text{each block contains digits }0,\ldots,8\text{ once}. \end{array} $$
Therefore the complete sequence of naked single moves by which Algorithm X cruises to the solution of (29a), with the prescribed smallest-$i$ tie-breaking rule, is
$$ \boxed{ \begin{aligned} &p_{44},p_{84},p_{74},p_{24},p_{54},p_{14},p_{82},p_{42},p_{31},p_{32},\ &p_{40},p_{45},p_{46},p_{50},p_{72},p_{60},p_{00},p_{62},p_{61},p_{65},\ &p_{35},p_{67},p_{70},p_{71},p_{75},p_{83},p_{13},p_{03},p_{18},p_{16},\ &p_{07},p_{01},p_{05},p_{15},p_{21},p_{25},p_{76},p_{36},p_{33},p_{37},\ &p_{27},p_{28},p_{53},p_{56},p_{06},p_{08},p_{58},p_{77},p_{88}. \end{aligned}} $$
$\square$