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

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()
    status = sv.Solve(m)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError(
            "no solution: " + sv.StatusName(status))
    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

Before the Sudoku layer is imposed, two-cell sums $4$ and $16$ admit the multisets $\{1,3\},\{2,2\}$ and $\{7,9\},\{8,8\}$ respectively. A connected two-cell cage shares a row or column, so Sudoku excludes the repeated digits. Sum $9$ admits $\{1,8\},\{2,7\},\{3,6\},\{4,5\}$; sum $25$ is impossible even without Sudoku (the maximum is $18$).

For three cells, sum $4$ requires $\{1,1,2\}$, sum $9$ admits seven multisets, and sum $25$ admits two: $\{7,9,9\}$ and $\{8,8,9\}$. Whether repeated digits survive Sudoku depends on cage geometry. In an L-shaped cage across a box boundary, two cells can share neither a row, column nor box. Arithmetic and Sudoku restrictions must therefore be applied together.

The choice of allowed squares matters. With $\{1, 4, 9, 16, 25\}$ allowed, single-cell cages of value $1$ would be permitted but fixed-digit clues constraining those cells to $1$. 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.