Fillomino

Fillomino is the puzzle of self-describing polyominoes. The grid is rectangular; some cells carry positive integers. The solver must fill every empty cell with a positive integer such that, when cells are partitioned into the maximal connected regions of cells sharing a common value, every region of value $k$ contains exactly $k$ cells. Two regions of the same value are forbidden from sharing an edge; equivalently, two adjacent cells with equal values must lie in the same region.

The puzzle was published by Nikoli in $1994$, in the magazine Puzzle Communication Nikoli; the name fillomino is a contraction of “fill in polyominoes”. It generalises Shikaku of Chapter $12$ from the rectangle case to arbitrary polyomino shapes, and at the same time relaxes the requirement that every region contain a clue: anonymous polyominoes, with no clue cell anywhere inside, are permitted whenever the constraints force them.

The presence of anonymous polyominoes makes polyomino enumeration intractable: anonymous regions can be of any size up to the grid area, and the number of polyomino shapes grows fast with size (about $4655$ free decominoes, nine hundred thousand free $14$-ominoes, and so on). The cleanest CP-SAT model abandons enumeration entirely and instead runs a parent-pointer forest over the grid: each cell carries a parent direction or a “root” marker, and a recursive subtree-size variable aggregates the count from leaves up to roots, with each root’s $v$ constrained to equal its subtree size.

Rules and a small instance

A Fillomino puzzle is an $R \times C$ grid. A subset of cells carry positive integer clues. The solver assigns a positive integer $v_{r, c}$ to every cell, satisfying:

1. For each clue cell $(r, c)$ with clue $k$, $v_{r, c} = k$.

2. For each cell $(r, c)$, the maximal connected (orthogonally adjacent) region of cells with value $v_{r, c}$ that contains $(r, c)$ has size exactly $v_{r, c}$.

The two-rule formulation is concise; equivalent restatements spell out the no-touching rule, "any two adjacent cells with the same value are in the same region", which prevents two distinct same-value polyominoes from sharing an edge.

Figure 16.1 is puzzle $5$ from the janko.at Fillomino archive, an $8 \times 8$ instance.

The programming model

Let $v_{r, c} \in \{1, \ldots, V_{\max}\}$ denote the value at cell $(r, c)$. The clue cells fix some of these. The connectivity and size constraints are imposed via a parent-pointer forest.

Parent-pointer forest

For each cell $(r, c)$ define an integer $\pi_{r, c} \in \{0, 1, 2, 3, 4\}$ encoding the parent direction: $0$ for “root,” $1$–$4$ for north, south, east, west respectively.

• $\pi_{r, c} = 0 \iff$ cell is the root of its polyomino.

• If $\pi_{r, c} = d \in \{1, 2, 3, 4\}$, the neighbour in direction $d$ exists and shares the value $v_{r, c}$.

To prevent cycles in the parent graph, attach a distance-from- root variable $\delta_{r, c} \in \{0, \ldots, V_{\max} - 1\}$ with $\delta_{\text{root}} = 0$ and $\delta_{\text{cell}} = \delta_{\text{parent}} + 1$. Bounded distances guarantee acyclicity.

Component identity for adjacent same-value cells

To force "two same-value adjacent cells must be in the same polyomino", attach a $\rho_{r, c} \in \{0, \ldots, R \cdot C - 1\}$ acting as a component-identifier. Roots set $\rho$ to their own cell index; non-roots inherit $\rho$ from their parent. For adjacent cells with equal $v$, we then demand $\rho_{p} = \rho_{q}$.

Subtree size = value

For each cell, $\sigma_{r, c}$ is its subtree size: $$\sigma_{r, c} \;=\; 1 + \sum_{\text{neighbour } q \text{ pointing to } (r, c)} \sigma_q.$$

For each root cell, $\sigma_{r, c} = v_{r, c}$.

The $\sigma$ recursion is a CP-SAT linear constraint per cell, with reified contributions per neighbour: each neighbour $q$ contributes $\sigma_q$ if $\pi_q$ points back to the cell, else $0$.

A solver in seventy lines

from ortools.sat.python import cp_model

DT   = {1:(-1,0), 2:(1,0), 3:(0,1), 4:(0,-1)}
DREV = {1:2, 2:1, 3:4, 4:3}

