Is there a well known algorithm fill in the grid given a set of points?

Question

I saw this game here Flow, it looks quite interesting.

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

Given a set of pairs (x, y), is there an algorithm to solve the puzzle, i.e. fill in the whole grid (assuming there is a solution) that I'm not aware of?

Answer 1

This is a very specific instance of the global routing problem. Global routing is a well studied problem in VLSI CAD (where one needs to route millions of nets in an integrated circuit). The problem is NP-complete and can be solved in many ways depending upon the tradeoff you need between runtime and quality. Following wiki is a good starting point:

https://en.wikipedia.org/wiki/Routing_(electronic_design_automation)

Paper here gives a survey of various techniques:

http://dropzone.tamu.edu/~jhu/publications/HuIntegration01.pdf

Bear in mind that the pointers I had given typically try to solve a far more complex version of the problem you had stated. Never-the-less, the mathematical concepts remain the same.