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 CP-SAT solver

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 combines all-different propagation with Boolean reasoning and search. This does not guarantee that every human tactic is performed by one propagator.

A hard instance

Arto Inkala’s AI Escargot, published in $2006$, is a well-known difficult Sudoku for human solvers. The same model solves it; computational effort depends on the instance and solver settings, rather than uniqueness alone.

The gap between human and solver here is instructive. Humans track candidates and forcing chains; the solver applies generic constraint propagation and search. OR-Tools supports several all-different treatments, including matching-based filtering and Boolean expansion. Neither the encoding nor the measured times imply that all uniquely solvable Sudokus take equal work.

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 search for sixteen-clue puzzles, none of which can be unique. 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 implementations include matching-based filtering related to Régin’s algorithm (AAAI $1994$), with the treatment depending on the model and solver settings.