Flow Free

Flow Free is the puzzle of disjoint paths. The grid holds a set of coloured dots paired up by colour: two yellows, two blues, two reds. The task is to draw, for each colour, an unbroken path through orthogonally adjacent grid cells joining its two dots, with the strict additional rule that every cell of the grid must lie on exactly one path. No path crosses itself, no two paths share a cell, no cell is left blank.

The puzzle is sold under the trademark Flow Free by Big Duck Games ($2012$), but its lineage is older. Nikoli published essentially the same puzzle for years under the name Arukone (a contraction of aru “some” and kone “connection”), itself a relative of the long-standing Number Link puzzles by Walter Mott in $1897$. The polynomial-time complexity of the two-colour version is classical; with three or more colours the puzzle is NP-complete (Adcock et al., $2015$), making it the first in this book to be NP-complete by basic combinatorics rather than by sheer combinatorial scale.

The model in this chapter is, despite the complexity of the puzzle, strikingly compact: a colour-indicator variable per cell-colour pair, plus a degree constraint per cell-colour saying that endpoints have one same-colour neighbour and interior cells have two. The trick that makes it work is the strict “every cell must be filled” clause. Without it, paths could short-circuit through empty cells and the model would need a connectivity layer; with it, the degree constraints alone almost suffice, and a well-formed puzzle resolves uniquely.

Rules and a small instance

A Flow Free puzzle is an $n \times n$ grid with $K$ colours. Each colour $k \in \{1, \ldots, K\}$ is assigned exactly two cells, its endpoints; remaining cells are unmarked.

1. Each unmarked cell receives exactly one colour from $\{1, \ldots, K\}$.

2. For each colour $k$, the cells coloured $k$ form a single path between the two endpoints of $k$. Equivalently: each endpoint of $k$ has exactly one orthogonal neighbour of colour $k$, and every other cell of colour $k$ has exactly two.

3. Every cell is covered by some colour (the fill property).

Figure 7.1 is a $5 \times 5$ Flow Free with four colours. The endpoints are drawn as small filled disks labelled with the colour number; the puzzle is to thread a path of each colour from dot to dot, covering every cell exactly once.

The programming model

For each cell $(r, c)$ and each colour $k$, introduce a Boolean variable $x_{r,c,k} \in \{0, 1\}$ that is $1$ iff cell $(r, c)$ is coloured $k$. The model has three families of constraints.

1. Single colour per cell. For each cell, $\sum_{k} x_{r,c,k} = 1$.

2. Endpoints fixed. For each pair of endpoints $\{e_1, e_2\}$ of colour $k$, set $x_{e_1, k} = 1$ and $x_{e_2, k} = 1$.

3. Degree. For each cell $(r, c)$ and each colour $k$, if $x_{r,c,k} = 1$ then the count of $k$-coloured orthogonal neighbours equals $1$ (when $(r, c)$ is an endpoint of colour $k$) or $2$ (otherwise).

The degree constraint is reified: $\sum_{(r', c') \sim (r, c)} x_{r', c', k} = t_{r,c,k}$ holds only when $x_{r,c,k} = 1$, where $t_{r,c,k} \in \{1, 2\}$ depending on endpoint status. CP-SAT expresses this with OnlyEnforceIf; no further machinery is needed.

A note on connectivity

The degree-and-fill conditions are necessary for a valid solution but not strictly sufficient: a colour could in principle form a path between its endpoints plus a separate disjoint cycle, and every cell would still have the right degree. In practice, a well-formed Flow Free puzzle has a unique grid-filling solution and the unique solution has no separate cycles; the degree model returns it. For adversarial inputs one would add a connectivity constraint (a multi-commodity flow on the cell graph, or a position-along-the-path variable for each cell). For every puzzle in this chapter the degree model alone suffices, and we verify the result by checking each colour’s induced subgraph is connected.

A solver in twenty lines

from ortools.sat.python import cp_model

def nbrs(r, c, n):
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0 <= r+dr < n and 0 <= c+dc < n:
            yield (r+dr, c+dc)

def solve_flow(n, eps):
    """eps: dict {colour: [(r1, c1), (r2, c2)]}."""
    K = sorted(eps)
    m = cp_model.CpModel()
    x = {(r, c, k): m.NewBoolVar("")
         for r in range(n) for c in range(n) for k in K}
    for r in range(n):
        for c in range(n):
            m.Add(sum(x[(r, c, k)] for k in K) == 1)
            for k in K:
                if (r, c) in eps[k]:
                    m.Add(x[(r, c, k)] == 1)
    for r in range(n):
        for c in range(n):
            for k in K:
                same = [x[(nr, nc, k)]
                        for nr, nc in nbrs(r, c, n)]
                t = 1 if (r, c) in eps[k] else 2
                m.Add(sum(same) == t).OnlyEnforceIf(
                    x[(r, c, k)])
    s = cp_model.CpSolver()
    s.Solve(m)
    return [[next(k for k in K
                  if s.Value(x[(r, c, k)]))
             for c in range(n)] for r in range(n)]

The toy solves in about $5$ milliseconds.

A larger instance: Arukone 300

Figure 7.3 is puzzle $300$ from the janko.at Arukone archive, a $15 \times 15$ instance by ARA3 with ten colour pairs. Two of the ten pairs sit close together (the green pair occupies cells $(2, 4)$ and $(2, 10)$, on the same row); the remaining eight thread across the grid. The same solver code, called on this instance, returns the unique completion in about $90$ milliseconds.

Sources. The Numberlink puzzle was first published by Walter Mott in Tit-Bits magazine in $1897$; Nikoli rebranded a version of it as Arukone in the early $1980$s. The Flow Free mobile game by Big Duck Games ($2012$) revived the puzzle in its strict-fill form. Adcock, Demaine, Demaine, O’Brien, Reidl and Sullivan, Zig-zag Numberlink is NP-complete, Journal of Information Processing $23$ ($2015$), $239$–$245$, established NP-completeness for the version with three or more colour pairs and the all-cells-covered constraint. The hard puzzle in Figure 7.3 is Arukone $300$ from janko.at, attributed to ARA3 (numberlink.ara3.net).