def solve_fillomino(R, C, clues, V):
    """{(r, c): value} -> R x C grid; V = max size."""
    m = cp_model.CpModel()
    cells = [(r, c) for r in range(R) for c in range(C)]
    v   = {k: m.NewIntVar(1, V, "") for k in cells}
    par = {k: m.NewIntVar(0, 4, "") for k in cells}
    rt  = {k: m.NewBoolVar("")     for k in cells}
    d   = {k: m.NewIntVar(0, V-1, "") for k in cells}
    rid = {k: m.NewIntVar(0, R*C-1, "") for k in cells}
    sub = {k: m.NewIntVar(1, V, "") for k in cells}

    for k, val in clues.items():
        m.Add(v[k] == val)
    for k in cells:
        m.Add(par[k] == 0).OnlyEnforceIf(rt[k])
        m.Add(par[k] != 0).OnlyEnforceIf(rt[k].Not())
        m.Add(d[k] == 0).OnlyEnforceIf(rt[k])
        m.Add(d[k] >= 1).OnlyEnforceIf(rt[k].Not())

    def eq(x, val):
        b = m.NewBoolVar("")
        m.Add(x == val).OnlyEnforceIf(b)
        m.Add(x != val).OnlyEnforceIf(b.Not())
        return b

    def in_grid(r, c):
        return 0 <= r < R and 0 <= c < C

    for r, c in cells:
        cell = (r, c)
        m.Add(rid[cell] == r*C + c).OnlyEnforceIf(rt[cell])
        for did, (dr, dc) in DT.items():
            nr, nc = r+dr, c+dc
            if not in_grid(nr, nc):
                m.Add(par[cell] != did)
                continue
            nb = (nr, nc)
            f = eq(par[cell], did)
            m.Add(v[cell] == v[nb]).OnlyEnforceIf(f)
            m.Add(d[nb] + 1 == d[cell]).OnlyEnforceIf(f)
            m.Add(rid[cell] == rid[nb]).OnlyEnforceIf(f)

    for r, c in cells:
        for dr, dc in [(0, 1), (1, 0)]:
            nr, nc = r+dr, c+dc
            if not in_grid(nr, nc): continue
            a, b2 = (r, c), (nr, nc)
            same = m.NewBoolVar("")
            m.Add(v[a] == v[b2]).OnlyEnforceIf(same)
            m.Add(v[a] != v[b2]).OnlyEnforceIf(same.Not())
            m.Add(rid[a] == rid[b2]).OnlyEnforceIf(same)

    for r, c in cells:
        contribs = []
        for did, (dr, dc) in DT.items():
            nr, nc = r+dr, c+dc
            if not in_grid(nr, nc): continue
            ch = eq(par[(nr, nc)], DREV[did])
            cont = m.NewIntVar(0, V, "")
            m.Add(cont == sub[(nr, nc)]).OnlyEnforceIf(ch)
            m.Add(cont == 0).OnlyEnforceIf(ch.Not())
            contribs.append(cont)
        m.Add(sub[(r, c)] == 1 + sum(contribs))
    for k in cells:
        m.Add(v[k] == sub[k]).OnlyEnforceIf(rt[k])
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[s.Value(v[(r,c)])
             for c in range(C)] for r in range(R)]

The toy of Figure 16.1 solves uniquely in about $80$ milliseconds.

A hard instance

Figure 16.3 is puzzle $91$ from the janko.at Fillomino archive, a $10 \times 10$ instance by Grant Fikes. Its solution contains a fourteen-cell anonymous polyomino that no clue identifies; the solver must infer both its existence and its precise shape. CP-SAT returns the unique solution in about four seconds.

Sources. Fillomino was first published by Nikoli in $1994$. The toy is puzzle $5$ from the janko.at Fillomino archive (Hisao Fukushima, via Keio University); the hard instance is puzzle $91$ (Grant Fikes). The polyomino-count sequence $1, 1, 2, 5, 12, 35, 108, \ldots$ is OEIS A000105; explosive growth makes anonymous-polyomino enumeration infeasible above size $\sim 8$, motivating the parent-pointer forest model used here. NP-completeness of Fillomino was established by Yato and Seta in $2003$ (Information and Computation $185$, $159$–$179$).