TAOCP 7.2.2.1 Exercise 63

The statement supplied here is insufficient to determine the requested number.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.1: Dancing Links

Exercise 63. [29] [29] In how many different ways can Behrens's $9 \times 9$ array (35c) be regarded as a gerechte latin square? (In other words, how many decompositions of that square into nine boxes of size 9 have a complete "rainbow" of values ${1,2,3,4,5,6,7,8,9}$ in each box? None of the boxes should simply be an entire row or an entire column.)

Verified: no
Solve time: 4m35s

The statement supplied here is insufficient to determine the requested number. The exercise depends on the specific entries of Behrens's $9\times 9$ array in Figure 35c, but that array is not included in the prompt. Since the count depends on the actual Latin square, no exact numerical answer can be derived from the exercise text alone.

A complete solution must begin by encoding the given array $L$. For each cell $(i,j)$, let $L(i,j)\in{1,\ldots,9}$ denote its entry. A gerechte decomposition is a partition

$$ \mathcal B={B_1,B_2,\ldots,B_9} $$

of the $81$ cells into nine subsets of size $9$, subject to

$$ {L(i,j):(i,j)\in B_k}={1,2,\ldots,9} $$

for every $k$, together with the condition that no $B_k$ is an entire row or an entire column.

The enumeration can then be made rigorous as follows.

For every possible box $B$, form the candidate set

$$ C=\left{B\subseteq{1,\ldots,9}^2: |B|=9,\ {L(i,j):(i,j)\in B}={1,\ldots,9}, \ B\text{ is not a row or column} \right}. $$

The desired decompositions are exactly the exact covers of the $81$ cells by nine members of $C$. Therefore an exhaustive algorithm is:

  1. Generate all members of $C$.
  2. Choose a candidate box $B\in C$.
  3. Remove all candidates intersecting $B$.
  4. Repeat until either all cells are covered or no candidate remains.
  5. Count the completed covers.

Every counted cover is valid because each selected box has size $9$ and contains each symbol once. Every valid gerechte decomposition appears because its nine boxes are members of $C$, and the exact-cover search considers every possible choice of such boxes.

To provide the final integer, the actual $9\times9$ array from Behrens's Figure 35c is required. Without that data, different Latin squares can give different numbers of gerechte decompositions, so the numerical answer cannot be recovered from the information given.