Flow Free

The app gives a square grid with a few pairs of coloured dots. Each pair must be joined by a path of its colour, running cell to cell along rows and columns, and the paths together must fill the board: every cell carries exactly one colour, and no two paths cross. It is one of the most downloaded puzzles there is, a hundred million installs and more, and it is a clean instance of a problem the rest of operations research knows well, a flow through a network, dressed up in colour.

A grid full of paths

Strip the colours back to their structure and a solved board is a partition of the cells into paths, one path per colour, each running between that colour’s two dots and covering some of the cells, all the cells used between them. So give every cell a colour variable and ask, of each cell, how many of its four neighbours share its colour. Along a path an interior cell has exactly two same-colour neighbours, the one behind and the one ahead; a dot, sitting at the end of its path, has exactly one. That single count, two for an ordinary cell and one for a dot, is most of the puzzle.

It is not quite all of it. The degree counts are equally happy with a path between the two dots and a separate closed loop of the same colour floating elsewhere, since every cell of a loop also has two same-colour neighbours. Loops are the one thing the counts cannot see, and forbidding them is the crux. The fix is the idea that rules out subtours in the travelling salesman problem: root each colour at one of its dots and hang the rest of its cells off it as a tree, by giving every cell a distance and insisting that each non-root cell has exactly one neighbour of its colour one step nearer the root. A floating loop has no cell at distance zero and no way to count down to one, so it cannot survive. With loops gone, the degree counts leave exactly one path per colour.

Variables

For an $m \times n$ board, every cell $(i, j)$ carries a colour and a distance, $$\mathrm{col}_{ij} \in \{1, \ldots, Q\}, \qquad \mathrm{dist}_{ij} \in \{0, \ldots, mn\},$$ for $Q$ the number of colours; the two dots of colour $k$ are fixed to colour $k$, and one of each pair is named the root.

Constraints

For neighbouring cells $c$ and $d$ a Boolean $\ell_{cd}$ records whether they share a colour. Each dot has one same-colour neighbour and each other cell has two; and each non-root cell has exactly one same-colour neighbour one nearer the root: $$\sum_{d \sim c} \ell_{cd} = \begin{cases} 1 & c \text{ a dot} \\ 2 & \text{otherwise,} \end{cases} \qquad \sum_{\substack{d \sim c \\ \mathrm{col}_d = \mathrm{col}_c \\ \mathrm{dist}_d = \mathrm{dist}_c - 1}} 1 = 1 \quad (c \text{ not a root}),$$ with the root of each colour fixed at distance zero. There is nothing to minimise; any board satisfying these is a solution.

A solver

from ortools.sat.python import cp_model

def solve_flow(rows, cols, endpoints):
    Q = len(endpoints)
    cells = [(i, j) for i in range(rows) for j in range(cols)]
    def nbrs(i, j):
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if 0 <= i + di < rows and 0 <= j + dj < cols:
                yield (i + di, j + dj)
    m = cp_model.CpModel()
    col = {c: m.NewIntVar(1, Q, "") for c in cells}
    dist = {c: m.NewIntVar(0, rows * cols, "") for c in cells}
    roots, ends = set(), set()
    for k, (r, t) in endpoints.items():
        m.Add(col[r] == k)
        m.Add(col[t] == k)
        roots.add(r)
        ends |= {r, t}
    link = {}
    for c in cells:
        for d in nbrs(*c):
            if c < d:
                b = m.NewBoolVar("")
                m.Add(col[c] == col[d]).OnlyEnforceIf(b)
                m.Add(col[c] != col[d]).OnlyEnforceIf(b.Not())
                link[c, d] = link[d, c] = b
    for c in cells:  # a dot has one neighbour, a path cell two
        deg = sum(link[c, d] for d in nbrs(*c))
        m.Add(deg == (1 if c in ends else 2))
    for c in cells:  # root a tree at each colour's first dot
        if c in roots:
            m.Add(dist[c] == 0)
        else:
            preds = []
            for d in nbrs(*c):
                p = m.NewBoolVar("")
                m.Add(col[d] == col[c]).OnlyEnforceIf(p)
                m.Add(dist[d] == dist[c] - 1).OnlyEnforceIf(p)
                preds.append(p)
            m.Add(sum(preds) == 1)
    s = cp_model.CpSolver()
    s.Solve(m)
    out = []
    for i in range(rows):
        out.append([s.Value(col[i, j]) for j in range(cols)])
    return out

A board

Here is a six-by-six board with five colours. Each colour’s two dots are shown as its number, and the empty cells carry a dot: $$\begin{array}{cccccc} \cdot & \cdot & \cdot & \cdot & 5 & \cdot \\ 3 & 2 & 1 & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & 5 & 3 & \cdot \\ \cdot & 4 & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 2 & \cdot & \cdot & \cdot & 4 & 1 \end{array}$$ The solver joins each pair and fills the board, one way only: $$\begin{array}{cccccc} 3 & 3 & 3 & 3 & 5 & 5 \\ 3 & 2 & 1 & 3 & 3 & 5 \\ 2 & 2 & 1 & 5 & 3 & 5 \\ 2 & 4 & 1 & 5 & 5 & 5 \\ 2 & 4 & 1 & 1 & 1 & 1 \\ 2 & 4 & 4 & 4 & 4 & 1 \end{array}$$ Reading a colour off the grid traces its path: colour $1$ runs from its dot at $(1, 2)$ down the third column and along the bottom to $(5, 5)$, while colour $3$ wraps the top-left in a long hook. A sweep for other solutions finds none.

The board sits in a paper that models six smartphone apps as integer programs, and Flow Free is the richest of them, the one that reaches past placement and counting into network flow. It is the puzzle elsewhere called Numberlink, and the distance trick that kills its loops is the same device, due to Miller, Tucker, and Zemlin, that keeps a salesman’s tour in one piece.

Sources. Flow Free, and its treatment as a flow on a grid network, is one of six smartphone puzzles modelled by Sönke Hartmann, Puzzle—Solving Smartphone Puzzle Apps by Mathematical Programming, INFORMS Transactions on Education volume $18$, number $2$ ($2018$), pages $127$–$141$, whose model is a multi-commodity flow with the subtour-elimination constraints of C. E. Miller, A. W. Tucker, and R. A. Zemlin, Integer Programming Formulation of Traveling Salesman Problems, Journal of the ACM volume $7$ ($1960$), pages $326$–$329$; the colour-and-distance form used here is an equivalent reading of the same idea. The puzzle is the pencil game Numberlink, of Nikoli and earlier Dudeney lineage. The six-by-six board and its unique solution are the present chapter’s, generated as an induced-path cover and checked for uniqueness by the model above. The companion Thermometer puzzle from the same paper is the subject of the preceding chapter.