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 a pathfinding game between a 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 we use 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 the path along edge.

2. For point nearest to each other, follow a direct path if there is one.

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

Answer 1

From an AI perspective, there are at least two substantially different ways to frame the Flow Free puzzle: 

• constraint satisfaction problem (CSP)

• shortest path problem. 

The former is the domain of SAT solvers and Knuth’s DLX, whereas the latter is the domain of Dijkstra’s algorithm and A* search.

At first, the blush, considering Flow Free as a CSP seems like a simpler formulation, because the constraints are so simple to state:

• Each free space must be filled in by color.

• Each filled-in cell must be adjacent to exactly two cells of the same color.

• Each dot must be adjacent to exactly one filled-in cell of the same color.

Although we could use a breadth-first search to solve the puzzle, I found that it’s significantly faster to go with the best-first search instead. The method I ended up using is kind of a poor man’s A* search in that it computes two quantities for each state x

• a cost-to-come g(x), g(x) that considers all of the moves made to get to this state; and

• a cost-to-go estimate h(x), h(x) that estimates the remaining “distance” to a goal state.

For a better understanding of the approach, you can refer the following link:

https://mzucker.github.io/2016/08/28/flow-solver.html

If you want to make your career in Artificial Intelligence then go through this video:

For the best of career growth, check out Artificial Intelligence Course and get certified.