Section 7.2.2.1: Dancing Links

Exercise 43. [M30] [M30] Give formulas for the entries $a_{ij}$, $b_{ij}$, $c_{ij}$ of the sudoku squares in (28).

Verified: no
Solve time: 2m14s

Setup

The exercise asks for formulas for the entries $a_{ij}$, $b_{ij}$, and $c_{ij}$ of the three sudoku squares in equation (28). The supplied section excerpt contains the definition of sudoku squares and refers to equation (28), but it does not include the actual three arrays in (28).

The values of $a_{ij}$, $b_{ij}$, and $c_{ij}$ depend on the exact arrangements of digits in those three displayed squares. Without the entries of (28), there are multiple inequivalent possible formulas, so the requested formulas cannot be derived uniquely.

Solution

Let the three squares in (28) be

$$ A=(a_{ij}){1\le i,j\le 9},\qquad B=(b{ij}){1\le i,j\le 9},\qquad C=(c{ij})_{1\le i,j\le 9}. $$

A formula for each entry must reproduce the digit in the corresponding position of the displayed square. The information provided gives only the sudoku constraints:

$$ {a_{ij}:1\le j\le 9}= {b_{ij}:1\le j\le 9}= {c_{ij}:1\le j\le 9}

{1,2,\ldots,9} $$

for every row $i$, together with the analogous conditions for columns and $3\times3$ boxes. These conditions characterize valid sudoku squares, but they do not determine a unique square.

For example, many different functions of the form

$$ f(i,j)=1+\bigl(g(i,j)\bmod 9\bigr) $$

can produce valid sudoku squares for suitable choices of $g(i,j)$. Therefore the sudoku axioms alone do not determine $a_{ij}$, $b_{ij}$, or $c_{ij}$.

Verification

The missing information is precisely the data needed to determine the functions. Once equation (28) is supplied, the formulas can be obtained by identifying the row and column transformations used in each displayed square and proving that the resulting expressions give the required entries.

No complete proof or computation of the requested formulas is possible from the excerpt alone.

Notes

Please provide the image or text of equation (28), including the three sudoku arrays labeled (a), (b), and (c). The formulas for $a_{ij}$, $b_{ij}$, and $c_{ij}$ can then be derived completely.