# how to cover a point matrix with right angle lines connecting each pair of dots [duplicate]

I'll describe the problem below, I'm not sure if it's an exist algorithm problem. The problem is from a small game.

• Here is a matrix, probably with some cells blocked(couldn't pass through)
• There are several pairs of numbered points
• connect each pairs of points with right angle lines, the lines shouldn't intersect
• lines and points should cover all available places

So, how to find out the solution if the solution exists? Here is an example image.

Problem:

One solution:

I'm not sure if it could be solved by any exist algorithm, so please tell me what algorithm I should use, or give me some hint to solve it. Runnable code would be better!