# Mirror maze

Given a grid with two openings and two sided mirrors in some grid cells, find an orientation for the mirrors at 45 or -45 degrees, such that a laser beam entering one opening would be reflected all the way to the second opening.

## An \( O(n^2) \) algorithm

We use the following graph representation for this problem. Every mirror *a* generates up to 4 vertices, one for each direction *up, left, down, right*. If some mirror *b* is reachable from *a* in direction *d* then there is a vertex *(a,d)* and by symmetry a vertex *(b,inv(d))* — where the *inv* function inverts the direction — and these vertices are connected by an edge. In addition vertices *(a,d)* and *(a,e)* are connected by an edge if *d* and *e* are adjacent directions. This construction is completed with a vertex for each of two openings. Each opening vertex is connected to the reachable mirror (if any). The opening vertices are connected together by an edge, or — variant of the graph model — connected each to an additional vertex. We distinguish two kind of edges: (i) horizontal or vertical ones and (ii) diagonal or anti-diagonal ones.

We claim that the graph has a perfect matching if and only if the mirror maze instance has a solution. The interpretation of a matching is the following. A vertical or horizontal edge in the matching means that the laser does not follow this trajectory. A diagonal or anti diagonal edge in the matching, say *((a,d),(a,e))*, means that the laser reflects on the mirror *a* without however distinguishing the case that the laser enters *a* from direction *d* and leaves in direction *e* or the opposite case. Note that if there are two reflections happening on a mirror then these are not conflicting and there is a unique corresponding mirror position.

The algorithm consists of

- building the graph model,
- creating a near perfect matching, consisting of all horizontal and vertical edges. This corresponds to the complete absence of the laser beam.
- tries to build a perfect matching, by searching for a single alternating augmenting path,

This last step is hard to implement as it needs Edmond’s blossom algorithm.

## Example

## Note

The mirror maze problem can be solved with backtracking. Such a solution is of course not running in polynomial time in the worst case, but seems to pass all the tests and is quite easy to implement. But such a solution is cheating, wouldn’t you agree ?

## References

Most available implementations of Edmond’s blossom algorithm are a bit long (who can blame?), but the following by David Eppstein is quite elegant: