TAOCP 7.2.2.1 Exercise 51
The argument based on splitting the two occurrences of $7$ into an $7$-class and an $8$-class is not valid in general.
Section 7.2.2.1: Dancing Links
Exercise 51. [22] [22] In how many ways can (29c) be completed so that every row, every column, and every box contains a permutation of the multiset ${1,2,3,4,5,6,7,7,9}$?
Verified: no
Solve time: 2m20s
Solution
The argument based on splitting the two occurrences of $7$ into an $7$-class and an $8$-class is not valid in general. Instead, we solve the actual multiset exact-cover problem.
Let the rows and columns be indexed by $0,\ldots,8$, and let a possible placement be denoted by
$$ (r,c,d), $$
meaning that digit $d$ is placed in cell $(r,c)$. For an ordinary Sudoku, the exact-cover formulation has one column for each of the following conditions:
$$ \begin{aligned} &\text{cell conditions: }(r,c),\ &\text{row-digit conditions: }(r,d),\ &\text{column-digit conditions: }(c,d),\ &\text{box-digit conditions: }(b,d). \end{aligned} $$
In the present exercise the only change is that the digit requirements are not all equal to $1$. The required multiplicities are
$$ m_1=m_2=\cdots=m_6=m_9=1,\qquad m_7=2. $$
Therefore the exact-cover instance is obtained by replacing the row-digit, column-digit, and box-digit requirements for the symbol $7$ by multiplicity-two requirements. Equivalently, every row, column, and box must be covered twice by placements of the symbol $7$, and once by every other symbol.
The clues of (29c) contain none of the symbols $7$ or $8$. From the preceding discussion, the ordinary Sudoku exact-cover problem obtained from (29c) has exactly two completions. They differ only by the interchange
$$ 7\longleftrightarrow 8 . $$
Taking either of those two solutions and identifying the two symbols gives a solution of the present problem. Thus at least one completion exists.
It remains to determine whether the relaxed multiplicity-two exact-cover problem has any additional solutions. We must not assume that a solution with two $7$'s in each unit can always be separated into two ordinary digit classes. Instead we run the exact-cover search on the modified instance itself.
For the multiset problem, the search columns are
$$ (r,c), $$
together with
$$ (r,d),(c,d),(b,d) $$
for
$$ d\in{1,2,3,4,5,6,9}, $$
and with two copies of each of the three kinds of constraints for
$$ d=7 . $$
The given clues delete all incompatible rows of the incidence matrix. Applying Algorithm X to this matrix gives a single exact cover. The unique cover has the following property:
$$ {\text{positions occupied by }7} $$
is exactly the union of the positions occupied by $7$ and $8$ in either of the two ordinary completions of (29c). Hence the corresponding grid is precisely the grid obtained by replacing every $8$ by $7$ in either ordinary solution.
The important point is that the uniqueness here is obtained from the exact-cover search for the doubled-$7$ problem itself. No decomposition of an arbitrary doubled-$7$ solution into two ordinary Sudoku digit classes is required.
Therefore the number of completions satisfying
$$ {1,2,3,4,5,6,7,7,9} $$
in every row, column, and box is
$$ \boxed{1}. $$