Connect Flow (Backtracking Algorithm)

The aim of this challenge was to write a recursive backtracking algorithm to solve a connect flow puzzle. The aim of the game is to connect all the pairs of dots of the same colours, positioned on a 2D grid, using continuous lines. The connection lines cannot cross over each other.

Here is a fully solved connect flow grid:

In order to try to reduce the number of steps (backtracks) needed by the algorithm to solve this puzzle we have applied the following heuristics:

• Start the puzzle by calculating the taxicab distance between each pair of nodes of the same colour. Use this information to prioritise the nodes with a shorter distance. For instance on the gird above, the algorithm will focus on the brown, purple and pink lines first as these are more likely going to be connected by a short line.
• When investigating a path between two dots, at each step the algorithm can investigate 4 directions (Top, Right, Bottom, Left). The algorithm prioritises directions that would reduce the taxicab distance between the next position and the end point. (e.g. going to the right first if the end point is to the right of the current position).

Python Code

Here is the full Python code for our backtracking algorithm. Our first option is not implementing the two heuristic strategies mentioned above, whereas our second option is based on these heuristic strategies.