Is there a solution for this traversal problem?

Question

Say we have a matrix M x N,given two randomly specified exit and entrance,

find a path(up,down,left,right) from entrance to exit that covers each node in the matrix only once?

Answer 1

One thing you could try is something like this:

Split your matrix in two such that entrance and exit are in different partitions. Then, for each valid pair of cells that form a "bridge" over the split, recursively find whether or not there are valid paths from entrance to the cell in its partition, and from that cell's pair to exit. If none of the pairs work, then we can't find a path (because if such a path existed, it has to cross that partition eventually).

Using a small example, suppose we had

+---+---+
| A | B |
+---+---+
|   |   |
+---+---+

and split it down in the middle to give

+---+     +---+
| A |     | B |
+---+     +---+
|   | <-> |   |
+---+     +---+

with <-> being the only valid "bridge." Naming the cells in that pair "C" and "D", we then have

+---+     +---+
| A |     | B |
+---+     +---+
| C | <-> | D |
+---+     +---+

where we now find paths from A to C and from D to B. Splicing those mini paths together, we get A to C to D to B.

In the example given by Emil, no matter which way you partition that matrix, you can't get a valid pair to test, so you can immediately conclude that there is no such path.

Answer 2

This is obviously not always solvable. Say you have this matrix, where A is entrance and B exit:

+---+---+
| A |   |
+---+---+
|   | B |
+---+---+

How do you solve this?