Sudoku

Sudoku is the Latin square with pedigree. Nine rows, nine columns, nine $3 \times 3$ boxes, and the same nine digits placed everywhere exactly once. The puzzle’s commercial history is briefer than its logical lineage: Leonhard Euler studied Latin squares in the $1780$s; Howard Garns, an American retired architect, published a reduced-size version called Number Place in Dell Magazines in $1979$; and the Japanese publisher Nikoli picked it up in $1984$, renaming it Sudoku (a contraction of suuji wa dokushin ni kagiru, “the digits must remain single”) and imposing the rotational symmetry of clues that defines its modern visual rhythm.

Sudoku is, for our purposes, the canonical all-different puzzle. It has no sum clues, no length-variable runs, no visibility rules. The entire specification sits in three disjoint families of all-different constraints: rows, columns, and boxes. A CP-SAT model is a five-line affair. What makes individual puzzles hard is the amount of propagation a human needs to perform before a cell can be written in; what makes the solver fast is the aggregation of that propagation into a few standard constraint operators.

This chapter treats Sudoku twice over: once with a beginner’s instance, then again with Arto Inkala’s AI Escargot from $2006$, at the time the hardest puzzle known. The solver code does not change between the two.

Rules and a small instance

A Sudoku grid is a $9 \times 9$ lattice of cells. A subset of cells carry given digits between $1$ and $9$; the solver’s task is to fill every other cell with a digit between $1$ and $9$ subject to three constraints.

1. Each row contains each digit from $1$ to $9$ exactly once.

2. Each column contains each digit from $1$ to $9$ exactly once.

3. Each of the nine $3 \times 3$ boxes contains each digit from $1$ to $9$ exactly once.

A well-posed Sudoku has exactly one completion consistent with the givens. McGuire, Tugemann and Civario proved in $2012$ that the minimum number of givens a uniquely solvable Sudoku can carry is seventeen. At seventeen the puzzle is unique but often delicate; most Nikoli-published puzzles sit between twenty and thirty.

Figure 2.1 is the standard beginner’s example circulated in introductions to the puzzle, with thirty givens.

The programming model

Let $x_{r,c}$ denote the digit in row $r$ and column $c$, with $r,c \in \{0, 1, \ldots, 8\}$. The givens $g_{r,c}$ fix $x_{r,c} = g_{r,c}$ for those cells; all other $x_{r,c}$ are variables with domain $\{1, 2, \ldots, 9\}$. The three families of all-different constraints are $$\begin{align*} \operatorname{alldifferent}\bigl(\{x_{r,c} : c = 0, \ldots, 8\}\bigr) && \text{for each row } r, \\ \operatorname{alldifferent}\bigl(\{x_{r,c} : r = 0, \ldots, 8\}\bigr) && \text{for each column } c, \\ \operatorname{alldifferent}\bigl(\{x_{3 b_r + i,\, 3 b_c + j} : i, j = 0, 1, 2\}\bigr) && \text{for each box } (b_r, b_c). \end{align*}$$

Twenty-seven constraints in total, each over nine variables. A $0$/$1$ ILP formulation replaces $x_{r,c}$ with nine indicators $y_{r,c,d}$ and expresses each all-different as a pair of $\le$ inequalities. The CP model is shorter to write and faster to solve.

A solver in twenty lines

from ortools.sat.python import cp_model

def solve_sudoku(givens):
    """Return a 9x9 completion of the puzzle."""
    m = cp_model.CpModel()
    x = [[m.NewIntVar(1, 9, f"x{r}{c}")
          for c in range(9)] for r in range(9)]
    for r in range(9):
        for c in range(9):
            if givens[r][c]:
                m.Add(x[r][c] == givens[r][c])
    for r in range(9):
        m.AddAllDifferent(x[r])
    for c in range(9):
        m.AddAllDifferent([x[r][c] for r in range(9)])
    for br in range(3):
        for bc in range(3):
            block = [x[br*3+i][bc*3+j]
                     for i in range(3) for j in range(3)]
            m.AddAllDifferent(block)
    s = cp_model.CpSolver()
    ok = s.Solve(m)
    if ok not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError("no solution")
    return [[s.Value(x[r][c])
             for c in range(9)] for r in range(9)]

The function recovers Figure 2.2 in about $15$ milliseconds. No tactical code is written: no naked pairs, no hidden triples, no X-wings. CP-SAT’s all-different propagator, implemented as a matching in a bipartite digit-cell graph, does every one of these inferences by construction.

A hard instance

Arto Inkala’s AI Escargot, published in $2006$, was for several years the hardest Sudoku known in the sense that it required the longest chain of logical inferences a human could be forced to follow to solve it. Computationally it is no harder than any other unique puzzle: the same solver, the same code path, the same handful of milliseconds.

The gap between human and solver here is instructive. A human solves AI Escargot by maintaining a grid of candidate digits for every empty cell, eliminating candidates via row, column, and box exclusions, and tracing long conditional chains to contradiction (“if this cell is a seven, then that cell is a four, and then the box down-right has no place for a one”). CP-SAT does the same work algebraically. The all-different propagator, given the current domains, computes a maximum matching between cells and digits; any edge not in some maximum matching corresponds to a digit a cell cannot take, and is pruned. A linear-time update after each assignment suffices. In machine terms there is no distinction between Escargot and the beginner’s grid of Figure 2.1.

Sources. Howard Garns designed Number Place for Dell Pencil Puzzles & Word Games in $1979$. Nikoli began publishing the puzzle in $1984$ under the name Sudoku; the convention of rotationally symmetric clues and a minimum-clue ambition is their contribution. The uniqueness minimum of seventeen was settled by McGuire, Tugemann and Civario in Experimental Mathematics $23$ ($2014$), $190$–$217$, after a brute-force enumeration of candidate seventeen-clue grids. AI Escargot was published by Arto Inkala in $2006$; the puzzle appears in Inkala’s book AI Sudoku and on his website. CP-SAT’s all-different propagator follows Régin’s filtering algorithm (AAAI $1994$).