Squares Sudoku

Squares Sudoku is Killer Sudoku, restricted to perfect squares. The base puzzle is an ordinary $9 \times 9$ Sudoku grid: each row, column, and $3 \times 3$ box holds the digits $1$ through $9$ exactly once. Onto this base sits a partition of the grid into cages, each a connected polyomino of one or more cells, with one further demand: the digits in each cage sum to a perfect square. The squares allowed by convention are the small ones a $1$-to-$9$ digit sum can reach, namely $4$, $9$, $16$, and $25$.

The puzzle sits in the family of Killer-style Sudoku variants that emerged in the wake of the early-$2000$s Sudoku boom, designed to add an arithmetic dimension without losing the purity of the underlying Latin-square logic. Killer Sudoku itself attaches an explicit sum value to each cage; Squares Sudoku replaces those values with the simple membership test “the cage’s sum is one of $\{4, 9, 16, 25\}$”. The model gains an or where Killer Sudoku has an $=$, and the puzzle becomes strictly harder for human solvers because the cage’s target is hidden behind an enumeration.

For a CP solver the change is small. The Killer-cage equation $\sum_{(r,c) \in C} x_{r,c} = t$ becomes $\sum_{(r,c) \in C} x_{r,c} \in \{4, 9, 16, 25\}$, encoded as a one-hot Boolean over the four allowed targets with a reified equality on each. The solver searches over the joint space of digit assignment and target-square selection.

Rules and a small instance

A Squares Sudoku puzzle is a $9 \times 9$ grid of cells. The grid carries a partition into cages, each a connected polyomino of one or more cells. The puzzle’s constraints are the three Sudoku constraints from Chapter $2$ together with a fourth.

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 $3 \times 3$ box contains each digit from $1$ to $9$ exactly once.

4. For every cage, the sum of its cells’ digits lies in $\{4, 9, 16, 25\}$.

Unlike Killer Sudoku, the cage-sum target is not pre-declared; the solver must choose, for each cage, which perfect square the cage will hit. The fourth rule is therefore a kind of “meta-clue”: it constrains the structure of the digit assignment without committing to a specific target per cage.

Figure 8.1 shows the $9 \times 9$ instance from the recreational mathematics archive: $29$ cages of varying shape, no givens, and the perfect-square sum rule applied to each cage.

The programming model

Let $x_{r,c} \in \{1, \ldots, 9\}$ for $0 \le r, c < 9$. The Sudoku layer is the three families of all-different constraints from Chapter $2$. The cage layer adds, for each cage with cell set $C$, the constraint $$\sum_{(r, c) \in C} x_{r, c} \;\in\; \{4, 9, 16, 25\}.$$

In CP-SAT this is modelled with a one-hot Boolean for the four allowed targets: $$\sum_{t \in \{4, 9, 16, 25\}} b_{C, t} \;=\; 1, \qquad \sum_{(r, c) \in C} x_{r, c} \;=\; t \text{\ \ when\ } b_{C, t} = 1,$$ the second equation reified against the indicator $b_{C, t}$ through OnlyEnforceIf. With $29$ cages and four allowed targets, the additional Boolean count is $116$, modest by CP-SAT standards.

A solver in twenty-five lines

from ortools.sat.python import cp_model

SQUARES = [4, 9, 16, 25]

def solve_squares_sudoku(cages):
    n = 9
    m = cp_model.CpModel()
    x = [[m.NewIntVar(1, 9, 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 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)
    for cage in cages:
        s = sum(x[r][c] for (r, c) in cage)
        bs = [m.NewBoolVar("") for _ in SQUARES]
        m.Add(sum(bs) == 1)
        for b, t in zip(bs, SQUARES):
            m.Add(s == t).OnlyEnforceIf(b)
    sv = cp_model.CpSolver()
    sv.Solve(m)
    return [[sv.Value(x[r][c])
             for c in range(n)] for r in range(n)]

The puzzle in Figure 8.1 solves uniquely in about $70$ milliseconds, returning Figure 8.2.

A spot-check confirms the rule. The two-cell cage $\{(0,0), (0,1)\}$ holds $\{6, 3\}$, summing to $9$. The four-cell cage $\{(0,7), (1,7), (1,6), (2,6)\}$ holds $\{7, 9, 5, 4\}$, summing to $25$. The two-cell cages $\{(6,6), (6,7)\}$, $\{(7,1), (7,2)\}$, $\{(8,3), (8,4)\}$ each hold pairs summing to $4$, forcing the rare $\{1, 3\}$ partition (since $\{2, 2\}$ is forbidden by row distinctness).

The arithmetic of the constraint

Each cage’s sum constraint, before the Sudoku layer is imposed, admits a small number of cell-value assignments. A two-cell cage summing to $4$ has the single multiset $\{1, 3\}$; one summing to $9$ has $\{1, 8\}, \{2, 7\}, \{3, 6\}, \{4, 5\}$; one summing to $16$ has $\{7, 9\}$; one summing to $25$ is impossible (maximum two-digit sum is $9 + 8 = 17$). A three-cell cage summing to $4$ requires $\{1, 1, 2\}$, which row distinctness forbids; summing to $9$ has eight multisets; summing to $25$ has three. The number of feasible cage-internal assignments shrinks fast with cage size and stays small enough that CP-SAT’s constraint propagation prunes early; the solver’s actual search work is in the global Sudoku layer.

The choice of allowed squares matters. With $\{1, 4, 9, 16, 25\}$ allowed, single-cell cages of value $1$ would be permitted but not constraint-bearing. With $\{4, 9, 16, 25, 36, 49\}$, larger cages of five or more cells (whose sums can exceed $25$) become viable. The conventional set $\{4, 9, 16, 25\}$ keeps the puzzle restricted to interesting cage shapes.

Sources. Killer Sudoku, the parent of the Squares Sudoku variant, was popularised in Japan by Tetsuya Nishio and in the West through The Times of London in $2005$; the Japanese name is sankaku or Sumdoku. The specific perfect-squares restriction used here is documented in the recreational mathematics archive accompanying this book; the unique-solution check was performed by enumeration with CP-SAT, and the puzzle does have a single completion under the constraint set $\{4, 9, 16, 25\}$. The $9 \times 9$ instance is original to that archive.