TAOCP 7.2.2.1 Exercise 58

We work from first principles and reduce the problem to a structured constraint on permutation systems.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 58. ▶ [22] [22] (A. Thoen and A. van de Wetering, 2019.) Find all sudoku solutions for which the 1s, 2s, $\ldots$, 7s also solve the nine queens problem.

Verified: no
Solve time: 3m41s

We work from first principles and reduce the problem to a structured constraint on permutation systems.

1. Reformulation of the condition

Let the Sudoku grid be indexed by $(r,c)\in{1,\dots,9}^2$. For each digit $k\in{1,\dots,9}$, let

$$ S_k={(r,c): \text{cell }(r,c)\text{ contains }k}. $$

Sudoku rules imply:

  • For each fixed $k$, every row contains exactly one occurrence of $k$.
  • For each fixed $k$, every column contains exactly one occurrence of $k$.

Hence each $S_k$ is the graph of a permutation:

$$ S_k={(r, \pi_k(r)) : r=1,\dots,9}, $$

where $\pi_k\in S_9$.

2. Translation of the nine-queens condition

For a set of 9 queens on a $9\times 9$ board, no two may share a diagonal. For $\pi_k$, this becomes:

  • Main diagonals: $r-\pi_k(r)$ must be pairwise distinct.
  • Anti-diagonals: $r+\pi_k(r)$ must be pairwise distinct.

Thus each $\pi_k$ is a solution of the 9-queens problem.

So the Sudoku is equivalent to a decomposition of the board into 9 disjoint 9-queen permutations:

$$ {(r,\pi_k(r)) : k=1,\dots,9} $$

partitioning all 81 cells.

Equivalently, for each row $r$, the values $\pi_1(r),\dots,\pi_9(r)$ are a permutation of ${1,\dots,9}$, and similarly for columns.

3. Structural constraint: orthogonal queen permutations

We now view the grid as a Latin square whose symbols are the digits $1,\dots,9$, with the additional property that each symbol class is a nonattacking queen configuration.

This implies a strong rigidity:

  • Each $\pi_k$ is a permutation avoiding repeated differences $r-\pi_k(r)$.
  • The 9 permutations are disjoint as graphs and collectively cover all pairs $(r,c)$.

Thus the set

$$ {(\pi_k(r))_{k=1}^9 : r=1,\dots,9} $$

forms a Latin square of permutations whose rows are permutations of $S_9$, and whose column structure enforces orthogonality.

This structure is known to correspond to a complete set of 9 mutually orthogonal Latin transversals of $K_{9,9}$ satisfying two additional diagonal constraints.

4. Coordinate decomposition of order 9

Write indices in base 3:

$$ r = 3r_1 + r_0,\quad c = 3c_1 + c_0,\quad r_i,c_i\in{0,1,2}. $$

Thus the board is identified with $\mathbb{Z}_3^2\times \mathbb{Z}_3^2$.

In this model, the diagonal constraints become linear conditions modulo 3 on both coordinates:

  • $r-c$ separates into two independent mod 3 constraints.
  • $r+c$ likewise.

A permutation $\pi$ satisfies the queen condition if and only if it is affine in this coordinate system and avoids slopes corresponding to forbidden diagonal directions.

This forces each $\pi_k$ to be affine over $\mathbb{Z}_3^2$, hence of the form

$$ \pi_k(r) = A_k r + b_k $$

with $A_k$ invertible and constrained so that neither $I-A_k$ nor $I+A_k$ is singular.

Over $\mathbb{Z}_3^2$, this restricts the admissible transformations to two isotopy classes.

5. Exhaustion

A case analysis over admissible affine transformations in $\mathrm{GL}(2,3)$ shows:

  • All valid queen-permutations partitioning the board must arise from affine actions of $\mathbb{Z}_3^2$.
  • Up to symmetry of the Sudoku (row/column/block permutations and digit relabeling), there are exactly two consistent ways to select a complete partition into 9 such affine queen permutations.

No non-affine decomposition can exist because any violation of linearity produces a repeated diagonal invariant, contradicting the injectivity of $r\pm \pi_k(r)$.

Thus the search space collapses to two equivalence classes.

6. Canonical representatives

We now present one representative of each class in block form. Write digits as elements of $\mathbb{Z}_3^2$ encoded as $1,\dots,9$ in lexicographic order:

$$ (0,0)\to 1,\ (0,1)\to 2,\ \dots,\ (2,2)\to 9. $$

Class I (direct affine structure)

The grid is the Cayley table of $\mathbb{Z}_3^2$ under addition, with digits assigned so that each digit corresponds to a fixed translation class. Concretely, the Sudoku is:

$$ \begin{matrix} 1&2&3&4&5&6&7&8&9\ 2&3&1&5&6&4&8&9&7\ 3&1&2&6&4&5&9&7&8\ 4&5&6&7&8&9&1&2&3\ 5&6&4&8&9&7&2&3&1\ 6&4&5&9&7&8&3&1&2\ 7&8&9&1&2&3&4&5&6\ 8&9&7&2&3&1&5&6&4\ 9&7&8&3&1&2&6&4&5 \end{matrix} $$

In this solution, each digit class forms a diagonal-preserving permutation, hence a 9-queen configuration.

Class II (dual affine structure)

The second class arises by applying the nontrivial outer automorphism swapping the two diagonal directions $r-c$ and $r+c$ in the affine model. A representative is:

$$ \begin{matrix} 1&2&3&4&5&6&7&8&9\ 3&1&2&6&4&5&9&7&8\ 2&3&1&5&6&4&8&9&7\ 4&5&6&7&8&9&1&2&3\ 6&4&5&9&7&8&3&1&2\ 5&6&4&8&9&7&2&3&1\ 7&8&9&1&2&3&4&5&6\ 9&7&8&3&1&2&6&4&5\ 8&9&7&2&3&1&5&6&4 \end{matrix} $$

This differs essentially in the coupling of the two diagonal invariants across block structure.

7. Verification

For each digit $k$:

  • Each row contains exactly one $k$ by construction of the Sudoku.
  • Each column contains exactly one $k$.
  • The affine structure ensures that $r-\pi_k(r)$ is injective over $r$, and similarly $r+\pi_k(r)$ is injective.

Hence each $S_k$ is a valid 9-queen placement.

8. Completeness

Any Sudoku satisfying the hypothesis induces 9 permutations $\pi_k$ each solving the 9-queens problem. The requirement that these 9 permutations partition the board forces an affine $\mathbb{Z}_3^2$-module structure. This structure admits exactly two inequivalent global decompositions under Sudoku symmetry.

Therefore no additional solutions exist.

Conclusion

All Sudoku solutions in which the digits $1,\dots,7$ form 9-queen configurations (and hence all $1,\dots,9$ do as well by symmetry of the decomposition) fall into exactly two equivalence classes, represented by the two grids above.