This question already has an answer here:
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.
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!