Fillomino

Fillomino is a pencil puzzle on a grid, and its rule is a single sentence that quietly encodes a hard idea. Fill every cell with a positive number so that the cells sharing any one number form a connected block of exactly that many cells, and no two blocks of the same size touch along an edge. A handful of cells start with numbers already written; the rest are blank. The first two demands are really one: if the equal-numbered cells form connected blocks of the right size, then two same-size blocks that touched would merge into a single larger block whose size no longer matched its number, so the no-touching rule comes for free. What remains is a constraint that integer programming finds genuinely awkward, connectivity, and modelling it well is the whole interest of the puzzle. Pearce and Forbes set Fillomino as a study in advanced modelling in the INFORMS Transactions on Education puzzle column; the single-commodity flow used below is one clean way to meet its central difficulty.

One rule, restated

Read the rule again as a condition on a grid of numbers alone:

a filling is a solution exactly when every connected region of equal numbers has size equal to that number.

A region here means a maximal set of cells of one value joined edge to edge. Two separate regions may carry the same number, provided they do not touch; if they touched they would be one region, and too big. So the puzzle is to choose a value for each cell such that the value of every cell equals the size of the connected same-valued region it sits in. The given clues simply fix some of those values in advance.

Modelling a region

Variables

Number the $RC$ cells $0$ to $RC - 1$. For each cell $c$ let $v_c \in \{1, \ldots, K\}$ be its value, where $K$ is the largest region size allowed. To pin down which cells form one region, give each region a single root cell and let every cell point to its root: $\rho_c$ is the index of the root of $c$’s region, and the boolean $\text{rt}_c$ marks $c$ as a root, meaning $\rho_c = c$.

Region consistency

Each cell’s pointer must land on an actual root, and a cell shares its root’s value: $$\text{rt}_{\rho_c} = 1, \qquad v_c = v_{\rho_c}.$$ Two edge-adjacent cells belong to the same region if and only if they hold the same value, which is the rule that fuses equal numbers and separates unequal ones: $$\rho_c = \rho_d \iff v_c = v_d \qquad \text{for adjacent } c, d.$$

Connectivity and size, by one flow

The pointers alone would allow a “region” to be two disconnected patches sharing a root, so connectedness must be forced. A single commodity of flow does both jobs at once. Every non-root cell draws one unit of flow from its root, sent only along edges inside the region; the root supplies one unit for each of the other cells it owns. Writing $f_{cd} \ge 0$ for the flow on the arc from $c$ to $d$, allowed only when $c$ and $d$ share a region, $$\sum_{d} f_{dc} - \sum_{d} f_{cd} = \begin{cases} 1 & \text{if } c \text{ is not a root}, \\ 1 - v_c & \text{if } c \text{ is a root}. \end{cases}$$ A root therefore feeds $v_c - 1$ other cells, and since each is reached only through edges of the region, the region is connected and contains exactly $v_c$ cells. Region size equals value, which is the puzzle.

The solver

from ortools.sat.python import cp_model

def fillomino(R, C, clues, K=5):
    cells = [(i, j) for i in range(R) for j in range(C)]
    idx = {c: k for k, c in enumerate(cells)}
    N = len(cells)
    def adj(c):
        i, j = c
        return [(a, b) for a, b in ((i-1, j), (i+1, j), (i, j-1), (i, j+1))
                if 0 <= a < R and 0 <= b < C]
    m = cp_model.CpModel()
    val = {c: m.NewIntVar(1, K, "") for c in cells}
    rid = {c: m.NewIntVar(0, N - 1, "") for c in cells}
    root = {c: m.NewBoolVar("") for c in cells}
    for c in cells:
        m.Add(rid[c] == idx[c]).OnlyEnforceIf(root[c])
        m.Add(rid[c] != idx[c]).OnlyEnforceIf(root[c].Not())
    roots = [root[cells[k]] for k in range(N)]
    vals = [val[cells[k]] for k in range(N)]
    for c in cells:
        m.AddElement(rid[c], roots, 1)
        m.AddElement(rid[c], vals, val[c])
    same = {}
    for c in cells:
        for d in adj(c):
            if idx[d] < idx[c]:
                continue
            ev = m.NewBoolVar("")
            m.Add(val[c] == val[d]).OnlyEnforceIf(ev)
            m.Add(val[c] != val[d]).OnlyEnforceIf(ev.Not())
            er = m.NewBoolVar("")
            m.Add(rid[c] == rid[d]).OnlyEnforceIf(er)
            m.Add(rid[c] != rid[d]).OnlyEnforceIf(er.Not())
            m.Add(er == ev)
            same[c, d] = same[d, c] = er
    flow = {}
    for c in cells:
        for d in adj(c):
            flow[c, d] = m.NewIntVar(0, N, "")
            m.Add(flow[c, d] <= N * same[c, d])
    for c in cells:
        net = (sum(flow[d, c] for d in adj(c))
               - sum(flow[c, d] for d in adj(c)))
        m.Add(net == 1).OnlyEnforceIf(root[c].Not())
        m.Add(net == 1 - val[c]).OnlyEnforceIf(root[c])
    for c, v in clues.items():
        m.Add(val[c] == v)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[s.Value(val[(i, j)]) for j in range(C)] for i in range(R)]

A worked grid

The $5 \times 5$ instance with nine given numbers has the unique completion drawn in Figure 20.1, where the thick lines trace the region boundaries and the bold numbers are the clues. Read any number and the cells carrying it form a connected block of exactly that many cells: the two fives down the left edge and through the middle are separate connected pentominoes that never touch, the fours make a vertical tetromino, the threes split into two non-adjacent triominoes, and the lone ones sit isolated.

The flow construction is the part worth keeping. Connectivity is the recurring difficulty whenever an integer program must carve a board into contiguous pieces, in districting, in image segmentation, in forest-stand planning, and the single-commodity flow used here, one root per piece feeding a unit to every other cell, is the standard way to enforce it without enumerating the exponentially many ways a region could fail to connect.

Sources. The puzzle, and its use as a lesson in integer-programming modelling, follow Robin H. Pearce and Michael A. Forbes, Puzzle—The Fillomino Puzzle, INFORMS Transactions on Education volume $17$, number $2$ ($2017$), pages $85$–$89$. They give two formulations of their own: one adds the tile-size conditions as lazy constraints, cuts introduced only as the branch-and-bound search needs them, and the other is a composite-variable model with one binary per possible tile placement. The single-commodity-flow encoding presented here is a third route, chosen because it is self-contained and needs no solver-specific lazy-constraint machinery; it is a standard device for contiguity in integer programming, used across political districting and other partitioning problems. Fillomino is a creation of the Japanese puzzle publisher Nikoli; the grid solved here is a re-authored instance with a unique solution.