Chapter 6

KenKen

KenKen is Sudoku with arithmetic. The grid is again an $n \times n$ Latin square: each row and each column a permutation of $1, \ldots, n$ . Layered on top, the grid is partitioned into cages, each carrying an arithmetic clue: the cells in a cage must combine, by addition, multiplication, subtraction, or division, to a target value declared in the cage’s top-left corner.

The puzzle was invented by the Japanese mathematics teacher Tetsuya Miyamoto in $2004$ , originally as a teaching device for elementary-school students learning arithmetic; he called it kashikoku naru puzzle ("a puzzle that makes you smarter"). The Tokyo publisher Gakken adopted it and renamed it KenKen, short for kenkou ken’i, "wisdom and cleverness". Among many trademarked variants in English-speaking markets it goes by Calcudoku, Mathdoku, and the New York Times’ KenKen.

The constraint set extends Sudoku in the cleanest possible way: the two all-different families remain, and every cage contributes one further equation. The arithmetic is local; the all-differents are global. CP-SAT’s AddMultiplicationEquality and AddAbsEquality primitives make the cage clues a few lines each. The result is a model that, like Sudoku, scales smoothly from a $4 \times 4$ teaching example to the $9 \times 9$ puzzles that test computer solvers.

Rules and a small instance

A KenKen puzzle is an $n \times n$ grid. Each cell holds a digit from $1$ to $n$ . The grid is partitioned into cages: each cage is a connected polyomino of one or more cells, and each carries an arithmetic clue.

Each row contains each digit from $1$ to $n$ exactly once.
Each column contains each digit from $1$ to $n$ exactly once.
For each cage with target $t$ and operator $\circ \in \{+, -, \times, \div\}$ , the cell values combine under $\circ$ to $t$ . Singleton cages carry only a target $t$ and force the cell to hold $t$ .

The arithmetic conventions need a moment. For addition and multiplication the cage’s cells combine in the natural order-free way: their sum or product equals the target. For subtraction and division, which are not commutative, the convention is to take the absolute difference (subtraction) or the larger divided by the smaller (division), so the order of cells in the cage does not matter. By tradition, subtraction and division cages contain exactly two cells.

Figure 6.1 shows a $4 \times 4$ KenKen with nine cages, including two singleton "givens" that are KenKen’s analogue of Sudoku starter clues.

*A $4 \times 4$ KenKen with nine cages. Cage borders are dashed; the operator and target sit in the top-left cell of each cage.*

*The unique completion. Each row and column contains $\{1, 2, 3, 4\}$ ; each cage’s contents combine under its operator to the target.*

The programming model

Let $x_{r,c} \in \{1, \ldots, n\}$ for $0 \le r, c < n$ . The Latin square base reuses the Sudoku constraints: $\begin{align*} \operatorname{alldifferent}(\{x_{r,c} : c\}) && \text{for each row } r, \\ \operatorname{alldifferent}(\{x_{r,c} : r\}) && \text{for each column } c. \end{align*}$

Each cage with target $t$ , operator $\circ$ , and cell set $C$ contributes one further constraint:

$\begin{align*} \text{Sum:} \quad & \sum_{(r,c) \in C} x_{r,c} = t. \\ \text{Product:} \quad & \prod_{(r,c) \in C} x_{r,c} = t. \\ \text{Difference } (|C|=2): \quad & |x_{r_1,c_1} - x_{r_2,c_2}| = t. \\ \text{Quotient } (|C|=2): \quad & x_{r_1,c_1} = t \cdot x_{r_2,c_2}\ \text{or}\ x_{r_2,c_2} = t \cdot x_{r_1,c_1}. \\ \text{Given:} \quad & x_{r,c} = t. \end{align*}$

The product and difference constraints need a touch of CP-SAT plumbing. AddMultiplicationEquality ties an auxiliary variable to the product of a list of variables in one call; AddAbsEquality ties an auxiliary to the absolute value of a single variable, used for the difference cage. The quotient cage uses two reified linear constraints under a Boolean indicator choosing which of the two cells is the dividend.

A solver in thirty lines

from ortools.sat.python import cp_model

def solve_kenken(n, cages):
    """cages: list of (op, target, [(r, c), ...]).
       op in {'+', '*', '-', '/', '='}."""
    m = cp_model.CpModel()
    x = [[m.NewIntVar(1, n, f"x{r}{c}")
          for c in range(n)] for r in range(n)]
    for r in range(n):
        m.AddAllDifferent(x[r])
    for c in range(n):
        m.AddAllDifferent([x[r][c] for r in range(n)])
    for op, t, cells in cages:
        vs = [x[r][c] for r, c in cells]
        if op == '+':
            m.Add(sum(vs) == t)
        elif op == '*':
            p = m.NewIntVar(1, n**len(vs), "")
            m.AddMultiplicationEquality(p, vs)
            m.Add(p == t)
        elif op == '-':
            d = m.NewIntVar(-n, n, "")
            ad = m.NewIntVar(0, n, "")
            m.Add(d == vs[0] - vs[1])
            m.AddAbsEquality(ad, d)
            m.Add(ad == t)
        elif op == '/':
            a, b = vs
            pick = m.NewBoolVar("")
            m.Add(a == t * b).OnlyEnforceIf(pick)
            m.Add(b == t * a).OnlyEnforceIf(pick.Not())
        elif op == '=':
            m.Add(vs[0] == t)
    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(n)] for r in range(n)]

The toy of Figure 6.1 solves in about $23$ milliseconds and admits a single completion.

A hard instance

Figure 6.3 is the $9 \times 9$ instance from the recreational maths archive, billed as the hardest KenKen recorded there. Thirty-three cages of mixed operator and length sit on top of the $9 \times 9$ Latin square base; the largest sums extend across five cells, the largest product is $378$ over four cells. CP-SAT returns the unique solution (Figure 6.4) in about $29$ milliseconds.

*A hard $9 \times 9$ KenKen with thirty-three cages. The largest cage carries the sum-clue $26$ over five cells; the most demanding is the product-clue $378$ over four.*

*The unique completion, recovered in about $29$ ms.*

The propagation that makes the hard puzzle tractable is again the all-different constraint working in tandem with cage-local arithmetic. A cage like $378 =$ product over four cells, on a $9 \times 9$ grid, has the factorisations $\{2, 3, 7, 9\}$ , $\{3, 6, 7, ?\}$ and a small handful of others over digits $1$ to $9$ ; CP-SAT enumerates these implicitly and prunes early.

Sources. KenKen was invented by Tetsuya Miyamoto in $2004$ and first published by Gakken in Japan as kashikoku naru puzzle. The puzzle reached an English audience through Will Shortz, the New York Times’ crossword editor, in $2008$ . Robert Fuhrer’s KenKen Puzzle LLC holds the trademark; Calcudoku and Mathdoku are widely-used free names for the same puzzle. The hard $9 \times 9$ instance is sourced from the recreational mathematics archive accompanying this book; its CP-SAT formulation matches the original Z $3$ model constraint by constraint.