Kakurasu

Every cell on this board carries a price, and the price is simply where it sits. Colour a cell in row $i$, column $j$, and it adds its column number $j$ to the total for that row and its row number $i$ to the total for that column. The puzzle gives the totals, some for the rows and some for the columns, and asks which cells are coloured. So each line is a small subset-sum: choose cells along it whose perpendicular positions add to the figure in the margin, and do it so the rows and columns agree.

Position as weight

The one idea is that a cell’s coordinates are its weights. A blue cell in column $j$ is worth $j$ to its row, because what the row counts is the column numbers of its blue cells; the same cell is worth its row number $i$ to its column. So a row total is a sum over that row with the column index as the coefficient, and a column total is a sum over that column with the row index as the coefficient. Nothing else is needed.

Variables

One binary to a cell, on an $n \times n$ board, $$x_{ij} = 1 \iff \text{cell } (i, j) \text{ is coloured blue}.$$

Constraints

Where a row total $r_i$ is given, the column numbers of that row’s blue cells must add to it; where a column total $c_j$ is given, the row numbers of that column’s blue cells must add to it: $$\sum_{j} j\, x_{ij} = r_i \quad (\text{rows } i \text{ with a total}),$$ $$\sum_{i} i\, x_{ij} = c_j \quad (\text{columns } j \text{ with a total}).$$ A line with no total given is left free. There is nothing to optimise.

from ortools.sat.python import cp_model

def solve_kakurasu(n, rows, cols):
    m = cp_model.CpModel()
    x = {(i, j): m.NewBoolVar("")
         for i in range(1, n + 1) for j in range(1, n + 1)}
    for i, r in rows.items():
        m.Add(sum(j * x[i, j] for j in range(1, n + 1)) == r)
    for j, c in cols.items():
        m.Add(sum(i * x[i, j] for i in range(1, n + 1)) == c)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[s.Value(x[i, j]) for j in range(1, n + 1)]
            for i in range(1, n + 1)]

Take a five-by-five board. The row totals $6$, $8$ and $13$ are given for the first, third and fifth rows, with the second and fourth left blank, and the column totals are $11, 2, 12, 8, 10$. Even with two row totals missing the board is pinned, the columns and the three rows between them leaving one colouring (blue cells filled, the deduced row totals shown in brackets): $$\begin{array}{ccccc|c} \blacksquare & \cdot & \cdot & \cdot & \blacksquare & 6 \\ \blacksquare & \blacksquare & \cdot & \cdot & \cdot & (3) \\ \blacksquare & \cdot & \blacksquare & \blacksquare & \cdot & 8 \\ \cdot & \cdot & \blacksquare & \cdot & \blacksquare & (8) \\ \blacksquare & \cdot & \blacksquare & \blacksquare & \blacksquare & 13 \\ \hline 11 & 2 & 12 & 8 & 10 & \end{array}$$ The single blue cell of column two sits in row two, since $2$ is the only row number a lone cell there can contribute; column one’s total of $11$ is its rows $1, 2, 3, 5$; and row five, wanting $13$, takes columns $1, 3, 4, 5$. A count confirms there is no other board, which is how the puzzle is set, with just enough totals that no guessing is needed.

The constraint is the same weighted sum that runs through the knapsack chapter, one equation choosing a subset of items to hit a target, except that here the items are a line of cells, their values are fixed by position, and two families of these equations, one along the rows and one down the columns, are laced together so that each cell answers to both. It is about the smallest a puzzle can be while still needing a model.

Sources. Kakurasu is modelled by Martin J. Chlond, Japanese IPs, INFORMS Transactions on Education volume $14$, number $1$ ($2013$), pages $61$–$62$, which gives the row-number and column-number sum constraints used here; the five-by-five board, its partial totals and its unique solution are Chlond’s, reproduced and checked unique by the model above. Chlond credits the puzzle to the collection at brainbashers.com; it is a Japanese puzzle, circulated in the West also under the name Index Sums. The article’s companion puzzle, 3-In-A-Row, is the same binary grid with equal rows and columns and no three in a line that this book has already met as Binary Sudoku, and is not repeated here.