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: 5m02s

Let the Sudoku grid be partitioned into the usual $3\times 3$ boxes. A horizontal trio is the three cells in a fixed row of a box, and a vertical trio is the three cells in a fixed column of a box.

The condition is that every horizontal and vertical trio lies in

$$ T=\bigl{{a,b,c}\mid a\in{1,2,3},\ b\in{4,5,6},\ c\in{7,8,9}\bigr}. $$

Hence every such trio contains exactly one digit from each of

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

1. Reduction to a 3-symbol structure inside each box

Fix a box. Each horizontal trio in the box is a row of length 3, and it contains exactly one element from each of $A,B,C$. The same holds for each column of the box.

Therefore, if we replace every digit in $A$ by the symbol $A$, every digit in $B$ by $B$, and every digit in $C$ by $C$, then in each box:

every row contains $A,B,C$ exactly once,
every column contains $A,B,C$ exactly once.

So each box is a Latin square of order $3$ on the alphabet ${A,B,C}$.

No interaction between different boxes has been used yet.

2. Global consequences of the box structure

Now use the full Sudoku condition: each row and each column of the $9\times 9$ grid contains each digit $1,\dots,9$ exactly once.

Fix a global row of the Sudoku. It intersects three boxes, and in each box-row it contributes one $A$, one $B$, and one $C$. Hence every global row contains exactly three $A$-cells, three $B$-cells, and three $C$-cells. The same holds for every column.

Thus each of the three classes $A,B,C$ forms an independent $9\times 9$ pattern of occupied cells in which:

each row contains exactly three cells of the class,
each column contains exactly three cells of the class,
each box contains exactly three cells of the class, one in each row and column of the box.

This is already a rigid combinatorial structure: within each class, the positions form a $3$-fold transversal system of the $3\times 3$ box grid, but still with internal freedom.

Importantly, nothing here forces a unique cyclic or affine pattern; different boxes may realize different Latin squares on ${A,B,C}$, independently.

3. Decoupling into three independent subsystems

We now refine the structure. Consider only the cells whose values lie in $A={1,2,3}$. In each box, exactly three cells belong to $A$, and they occupy one cell in each row and column of the box. Hence the $A$-cells form a valid Sudoku-shaped configuration on the $9\times 9$ grid with the following property:

every row contains exactly three $A$-cells,
every column contains exactly three $A$-cells,
every box contains exactly three $A$-cells, one per box-row and box-column.

Now consider the actual digits inside $A$. Since global Sudoku requires each digit $1,2,3$ to appear exactly once in every row and column, the restriction to $A$-cells is itself a standard Sudoku on the alphabet ${1,2,3}$ (with the same $9\times 9$ grid, but each row/column contains each of $1,2,3$ exactly once among the $A$-cells).

The same argument applies independently to $B={4,5,6}$ and $C={7,8,9}$.

Hence the original Sudoku decomposes into three disjoint Sudoku systems on alphabets of size $3$, coupled only by the requirement that their occupied positions are disjoint and cover the grid.

4. Structure inside a single box

Return to a single box. Inside that box, for each class $A,B,C$, there is exactly one cell per row and per column assigned to that class. Thus, within the box, the class pattern is a $3\times 3$ Latin square on ${A,B,C}$.

Crucially, there is no constraint forcing the same Latin square to appear in different boxes. Each of the 9 boxes may choose any Latin square of order $3$ independently, subject only to compatibility with row/column counts, which is automatic from the Latin property.

Therefore, the global structure is not a single rigid affine pattern; it is a patchwork of local Latin squares.

5. Final classification

A Sudoku solution satisfying the condition is exactly equivalent to the following data:

For each box, a Latin square of order $3$ on ${A,B,C}$, independently chosen subject only to Sudoku row/column consistency (which is exactly the Latin property in each box).
For each class $A,B,C$, an independent Sudoku filling of the $9\times 9$ grid restricted to the cells of that class, using digits ${1,2,3}$ (for $A$), ${4,5,6}$ (for $B$), and ${7,8,9}$ (for $C$), respectively.

These three fillings are independent, and there is no further global coupling beyond the requirement that each box has the prescribed $A/B/C$ partition.

Equivalently, the set of solutions is the Cartesian product of three independent order-$3$ Sudoku structures together with independent choices of $3\times 3$ Latin squares in each box specifying the class layout.

6. Conclusion

The condition “all horizontal and vertical trios lie in $T$” enforces only that each $3\times 3$ box is a Latin square over the three digit blocks $A,B,C$, and that each block of digits behaves independently as a valid $3$-symbol Sudoku system.

It does not force any global cyclic or affine structure. In particular, there is no uniqueness up to symmetry: many non-isomorphic configurations arise from independent choices of Latin squares in the boxes and independent $3$-symbol Sudoku fillings within each digit block.