sec-sudoku-flow

9.16 Running example: Sudoku and flow-based recurrent repair

Sudoku removes most of the semantic ambiguity of a crossword while retaining its local-to-global architecture. Let \(V\) be the set of 81 cells, let \(\Delta _9=\{ 1,\ldots ,9\} \), and let \(\mathcal U\) be the 27 row, column, and block units. For a puzzle specification \(c\), give each cell the typed domain

\[ C_v(c)= \begin{cases} \{ c(v)\} , & v\text{ is a given cell},\\ \Delta _9, & v\text{ is initially blank}. \end{cases} \]

For each unit \(S\in \mathcal U\), define its allowed-relation object

\[ A_S(c) = \left\{ a\in \prod _{v\in S}C_v(c) \ \middle |\ a:S\longrightarrow \Delta _9\text{ is bijective}\right\} . \]

Thus a row, column, or block is represented by one nine-variable relation, not by a numerical penalty for repeated digits.

Let \(\mathbb S_c\) be the incidence category with cell objects \(v\), unit objects \(S\), and an arrow \(S\to v\) whenever \(v\in S\). The Sudoku constraint diagram \(D_c:\mathbb S_c\to \mathbf{Set}\) sends \(S\) to \(A_S(c)\), sends \(v\) to \(C_v(c)\), and sends an incidence arrow to the corresponding coordinate projection.

Definition 9.25 Sudoku solution object

The Sudoku solution object of the specification \(c\) is

\begin{equation} \mathsf{Sol}_{\mathrm{Sud}}(c) =\lim _{\mathbb S_c}D_c. \end{equation}

9.14

Proposition 9.26 Universal Sudoku completion

The points of \(\mathsf{Sol}_{\mathrm{Sud}}(c)\) are in bijection with the valid completions of \(c\). Hence an inconsistent puzzle has an empty solution object, a uniquely solvable puzzle has a singleton solution object, and an underdetermined puzzle has several points.

Proof ▼

A point of the limit chooses an allowed tuple in \(A_S(c)\) for every unit and a value in \(C_v(c)\) for every cell. Commutativity of the limiting cone forces every unit tuple to restrict to the same value at each shared cell. These common values form a global grid respecting the givens, and membership in every \(A_S(c)\) enforces the row, column, and block constraints. Conversely, every valid grid restricts to such a compatible cone, uniquely.

Crossword and Sudoku completion are therefore instances of one universal construction with different local relations. Crossword crossings impose mostly binary equality constraints. Sudoku units impose overlapping nine-variable all-different constraints. In both cases, the limit specifies what a globally admissible answer is; it does not prescribe an efficient method for finding one.