Is there a well known algorithm fill in the grid given a set of points?
algorithm, graph
Solution
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.
Problem
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?