8
Let's pretend I have the following grid. I have to connect pairs of letters. Not only the same letters have to be connected, but I must also make sure that the connecting paths don't cross each other. What's the algorithm that could tell me if it is possible to connect all the pairs without crossing paths and the shortest path?
I realize that this is a graph problem and the shortest path part could be solved using BFS. What I am not sure about is the crossing paths.
+---+---+---+---+---+---+---+---+
| A | | | B | | | | |
+-------------------------------+
| | | | | | | | |
+-------------------------------+
| | | B | | | | D | |
+-------------------------------+
| | | | | | | | |
+-------------------------------+
| | C | | | C | | | |
+-------------------------------+
| | | | A | | | | |
+-------------------------------+
| | | | | | | D | |
+-------------------------------+
| | | | | | | | |
+---+---+---+---+---+---+---+---+