TAOCP 7.2.2.1 Exercise 57

Section 7.2.2.1: Dancing Links

Exercise 57. [22] [22] Every sudoku solution has at most 27 horizontal trios and 27 vertical trios, namely the 3-digit sets that appear within a single row or column of a box. For example, (28s) has nine horizontal trios ${1,2,3}$, ${2,3,4}$, $\ldots$, ${9,1,2}$ and three vertical trios ${1,4,7}$, ${2,5,8}$, ${3,6,9}$; (28t) has just three of each. The solution to (29a) has 26 horizontal trios and 23 vertical trios; ${3,6,8}$ occurs once horizontally, twice vertically.

Let $T$ be the 27 trios ${{a,b,c} \mid a \in {1,2,3}, b \in {4,5,6}, c \in {7,8,9}}$. Find all sudoku solutions for which all 27 horizontal trios and vertical trios are both equal to $T$.

Verified: no
Solve time: 6m08s

$$ A={1,2,3},\qquad B={4,5,6},\qquad C={7,8,9}. $$

Write $\mathcal C={A,B,C}$. The condition on a sudoku solution $S$ is exactly that, in every horizontal or vertical trio of every $3\times3$ box, the three entries belong to the three different classes $A,B,C$.

The previous solution tried to show that the induced $A,B,C$-pattern was unique up to sudoku symmetries. That assertion is false. The trio condition does not determine a unique class array. The correct classification is obtained by separating the class pattern from the fillings of the three classes.

Define a class sudoku to be a $9\times9$ array $K$ with entries in $\mathcal C$ satisfying:

Every row of $K$ contains exactly three $A$'s, three $B$'s, and three $C$'s.
Every column of $K$ contains exactly three $A$'s, three $B$'s, and three $C$'s.
Every $3\times3$ box of $K$ is a Latin square of order $3$ on the symbols $A,B,C$. Equivalently, every row and every column inside a box contains $A,B,C$ once each.

Every sudoku solution satisfying the hypothesis gives such a class sudoku by replacing each digit by its class. Conversely, every such class sudoku can be filled to give solutions of the required kind.

To see the converse, fix a class sudoku $K$. Consider the cells marked $A$. There are exactly three such cells in each row, column, and box. Fill these cells with $1,2,3$ in such a way that each row, column, and box contains each of $1,2,3$ exactly once. This is precisely a sudoku filling of the $A$-cells. Do the same independently for the $B$-cells using $4,5,6$, and for the $C$-cells using $7,8,9$.

The resulting $9\times9$ array is a sudoku solution. Indeed, every row, column, and box already contains the three classes $A,B,C$ in the required numbers, and the independent fillings ensure that within each class the individual digits occur exactly once in every sudoku unit. Therefore every unit contains the digits $1,\ldots,9$ exactly once.

Moreover, every horizontal or vertical trio lies in a single box. In that box it contains one occurrence of each of $A,B,C$, hence it is a set

$$ {a,b,c},\qquad a\in A,\ b\in B,\ c\in C, $$

and therefore belongs to $T$.

It remains to prove that this construction gives every possible solution. Let $S$ be any sudoku solution satisfying the condition. Replace every digit of $S$ by the element of $\mathcal C$ containing it. Because every trio contains one digit from each of $A,B,C$, each row and column contains three copies of each class, and each box has one copy of each class in every mini-row and mini-column. Hence the resulting array $K$ is a class sudoku.

The cells of $K$ labelled $A$ are exactly the cells occupied by $1,2,3$ in $S$. Since $S$ is a sudoku solution, those cells contain a valid filling of the $A$-cells. The same holds for $B$ and $C$. Thus $S$ arises from $K$ by the filling procedure above.

Therefore the complete set of solutions is:

$$ \boxed{ \begin{array}{l} \text{Choose any class sudoku }K\text{ on }{A,B,C};\[2mm] \text{then fill the }A\text{-cells by a sudoku filling of }{1,2,3},\ \text{the }B\text{-cells by a sudoku filling of }{4,5,6},\ \text{and the }C\text{-cells by a sudoku filling of }{7,8,9}. \end{array}} $$

Every solution satisfying the trio condition occurs exactly in this way.

The displayed array in the proposed solution is one particular member of this family, but it is not a normal form for all solutions. The missing degrees of freedom are the different possible class sudokus and the independent fillings of the three digit classes. $\square$