TAOCP 7.2.2.1 Exercise 97

Section 7.2.2.1: Dancing Links

Exercise 97. [M21] Find all $9 \times 9$ ternary orotoruses $D = {d_{ij}}$ that are symmetrical, in the sense that $d_{(i+3)\bmod 9} = (d_{ij}+1)\bmod 3$. (See exercise 7.2.1.1–109.)

Verified: no
Solve time: 3m37s

The supplied statement is still insufficient to determine the mathematical answer. The previous response was right that the definition is essential, but it stopped too early. The missing information is not a minor detail: it determines the set that must be enumerated.

The exercise asks for all ternary orotoruses, not all ternary $9\times9$ arrays satisfying the displayed symmetry. The word “orotorus” refers to a definition given earlier in TAOCP, specifically in the material cited by “See exercise 7.2.1.1–109.” That definition is not included here. Without it, there are many different possible interpretations:

• If “orotorus” means a toroidal array with all $2\times3$ subrectangles distinct, the search space and the resulting list are one thing.
• If it means an oriented version where reflected or rotated subrectangles are identified differently, the constraints are different.
• If it imposes a different family of forbidden repetitions, the answer changes again.

The displayed symmetry condition alone,

$$ d_{(i+3)\bmod 9,j}=(d_{ij}+1)\bmod 3, $$

or the likely intended version

$$ d_{(i+3)\bmod 9,(j+3)\bmod 9} =(d_{ij}+1)\bmod 3, $$

does not determine a finite list of arrays. It only reduces the degrees of freedom. For example, under the second interpretation the array is determined by a fundamental region, but many such fundamental regions exist before the missing orotorus condition is applied.

Therefore a complete “find all” solution cannot be derived from the information provided. To produce the requested textbook-style solution, the definition of orotorus from Section 7.2.1.1, or the full statement of Exercise 7.2.1.1–109, is required. Once that condition is supplied, the enumeration and completeness proof can be carried out.