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: enter image description here

One solution: enter image description here

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!


Browse other questions tagged or ask your own question.