Introduction

Flow Free is not just a shortest-path puzzle. Each color pair must be connected by a path, the paths cannot overlap, and the final board must cover every cell. That makes the natural algorithm a constraint-driven search with aggressive pruning, not a greedy pathfinder that solves one color at a time.

Model the Board as a Search State

A convenient representation is a grid where each cell is one of three things:

• a fixed endpoint for a color
• an empty cell
• a temporary path cell placed during search

A move extends one unfinished color by one step in one of the four cardinal directions. A state is valid only if it does not create path overlap and does not make the remaining puzzle impossible.

A small neighborhood helper is enough to support most checks:

1DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
2
3def neighbors(r, c, rows, cols):
4    for dr, dc in DIRS:
5        nr, nc = r + dr, c + dc
6        if 0 <= nr < rows and 0 <= nc < cols:
7            yield nr, nc

Backtracking Is the Core Algorithm

A naive solver often tries to connect each color with BFS or A-star and then move to the next color. That fails because a locally good path can block the only valid route for another color.

The standard exact approach is depth-first search over partial boards:

1. choose an unfinished color
2. try one legal extension move
3. reject the state immediately if it becomes impossible
4. recurse
5. undo the move if the branch fails

The solver skeleton looks like this:

1def solve(board, colors):
2    if all_paths_finished(colors) and board_filled(board):
3        return True
4
5    color = choose_next_color(board, colors)
6
7    for move in legal_extensions(board, color):
8        apply_move(board, color, move)
9        if state_is_possible(board, colors) and solve(board, colors):
10            return True
11        undo_move(board, color, move)
12
13    return False

The exact helper functions vary, but this is the overall shape.

Pruning Makes the Search Practical

Without pruning, the search tree grows too fast. The main speedups come from rejecting impossible boards early.

One strong check is reachability. If an unfinished endpoint can no longer reach its partner through empty cells, the branch is dead.

1from collections import deque
2
3def reachable(board, start, goal, color):
4    rows, cols = len(board), len(board[0])
5    q = deque([start])
6    seen = {start}
7
8    while q:
9        r, c = q.popleft()
10        if (r, c) == goal:
11            return True
12        for nr, nc in neighbors(r, c, rows, cols):
13            cell = board[nr][nc]
14            if (nr, nc) not in seen and (cell == "." or cell == color or (nr, nc) == goal):
15                seen.add((nr, nc))
16                q.append((nr, nc))
17
18    return False

Another valuable check is dead-end detection. If an empty region becomes isolated in a way that no future path can legally fill it, the branch should be discarded immediately.

Heuristics Matter

Correctness comes from backtracking. Performance comes from heuristics.

Two very useful heuristics are:

• choose the unfinished color with the fewest legal next moves
• apply forced moves immediately when an endpoint has only one valid extension

These ideas reduce branching and expose contradictions earlier. They do not change the answer, but they can make the difference between a solver that finishes and one that stalls.

Do Not Forget the Coverage Rule

A board is not solved merely because every pair of endpoints is connected. Every cell must also be filled.

This matters because a partial set of disjoint valid paths can still leave unused pockets on the board. A correct solver must check both conditions:

• all color pairs are connected
• no cells remain empty

Many first implementations miss the second rule and accept invalid “solutions.”

Greedy Solvers Usually Fail

Shortest-path logic per color is tempting because the subproblem is easy. The problem is global interaction. A path that looks best for one color may permanently cut off another pair or create empty cavities that cannot be filled later.

That is why Flow Free behaves more like a constraint satisfaction problem than a sequence of independent routing problems.

A Reasonable Development Strategy

When building a solver, start with a small board and implement one pruning rule at a time. Confirm that the solver still finds known solutions after each new optimization. That makes it much easier to trust the pruning logic.

A good progression is:

1. plain backtracking
2. endpoint reachability
3. forced moves
4. dead-end and region checks
5. better next-color ordering

This is safer than dropping every heuristic into the solver at once.

Common Pitfalls

• Solving each color independently and expecting the combined result to stay valid.
• Backtracking without reachability or dead-end pruning.
• Forgetting that a valid Flow Free solution must fill every cell.
• Processing colors in a fixed order even when one color is clearly more constrained.
• Mutating the board during recursion and failing to undo the move correctly.

Summary

• Flow Free is best modeled as a constrained search problem over complete board states.
• The core exact algorithm is backtracking, not one shortest-path pass per color.
• Reachability and dead-end checks are essential pruning tools.
• Good move ordering and forced moves improve performance dramatically.
• A valid solution must connect every color pair and fill the entire board.