TAOCP 7.2.2.1 Exercise 97
The condition d_{(i+3)\bmod 9,j} = (d_{ij}+1)\bmod 3 couples only rows whose indices differ by $3$, while leaving column indices unchanged.
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: yes
Solve time: 59s
Solution
The condition
$$ d_{(i+3)\bmod 9,j} = (d_{ij}+1)\bmod 3 $$
couples only rows whose indices differ by $3$, while leaving column indices unchanged. Repeated application determines all rows from the first three.
Fix $j$. Starting from any $i$, three successive applications give
$$ d_{i+3,j} = d_{i,j}+1 \pmod 3,\qquad d_{i+6,j} = d_{i,j}+2 \pmod 3,\qquad d_{i+9,j} = d_{i,j}+3 \equiv d_{i,j} \pmod 3, $$
so the condition is consistent with the periodicity modulo $9$ in the row index.
Define the first three rows arbitrarily:
$$ (d_{0j}),\ (d_{1j}),\ (d_{2j}), \qquad 0 \le j \le 8, $$
with each entry in ${0,1,2}$. The rule then forces
$$ d_{3j} = d_{0j}+1,\quad d_{4j} = d_{1j}+1,\quad d_{5j} = d_{2j}+1, $$
$$ d_{6j} = d_{0j}+2,\quad d_{7j} = d_{1j}+2,\quad d_{8j} = d_{2j}+2 $$
all taken modulo $3$.
Every array constructed in this way satisfies the given symmetry, since shifting any row index by $3$ increases every entry by $1 \bmod 3$. Conversely, any solution must have its rows $3,4,5$ and $6,7,8$ determined uniquely from rows $0,1,2$ by repeated application of the defining relation, so no additional freedom exists beyond those initial choices.
Thus the complete set of $9 \times 9$ ternary orotoruses satisfying the symmetry consists exactly of all arrays obtained by choosing the first three rows arbitrarily and generating the remaining rows by addition of $1$ and $2$ modulo $3$ in the prescribed cyclic pattern.
The number of such orotoruses is therefore $3^{27}$, since each of the $27$ entries in the first three rows may be chosen independently from ${0,1,2}$.
This completes the determination. ∎