Unlocking Sudoku's Secrets

Two well-known mathematical approaches show up in sudoku: graph theory and computer algebra. The Chalkdust piece walks through both, with worked steps for each.

Sudoku as vertex coloring

Each of the 81 cells is a vertex labelled by an ordered pair $(x, y)$. Two distinct vertices share an edge if they sit in the same row, same column, or same 3×3 region. A valid sudoku solution is then a 9-coloring of this graph: assign one of nine colors to each vertex so that no edge has two endpoints the same color. The original sudoku has a solution iff the graph has a 9-coloring.

The piece pairs the greedy algorithm with backtracking:

1. Pick the first uncolored cell.
2. Assign it the smallest valid number.
3. Move to the next uncolored cell, repeat.
4. On a conflict (no valid number remains), backtrack to the previous cell, pick the next valid number, resume greedy from there.

The worked example shows the greedy run placing an 8 in cell (1, 7) (because 4–6 conflict with peers), then hitting a dead end at (1, 8), backtracking to (1, 7) to try 9, and resuming. Related work cited: Joshua Cooper and Anna Kirkpatrick on minimal sets and minimal fair puzzles; Michael Haythorpe linking Hamiltonian cycles to sudoku of different sizes.

Sudoku via Gröbner bases

Sudoku is also a constraint problem over the integers 1–9, which is the kind of thing computer algebra handles. The piece introduces the machinery:

• Polynomial ring $\mathbb{Q}[x_0, \dots, x_{80}]$ — one variable per cell.
• Ideal — additive subset closed under multiplication by ring elements; generated by a set of polynomials.
• Term ordering — fixed order on monomials. Lexicographic for explanation, degree-reverse-lex for actual Gröbner basis computation.
• Leading term — the greatest term under the ordering. A Gröbner basis $G$ for ideal $I$ is one where $\operatorname{lt}(G) = \operatorname{lt}(I)$.

The useful property is that a Gröbner basis puts the system into triangular form: $g_1$ involves only $x_1$, $g_2$ involves $x_1$ and $x_2$ with leading term in $x_2$, and so on. Substitution becomes mechanical.

Encoding sudoku as polynomials:

• Each cell takes value 1–9: $(x_i - 1)(x_i - 2)\cdots(x_i - 9) = 0$ for every cell.
• Each row, column, and region sums to 45 and has product $9! = 362{,}880$. That covers no-duplicates.
• For each pre-filled cell with value $a_j$: $x_j - a_j = 0$.

135 polynomials plus one per known cell. Run Buchberger's algorithm to compute the Gröbner basis of the ideal. If the puzzle has a unique solution, the basis is 81 linear polynomials and the solution reads off directly.

Bruno Buchberger introduced Gröbner bases in his 1965 PhD thesis, naming them after his advisor Wolfgang Gröbner.

The shidoku worked example

Shidoku is the 4×4 version with four 2×2 regions. 16 variables, value polynomials $(x_i-1)(x_i-2)(x_i-3)(x_i-4)$, row/column/region sums of 10 and products of 24, plus known-cell equations. 40 polynomials total, supplemented by the five pre-filled cells. Feed to Matlab's gbasis and the returned basis is the 16-equation linear system that reads off the unique solution.

What this is good for

Both approaches generalize. Backtracking graph-coloring solvers extend trivially to harder constraint problems; the Gröbner basis approach extends to any constraint problem expressible as polynomial equations over a field, which includes most combinatorial constraint puzzles. The trade is the usual one: backtracking is fast in practice but worst-case exponential; Gröbner basis computation has bad worst-case complexity (doubly exponential in the number of variables) but turns the search into pure algebraic substitution once the basis is computed.

The piece sits next to existing neurosymbolic threads in the wiki — see neurosymbolic-ai for the broader pattern of pairing search with symbolic constraint solvers.