Kakurasu

Kakurasu is a shading puzzle dressed as a Kakuro. The grid is a rectangle of cells, each of which is to be declared either shaded or unshaded. Down the right-hand edge sits a column of integers, one per row; along the bottom sits a row of integers, one per column. The right-edge integer is the sum of the column indices of the shaded cells in its row; the bottom-edge integer is the sum of the row indices of the shaded cells in its column. The weights $1, 2, \dots, n$ are labelled along the top and left edges: column indices increase from $1$ at the left, and row indices increase from $1$ at the top.

The puzzle looks, at first glance, like a Kakuro cousin. The arithmetic is the same shape: a sum over selected cells. What changes is the alphabet. In Kakuro each white cell takes a digit from $1$ to $9$; in Kakurasu each cell takes a value from $\{0, 1\}$, and the weights in the sum come not from the cells themselves but from their position along the run. That small shift, from digits-as-values to position-as-weight, moves the puzzle out of the constraint-programming register into something cleaner still: a pure binary integer program with only linear constraints and no all-different in sight.

This chapter models the puzzle in $0$/$1$ variables, solves a $9 \times 9$ instance in roughly $20$ milliseconds, and notes the single observation that makes the formulation water-tight: every row and every column’s clue uniquely decodes the binary pattern of that row or column, in the same way that the positional notation for an integer uniquely decodes its digits.

Rules and a small instance

A Kakurasu puzzle is an $n \times n$ grid of cells. Each cell $(r, c)$, with $r, c \in \{1, \ldots, n\}$, is either shaded or unshaded. Write $x_{r,c} \in \{0, 1\}$ for its state, with $1$ for shaded. Two families of clues govern the shading.

1. For each row $r$, the sum $\sum_{c=1}^{n} c \cdot x_{r,c}$ equals a given integer $R_r$. That is: shaded cells in row $r$, weighted by their column indices, total $R_r$.

2. For each column $c$, the sum $\sum_{r=1}^{n} r \cdot x_{r,c}$ equals a given integer $C_c$. Shaded cells in column $c$, weighted by their row indices, total $C_c$.

Figure 4.1 gives a $9 \times 9$ Kakurasu with every row- and column-clue populated; each is a demand on the corresponding run. No pre-shaded cells: the solver fills the entire $81$-bit array from the clues alone.

The programming model

Let $x_{r,c} \in \{0, 1\}$ for $1 \le r, c \le n$. The puzzle is the system of linear equalities $$\begin{align*} \sum_{c=1}^{n} c \cdot x_{r,c} &= R_r & \text{for each row } r, \\ \sum_{r=1}^{n} r \cdot x_{r,c} &= C_c & \text{for each column } c. \end{align*}$$

This is a $0$/$1$ integer linear program with $n^2$ variables and $2n$ equality constraints. No all-different, no reified booleans, no auxiliary variables: everything the puzzle says is a linear combination of indicator variables equal to a constant.

Why the clues decode uniquely

A single row, in isolation, looks like this: given $R \in \{0, 1, \ldots, n(n+1)/2\}$, find $x_1, \ldots, x_n \in \{0, 1\}$ with $\sum_c c \cdot x_c = R$. The answer is not always unique in isolation: $R = 3$ is both $\{3\}$ and $\{1, 2\}$. What makes the full puzzle uniquely solvable, when it is, is the interlocking of the row and column clues: the binary pattern of row $r$ must simultaneously satisfy its own row equation and contribute consistently to all nine column equations. For the specific $9 \times 9$ in Figure 4.1, enumeration confirms one admissible matrix. The solver shows it in Figure 4.2.

A solver in a dozen lines

from ortools.sat.python import cp_model

def solve_kakurasu(n, row_clues, col_clues):
    """Return an n x n 0/1 array satisfying the clues."""
    m = cp_model.CpModel()
    x = [[m.NewBoolVar(f"x{r}{c}")
          for c in range(n)] for r in range(n)]
    for r in range(n):
        m.Add(sum((c+1) * x[r][c]
                  for c in range(n)) == row_clues[r])
    for c in range(n):
        m.Add(sum((r+1) * x[r][c]
                  for r in range(n)) == col_clues[c])
    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)]

For the $9 \times 9$ instance the solver returns in about $18$ milliseconds. Enumeration of all feasible assignments returns one, so the puzzle is well-posed.

A larger instance

Figure 4.3 is Otto Janko’s Puzzle $390$ from the janko.at Kakurasu archive, at $11 \times 11$ and rated at the top tier of the site’s difficulty scale. The row and column clues are large enough to force substantial interaction between constraints; CP-SAT returns the unique shading in Figure 4.4 in about $2$ milliseconds, a reminder that $121$ binary variables under $22$ linear constraints is small work for a modern ILP backend, however challenging the puzzle is to solve by hand.

The arithmetic geometry of the grid

A $n \times n$ Kakurasu sits naturally in the integer lattice $\mathbb{Z}^{n^2}$, each cell a coordinate. The shaded patterns form the integer points of the hypercube $\{0, 1\}^{n^2}$; the clue set carves out an intersection of this cube with an affine subspace of codimension $2n$. A well-posed puzzle is one whose cube-affine intersection consists of a single point. The number of clue tuples that yield unique puzzles grows rapidly with $n$; for $n = 9$ the feasible volume under $18$ clue values is already small enough that a well-tuned generator produces a near-unique puzzle the first time.

One further curiosity. The maximum row clue is $1 + 2 + \cdots + n = n(n+1)/2$, attained when the entire row is shaded. The minimum is $0$, attained when none is. The same bounds apply to column clues. The middle clue values, around $n(n+1)/4$, support the greatest number of feasible row patterns and are the ones that, under random generation, most reliably lead to unique puzzles when paired in sufficient count.

Sources. Kakurasu appears in the Nikoli family of sum-based puzzles as a counterpart to Kakuro; the positional weighting is a unique identifier. The $9 \times 9$ instance in Figure 4.1 is sourced from the recreational_maths collection and was originally solved with Z$3$; the CP-SAT port here is in the same variable space with equivalent constraints. For the broader family of positional-sum puzzles, see the survey material at the Nikoli English-language site.