Algorithm for solving Flow Free Game

Question

I recently started playing Flow Free Game.

Connect matching colors with pipe to create a flow. Pair all colors, and cover the entire board to solve each puzzle in Flow Free. But watch out, pipes will break if they cross or overlap!

I realized it is just path finding game between given pair of points with conditions that no two paths overlap. I was interested in writing a solution for the game but don't know where to start. I thought of using backtracking but for very large board sizes it will have high time complexity.

Is there any suitable algorithm to solve the game efficiently. Can using heuristics to solve the problem help? Just give me a hint on where to start, I will take it from there.

I observed in most of the boards that usually

1. For furthest points, you need to follow path along edge.
2. For point nearest to each other, follow direct path if there is one.

Is this correct observation and can it be used to solve it efficiently?

Answer 1

Reduction to SAT

Basic idea

1. Reduce the problem to SAT
2. Use a modern SAT solver to solve the problem
3. Profit

Complexity

The problem is obviously in NP: If you guess a board constellation, it is easy (poly-time) to check whether it solves the problem.

Whether it is NP-hard (meaning as hard as every other problem in NP, e.g. SAT), is not clear. Surely modern SAT solvers will not care and solve large instances in a breeze anyway (I guess up to 100x100).

Literature on Number Link

Here I just copy Nuclearman's comment to the OP:

Searching for "SAT formulation of numberlink" and "NP-completeness of numberlink" leads to a couple references. Unsurprisingly, the two most interesting ones are in Japanese. The first is the actual paper proof of NP-completeness. The second describes how to solve NumberLink using the SAT solver, Sugar. –

Hint for reduction to SAT

There are several possibilities to encode the problem. I'll give one that I could make up quickly.

Remark

j_random_hacker noted that free-standing cycles are not allowed. The following encoding does allow them. This problem makes the SAT encoding a bit less attractive. The simplest method I could think of to forbid free-standing loops would introduce O(n^2) new variables, where n is the number of tiles on the board (count distance from next sink for each tile) unless one uses log encoding for this, which would bring it down to O(n*log n), possible making the problem harder for the solver.

Variables

One variable per tile, piece type and color. Example if some variable X-Y-T-C is true it encodes that the tile at position X/Y is of type T and has color C. You don't need the empty tile type since this cannot happen in a solution.

Set initial variables

Set the variables for the sink/sources and say no other tile can be sink/source.

Constraints

1. For every position, exactly one color/piece combination is true (cardinality constraint).
2. For every variable (position, type, color), the four adjacent tiles have to be compatible (if the color matches).

I might have missed something. But it should be easily fixed.

Answer 2

I suspect that no polynomial-time algorithm is guaranteed to solve every instance of this problem. But since one of the requirements is that every square must be covered by pipe, a similar approach to what both people and computers use for solving Sudoku should work well here:

1. For every empty square, form a set of possible colours for that square, and then repeatedly perform logical deductions at each square to shrink the allowed set of colours for that square.
2. Whenever a square's set of possible colours shrinks to size 1, the colour for that square is determined.
3. If we reach a state where no more logical deductions can be performed and the puzzle is not completely solved yet (i.e. there is at least one square with more than one possible colour), pick one of these undecided squares and recurse on it, trying each of the possible colours in turn. Each try will either lead to a solution, or a contradiction; the latter eliminates that colour as a possibility for that square.

When picking a square to branch on, it's generally a good idea to pick a square with as few allowed colours as possible.

[EDIT: It's important to avoid the possibility of forming invalid "loops" of pipe. One way to do this is by maintaining, for each allowed colour i of each square x, 2 bits of information: whether the square x is connected by a path of definite i-coloured tiles to the first i-coloured endpoint, and the same thing for the second i-coloured endpoint. Then when recursing, don't ever pick a square that has two neighbours with the same bit set (or with neither bit set) for any allowed colour.]

You actually don't need to use any logical deductions at all, but the more and better deductions you use, the faster the program will run as they will (possibly dramatically) reduce the amount of recursion. Some useful deductions include:

1. If a square is the only possible way to extend the path for some particular colour, then it must be assigned that colour.
2. If a square has colour i in its set of allowed colours, but it does not have at least 2 neighbouring squares that also have colour i in their sets of allowed colours, then it can't be "reached" by any path of colour i, and colour i can be eliminated as a possibility.

More advanced deductions based on path connectivity might help further -- e.g. if you can determine that every path connecting some pair of connectors must pass through a particular square, you can immediately assign that colour to the square.

This simple approach infers a complete solution without any recursion in your 5x5 example: the squares at (5, 2), (5, 3), (4, 3) and (4, 4) are forced to be orange; (4, 5) is forced to be green; (5, 5) is also forced to be green by virtue of the fact that no other colour could get to this square and then back again; now the orange path ending at (4, 4) has nowhere to go except to complete the orange path at (3, 4). Also (3, 1) is forced to be red; (3, 2) is forced to be yellow, which in turn forces (2, 1) and then (2, 2) to be red, which finally forces the yellow path to finish at (3, 3). The red pipe at (2, 2) forces (1, 2) to be blue, and the red and blue paths wind up being completely determined, "forcing each other" as they go.