TryAlgo

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

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: