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$. Adcock et al. proved NP-completeness for the generalized strict-fill problem, in which the number of endpoint pairs is part of the input. That result does not establish a threshold at three fixed colours.

The model uses colour indicators and actual directed path edges. Each path starts at one endpoint and ends at the other; increasing positions along used edges prevent separate cycles. Same-colour cells may touch without a drawn edge between them.

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$. Each endpoint has one used edge and each other covered cell has two used edges. These are drawn edges, rather than every same-colour adjacency.

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$. Every cell has exactly one colour and endpoints are fixed. For every directed neighbouring pair $p,q$ introduce $a_{p,q,k}$, indicating a used edge of colour $k$. A used edge implies that both incident cells have that colour.

Orient each path from its first endpoint to its second. The first has one outgoing edge and no incoming edge; the second has one incoming edge and no outgoing edge. Every other occupied cell has one incoming and one outgoing edge. Unoccupied cells have neither. These degrees alone could still permit separate cycles.

For each cell and colour introduce a position $d_{p,k}$ between $0$ and $n^2-1$. Set the start position to zero and impose $d_{q,k}=d_{p,k}+1$ on every used edge. A directed cycle would require positions to increase and return to their starting value, which is impossible. In a finite graph with these degrees, every occupied cell must therefore lie on the endpoint-to-endpoint path. The return value includes the colour grid and actual edges; uniqueness must be checked on the edges as well as the colours.

A CP-SAT solver

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):
    """Return (colour grid, directed used edges).
    eps: {colour: [start, end]}, zero-based cells.
    """
    K = sorted(eps)
    cells = [(r,c) for r in range(n) for c in range(n)]
    m = cp_model.CpModel()
    x = {(r,c,k): m.NewBoolVar("")
         for r,c in cells for k in K}
    a = {(p,q,k): m.NewBoolVar("")
         for p in cells for q in nbrs(*p,n) for k in K}
    d = {(p,k): m.NewIntVar(0,n*n-1,"")
         for p in cells for k in K}
    for r,c in cells:
        m.Add(sum(x[r,c,k] for k in K) == 1)
        for k in K:
            p = (r,c); start,end = eps[k]
            incoming = [a[q,p,k] for q in nbrs(r,c,n)]
            outgoing = [a[p,q,k] for q in nbrs(r,c,n)]
            if p in (start,end):
                m.Add(x[r,c,k] == 1)
                m.Add(sum(incoming) == (p == end))
                m.Add(sum(outgoing) == (p == start))
            else:
                m.Add(sum(incoming) == x[r,c,k])
                m.Add(sum(outgoing) == x[r,c,k])
            if p == start:
                m.Add(d[p,k] == 0)
    for (p,q,k), edge in a.items():
        m.AddImplication(edge,x[p[0],p[1],k])
        m.AddImplication(edge,x[q[0],q[1],k])
        m.Add(d[q,k] == d[p,k]+1).OnlyEnforceIf(edge)
    s = cp_model.CpSolver()
    status = s.Solve(m)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError(
            "no solution: " + s.StatusName(status))
    grid = [[next(k for k in K if s.Value(x[r,c,k]))
             for c in range(n)] for r in range(n)]
    edges = {key for key,v in a.items() if s.Value(v)}
    return grid, edges

The companion checks run this model on both examples and on a $3 \times 3$ one-colour snake, which requires same-colour cells to touch without using every adjacency.

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 returns the shown completion; the companion verification record reports the fresh edge-based uniqueness check.

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, Sánchez Villaamil and Sullivan, Zig-zag Numberlink is NP-complete, Journal of Information Processing $23$ ($2015$), $239$–$245$, established NP-completeness for the version with a variable number of 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).