Reflecting Light Is Easy, Collecting It Is Not

What a mirror does

A mirror has exactly two settings, / and \. A beam arriving from a fixed side leaves by one of exactly two routes, and which one depends on nothing but that setting. That is all a mirror does.

What pre-commitment actually costs

A mirror the beam reaches twice has to serve both visits with one setting, so the visits are coupled: the choice made for the first has to suit the second. That coupling is the whole of what committing in advance costs, and it is worth measuring, because both versions of the puzzle turn out to be easy.

Allow flips while the beam is moving and the coupling vanishes. Every arrival becomes a fresh, local choice, and nothing has to agree with anything else. The question stops being “is there an assignment?” and becomes “is there a path?”, and you may as well steer the beam by hand, one bounce at a time.

The grid below is the smallest example that separates them. The beam visits the marked mirror twice, and the target is the left port.

The mid-flight version is easier than polynomial. Both of the moves the beam makes are unordered pairs. A straight run joins the two mirror sides at its ends, and a mirror’s join is a pair of its sides the beam may cross either way. Tag each side with which of the two kinds of move comes next and the question becomes plain undirected reachability, which is symmetric logspace, and by Reingold’s theorem that is plain L.

So the cost of pre-commitment is real but bounded: it takes the problem from L to P, and no further. It costs anything at all only when the beam returns to a mirror it has already used. If every mirror were visited at most once the two versions would coincide, since each choice would be used once and could be made greedily on arrival. Everything that separates them lives in the revisits.

A mirror is really a pairing

So far a mirror has been described by what it does to a beam arriving from one side. A second description is less obvious and more useful, and it is the one the algorithm needs.

A mirror does not compute anything. It pairs up its four sides. Set to / it joins west to north, and east to south. Set to \ it joins west to south, and east to north. What it can never do is join west to east, or north to south, because a mirror cannot let the beam pass straight through.

So draw the four joins a mirror is capable of. They form a square: north–west–south–east and back to north. And the two settings of the mirror are exactly the two ways of choosing a pair of opposite edges of that square.

Now, any two disjoint edges of a square are opposite edges. There is no third way to pick two joins that do not share a corner. So if a beam route ever asks one mirror for two joins that share no side, that request is automatically a legal setting, and can never be contradictory.

The whole maze is one graph

Give every mirror four ports, one per side. Two kinds of edge join them. Line edges are fixed by the layout: leave a port, follow the straight run, and see what the beam meets: another mirror’s port, a block, or the edge of the board. Turn edges are the square from the last section, and drawn on the board that square becomes a small diamond inside each mirror cell.

Step through the construction on a four-mirror board.

That leaves one step, and it completes the argument. A beam route alternates: line, turn, line, turn, and out. Line edges never share a port, so they are a matching, and a path that alternates in and out of a matching, running between two ports the matching misses, is exactly an augmenting path.

Two things are needed to make that an equivalence. A real route never uses a port twice: to do so the beam would have to run through one of a mirror’s joins in both directions, and a beam that doubles back retraces its whole path and leaves by the entrance. And any port-disjoint path can be built: the turns it makes at a mirror share no port, so by the square argument they are always one of the two legal settings. Mirrors the route misses, like D above, can be set however you like.

What the matching actually is

Being exact matters here, because the matching is not itself the list of settings. Take every port, four per mirror and sixteen here, and add two more vertices for the entry and the target. Eighteen in all. A perfect matching pairs them up, and for this board it comes out as nine edges:

Four plus five is nine, covering all eighteen. The beam’s path sits in the matching as its line edges, and the turn edges are what the path leaves over.

And that leftover is exactly where the settings are written. At mirror A the beam turns west-to-south, and the matching holds A_N–A_E, the other half of the same setting. A mirror set to \ joins W–S and E–N. The beam uses one of those and the matching takes the other. So reading a solution off is immediate: a leftover turn joining N to E means \, one joining W to N means /.

Three cases, and only the middle one is the picture people usually have:

Every case pairs up neatly, and that is what the argument needs: a perfect matching exists exactly when a legal beam route does.

So finding a solution is finding an augmenting path, and Edmonds’ algorithm has done that in polynomial time since 1965. One caveat for the fastidious: a perfect matching may differ from the line matching by some closed loops as well as by the route. Those loops are harmless: the route is the piece joining the two ports the lines missed, and that is the piece you read the settings from.

The algorithm

Four steps, all polynomial:

It also explains why so many settings solve a board that looks tightly constrained. A mirror in the plane has four sides and a pass consumes two of them, so no beam passes the same mirror more than twice, and mirrors it never reaches are unconstrained.

Three dimensions

Everything above leans on one fact: a flat mirror cannot pass the beam straight through, so its four joins form a square. In space that fails, and the puzzle stays easy anyway, for the opposite reason.

A mirror in a cube is a tilted plane with six orientations. Each swaps two axes and leaves the third alone, so it makes three joins, and one of them is always the untouched axis joining a face to the one directly opposite. Draw the six faces round a circle with opposite faces opposite, and that straight-through join is a diameter of it:

Now the step that carried the proof: any two joins sharing no corner are automatically one legal setting. That is comfortably false in space. Of the 45 ways to pick two joins sharing no face, only 18 occur together in some orientation. A route can therefore ask a mirror for a combination it cannot deliver, in 27 different ways.

The matching test therefore over-accepts in space. It records which faces a route occupies, never how the route pairs them, and legality depends on the pairing. The equivalence that settled the plane is gone, and what takes its place is a repair step the plane does not admit.

The short-cut

In space, every pair of faces is a legal join. All fifteen occur in some orientation, unlike the plane, where the two diagonals occur in none. The rest of the argument runs on that difference.

First, a bound on repeats. A mirror in a d-dimensional box has 2d faces, a visit consumes two of them, and no route uses a face twice, so a mirror admits at most d visits: two in the plane, three in space. Both bounds are attained, so the plane’s two-visit analysis does not transfer.

Suppose a route visits some mirror k times, 2 ≤ k ≤ d. Each visit asks that mirror for a join, and the mirror has one setting with which to supply all k of them. If no setting contains all k, no assignment performs that route.

So shorten it. The beam first arrived at face f and last left at face g. No route uses a face twice, so f ≠ g. Join f to g directly and discard everything in between. The k visits become one, the mirror is asked for a single join, and every pair of faces lies in some setting:

One splice per repeated mirror is enough, since each collapses all of that mirror’s visits at once. Every mirror on the shortened route then carries a single join, a single join always extends to a legal setting, and mirrors the route misses can be set arbitrarily, so the shortened route is realisable.

Why over-accepting is harmless

On the face of it the test is unsound. It hands back some port-disjoint route, not a realisable one, and nothing so far says the route it returns can be repaired. Were repairability a property of the particular matching, the algorithm would have to search among matchings.

It does not, because the splice is a construction rather than a search: wherever a mirror is revisited it is available, and its availability does not depend on the route. Three facts:

A splice removes visits and never adds one, since the route it leaves behind is a sub-route of the one it started with. A mirror visited k times collapses to a single visit in one step, by joining the first face entered to the last face left. So the total number of visits strictly decreases, the process terminates, and it terminates at a route that uses every mirror at most once. Such a route asks each of its mirrors for one join, and a single join always extends to a legal setting.

Repairability is therefore not a property of the matching: every perfect matching yields a port-disjoint route, and every port-disjoint route splices down to a realisable one. The algorithm never has to choose between matchings, and an over-accepted route is one that wants simplifying rather than rejecting.

So a realisable route exists exactly when a port-disjoint one does, which is an augmenting path, which is Edmonds again. The three-dimensional puzzle is in P as well, by the very same algorithm.

The algorithm in space

Almost the same four steps, with one extra:

Step 5 is the only thing the plane does not need. There the matching’s leftover turns name the settings directly. In space they need not: the matching can hand back a route that no orientation performs, so you shorten it first, and then it always can.

That also places the last step in the argument. For the decision problem — is this level solvable — the algorithm is finished at step 4: a perfect matching exists exactly when a solution does, and the matching's existence is all the decision needs. Step 5 is what turns a matching into the actual mirror settings, and it is what proves the harder direction, that a matching implies a solution.

Every dimension

Nothing in that argument was about three. A mirror in d dimensions is a plane whose normal points along ei ± ej: it swaps two axes and ignores the rest. So it has d(d−1) settings, each pairing the 2d faces into d joins, of which d−2 are straight-through. Counting which pairs of faces are legal joins:

From three up the answer is always all of them — all d(2d−1) pairs, in d dimensions — and that is the only thing the short-cut needs. So the argument runs unchanged in every dimension above two, and the puzzle is in P for all of them: the same graph, the same matching, the same algorithm, just with 2d ports per mirror instead of four. The plane is the exception, and it is in P for its own separate reason.

Theorem 1. With no orbs, the puzzle is in P for every fixed dimension. A board is solvable exactly when its port graph has a perfect matching, and Edmonds’ algorithm finds one in polynomial time. In the plane the matching names the settings outright. From three dimensions up it need not, and the short-cut turns whatever route it hands back into one that some assignment performs.

The two cases are easy for opposite reasons. In the plane a mirror is too restricted to cause trouble: it cannot pass a beam straight through, so any two compatible-looking joins really are compatible. In space it is too permissive: it reaches every face from every other, so a route that returns to a mirror can always be spliced into one that does not. A hard version would need a mirror between the two extremes, at which a repeat visit is both possible and constrained.

Orbs

The last section ended on what a hard version of this puzzle would need: a mirror falling between the flat one and the one in space. There is a way to get there without touching the mirrors at all. Leave the physics exactly as it is, in whatever dimension you like, and change what counts as solved.

An orb is a cell the beam has to pass through. Reaching the exit is no longer enough: collect every orb on the way, or the level is unsolved. Nothing else about the game changes.

That is enough to break both proofs. The matching argument works because it needs only some port-disjoint route, so it is free to hand back whichever one falls out of the algorithm. It cannot be told to prefer a route through particular cells, and the leftover turns it returns may well park an orb on one of the stray loops rather than on the path. The short-cut in space fails for the same reason from the other side: it works by deleting a loop, and the loop may be the only part of the route that collects something.

The router

The argument is easiest in the plane, so that is where it is made, and it carries upward: a flat instance is a cube one layer deep, and a cube is a four-dimensional box one layer deep.

Take a mirror and wall one of its four sides — say the south one. A join is usable only when both of its sides are open, so the two joins touching the south side are gone, and each setting is left with exactly one:

Call this a router. Two properties matter, and both come straight from the figure above.

(R1) A router has a distinguished side — north, in the orientation drawn — and a binary choice of which other side to attach it to. Call the distinguished side its stem and the other two its branches, since every passage runs between the stem and one branch.

(R2) No setting joins west to east. A flat mirror cannot pass a beam straight through, so the two side ports cannot be connected to each other under any setting. This is the property the plane has and space does not, and the construction rests on it.

A run of empty cells carries the beam straight across, and that run is one line. To bend it, wall two adjacent sides of a mirror: only one join survives, so the mirror becomes a forced turn. A chain of lines joined by such turns is a wire.

The vertex gadget

Stack three cells in a column: a router with its south side walled, an empty cell holding an orb with its west and east sides walled, and a router with its north side walled. Write in₁, in₂ for the two open sides of the lower router and out₁, out₂ for those of the upper one.

Lemma 1. Any beam entering the gadget at in₁ or in₂ leaves at out₁ or out₂, crossing the orb. No beam traverses the gadget without crossing the orb, and the gadget admits at most one traversal.

Each part follows from the two properties. By (R1) the lower router's two usable joins both contain its north side, so a beam entering at either in-port leaves upward into the orb cell. That cell is empty and walled east and west, so its only straight crossing is the vertical one, and it leaves at the top into the upper router, which by (R1) again sends it out one of its two sides. For the second claim, a traversal that missed the orb would have to join in₁ to in₂, and (R2) says no setting does that. For the third, a crossing of the orb cell consumes both its north and south sides, and a beam uses each side of a cell at most once, so there is no second crossing. □

In space the second claim fails: a mirror there does join one pair of its faces straight through, so the gadget needs the orb requirement to rule that out. In the plane the geometry rules it out, and the orbs are free to do the one job the reduction actually needs them for.

The reduction

Reduce from directed Hamiltonian path: given a digraph G = (V, E) and vertices s, t, is there a directed path from s to t using every vertex exactly once? This is NP-complete, and remains so when every vertex has in-degree and out-degree at most two, even on planar digraphs. The bound is what lets a gadget with two in-ports and two out-ports suffice.

Given such an instance, first delete every edge into s and every edge out of t. No Hamiltonian s–t path uses those, so the answer is unchanged, and it leaves both of s’s in-ports and both of t’s out-ports free for the beam to enter and leave by. Then build a maze:

The walling in step 4 is not cosmetic. Were the leftover cells open, a router set the wrong way could throw the beam into the gap, and if it met another wire there the route could pass from one wire to another without crossing a gadget — a solution corresponding to no path in G. Walled, the beam travels only along wires, and every wire corner has two open sides and therefore one usable setting, so the only free choices left in the maze are the 2|V| router settings.

Wires may cross. A crossing happens on an empty cell, where one wire passes west-to-east and the other north-to-south. Those use disjoint pairs of sides, so both passes are available and neither disturbs the other. The embedding therefore does not need G to be planar, and the layout is a matter of bookkeeping: give each vertex four columns, one per port, space the vertices so their columns do not meet, and give each edge its own row above the gadget row. A column then belongs to one port of one vertex and a port carries one edge, so no two wires ever want the same corner.

The maze has |V| gadgets and |E| wires, in O(|V|) columns and O(|E|) rows, so it has O(|V||E|) cells and is written down in time polynomial in the size of G.

Correctness

Lemma 2. If G has a Hamiltonian s–t path then the maze is solvable.

Let the path be s = v₁, …, v_n = t. At each v_i, set the lower router to join the orb to the in-port carrying the wire for (v_i−1, v_i) — the entry, for v₁ — and the upper router to join the orb to the out-port carrying (v_i, v_i+1), or the exit for v_n. Set every wire corner to its one usable setting, and unreached mirrors are arbitrary. The beam then runs from the entry through v₁, along the wire for the first edge, through v₂, and so on to the exit, crossing every orb. No cell is used twice: the path visits each vertex once and each edge at most once, and distinct wires share only crossing cells, which they use on different axes. □

Lemma 3. If the maze is solvable then G has a Hamiltonian s–t path.

Fix a solution. Every orb is collected, so every gadget is traversed, and by Lemma 1 each is traversed exactly once. Write v₁, …, v_n for the gadgets in the order the beam crosses their orbs, which is therefore a permutation of V. The beam enters at an in-port of s, so v₁ = s. By Lemma 1 the beam leaves each gadget at an out-port, and every wire runs from an out-port to an in-port, so it arrives at the next gadget through an in-port and the same argument applies again. Between crossing the orb of v_i and that of v_i+1 the beam travels one wire, and that wire is the edge (v_i, v_i+1) of G. Finally the beam leaves by the exit, which only the out-port of t reaches, so v_n = t. The sequence is a Hamiltonian s–t path. □

The construction is polynomial and the two lemmas are the two directions, so laser maze with orbs is NP-hard in the plane, and hence in every dimension above it.

Membership in NP is the other half of the claim. The certificate is an assignment of orientations to the mirrors, and the verifier simulates the beam under that assignment, checking that it leaves by the target port and that every orb lies on the route. The simulation terminates because a beam never enters the same cell heading the same way twice, which bounds it by four steps per cell in the plane and 2d of them in d dimensions, so the check is linear in the size of the board.

Theorem 2. With orbs, the puzzle is NP-complete in every dimension from two up. Hardness is by reduction from directed Hamiltonian path with in-degree and out-degree at most two, and membership in NP is by simulating the beam under a proposed assignment of orientations. One rule about which cells the beam must touch carries the problem the whole way from Theorem 1, and because the argument is made in the plane it holds in space and above, where a flat maze is only a box one layer deep.

The degree-bounded form of the source problem rests on Plesník (Information Processing Letters 8, 1979), who proved the Hamiltonian cycle problem NP-complete for planar digraphs whose vertices all have in-degree and out-degree at most two. The path version used here follows by splitting one vertex into a source carrying its out-edges and a sink carrying its in-edges, which leaves both the planarity and the degree bounds intact.

Earlier the question was what a hard version would need: a mirror whose settings can be wired into a choice, and a requirement that stops the beam taking the shortest route to the exit. Both came without altering the mirror. Walling one side does the first — a free choice between two turns becomes a switch with a common port. Requiring the orbs does the second, since otherwise the beam need only reach the exit.

The mirrors are unchanged, in unchanged dimensions. All that is new is a set of cells the beam has to visit, and the hardness that follows has nothing to do with reflection. It is the difficulty that makes Hamiltonian path hard in the first place: one route, and every required vertex on it.

When the order is given

The game will number the orbs for you. Turn the hint on and each one shows its place in the order the intended solution collects them. What if that order came with the level, as part of the input? Is the puzzle still hard?

The reduction just given cannot answer that, because there the order is the answer. Its orbs are the vertices of G, and the sequence the beam collects them in is the Hamiltonian path. Given the sequence, all that remains is to check each consecutive pair is an edge, which takes time linear in G.

The order does not give the matching algorithm back either. That argument needed two things and the order supplies neither. A matching returns whichever port-disjoint route falls out, and there is no way to ask it for one that goes through particular cells. The short-cut runs into the same trouble. It works by throwing away a detour, and the detour may be the only part of the route that reaches an orb.

There is a limit to what a hint like this can be worth. Given any algorithm for the ordered puzzle, running it on all k! orders solves the unordered one, so the ordered version is at least as hard, up to a factor of k! and no more. Once k grows with the board that factor stops being polynomial, and the reduction above is exactly that case, so nothing yet rules out the ordered puzzle being easy. The rest of this section shows that it is not, by reducing satisfiability to it.

Fan-out without copying

A satisfiability reduction has to let one variable be read by every clause that mentions it, and that is awkward here, because a beam cannot copy itself. Reflection is reversible, so beams never merge and never split.

What it can do is get in its own way. The route is one continuous path and it never runs down the same line twice, because a beam that doubles back retraces its steps and leaves by the entrance. So a line the route uses early is closed to it later.

That is enough to record a bit. Lay a long chain of lines and let the route either run its whole length or keep off it altogether. Call the chain a rail. Running the rail uses up every line along it at once, so one decision, taken in one place, can be read at as many places as the rail is long, and nothing has been copied.

The construction

Reduce from 3-satisfiability: given a Boolean formula in conjunctive normal form with three literals per clause, is there an assignment making every clause true? Every cell not named below is walled, so the beam travels only along the wires laid for it.

The lines shared with the literal x sit on the rail standing for x being false, so one of them is free exactly when the literal is true. A variable occurring five times gets five of them spaced along that rail, and running the rail closes all five at once. Nothing bounds how often a variable may occur. The reduction from Hamiltonian path needed a degree bound because a vertex gadget has four ports and no more, but a rail has no such ceiling: it is made as long as the formula asks, and one passage spends the whole of it.

The variable gadget

The beam reaches x’s gadget along the backbone and meets a router. It leaves by one branch or the other, runs that rail from end to end, and comes back to the backbone through a second router that merges the two rails again. Which branch it took is the value of x. It cannot take both and it cannot take neither, because a router carries one passage and the backbone gives it nowhere else to go.

The clause gadget

Take the clause (x ∨ ¬y ∨ z). Its gadget has to pass the beam exactly when one of those three literals is true, and it comes in three parts.

Choosing a literal. One router offers two ways on, so two routers in a row offer three. The beam arrives from the backbone at the first router’s stem and leaves either straight onto the wire for x, or onward to a second router, which puts it on the wire for ¬y or the wire for z.

Crossing. Each of the three wires runs to the shared line belonging to its own literal and crosses it, in at one end and out at the other. The wire for x meets a line on x’s false rail, the wire for ¬y meets one on y’s true rail, and the wire for z meets one on z’s false rail.

Merging. Two more routers put the three wires back together, since a router taken the other way carries either branch to its stem, and the beam rejoins the backbone.

So the gadget passes exactly when the literal it was pointed at is true. Say that is x. If x is true the beam never ran x’s false rail, the line is untouched, and the crossing works. If x is false the rail was run end to end, both ends of the line are already used, and the beam turns aside into a wall and is absorbed.

What it does not get to do is back out and try ¬y instead. Every mirror is set before the beam is fired, so the two routers are a choice made by whoever sets the board, not a search the beam carries out. A setting that takes the beam through the gadget therefore exists exactly when at least one of the three literals is true, which is what the clause asks for.

Why the order gives nothing away

Every orb sits on the backbone, in the order it is laid out, so every solution of every instance collects them in the same sequence. That sequence can be written down from the formula without solving anything, and it is the same whether the formula is satisfiable or not. A solver handed it learns nothing about the answer.

Correctness

Each backbone line has a router stem at either end, and crossing a line spends both of its ports, so a beam that crosses one comes out inside the gadget on the far side. There is nowhere else for it to go, and both halves of the argument follow from that.

Lemma 4. In any solution the beam runs each variable’s chosen rail from end to end, so the rails taken record a consistent assignment.

A rail’s only exits along its length are the lines it shares, and leaving by one puts the beam on a clause wire, which delivers it to a backbone line in the clause half of the board. Crossing that line collects an orb standing later in the order than the one the beam still owes, so the route is rejected. If instead the wire meets a router set against it the beam is absorbed, which is no solution either. Every rail is therefore run whole. One of the two is run at each variable, never both and never neither, since the selector is a router and the backbone gives the beam nowhere else to go. □

Lemma 5. In any solution, every clause has a literal that the assignment of Lemma 4 makes true.

The line before a clause gadget carries an orb, so it is crossed, and by the observation above the beam is then inside that gadget. Its entry router forces the beam onto one of the three literal wires, and each wire runs across the line it shares with that literal’s rail. That line is passable only if the rail was left untouched, which by Lemma 4 is exactly the case in which the literal is true. □

The other direction is the construction read forwards. A satisfying assignment says which rail to take at each variable and which literal to use at each clause, and the beam then runs the backbone and collects the orbs in the order they are numbered. The board has one gadget per variable and per clause and wires of polynomial length, so it is written down in polynomial time. Membership in NP is as before, the certificate being an assignment of orientations and the verifier a simulation of the beam, which here reads off the sequence in which the orbs are crossed and compares it with the one the input names. □

One orb in the layout does nothing but separate the variable half of the backbone from the clause half, and it is there for the argument rather than for the board. Lemma 4 needs every orb in the clause half to stand later than every orb in the variable half, and without the separator that holds everywhere except at the join between the two, where leaving the last variable’s rail puts the beam on a line carrying the very orb it still owed. The separator removes the exception.

The embedding is explicit. Each variable takes two bands of four rows, one for each of its rails, with the selector and the merger side by side in the left margin, which keeps the backbone local rather than sending it across the board twice per variable. Each clause takes a fixed block of columns carrying its four routers together with the three lines its literals share, and its wires reach those lines from below, crossing the rails on empty cells, which costs nothing because the two wires use disjoint pairs of a cell’s sides. A variable therefore adds a constant number of rows and a clause a constant number of columns, so for n variables and m clauses the board is O(n + m) cells on a side.

Theorem 3. The puzzle stays NP-complete in every dimension from two up when the order the orbs must be collected in is given as part of the input. Hardness is by reduction from 3-satisfiability, and membership in NP is again by simulating the beam under a proposed assignment, the verifier now also checking that the orbs arrive in the given order. The hint prunes the search without changing the complexity.

Theorem 3 does not subsume Theorem 2. Dropping the order only ever adds solutions, since a route that collects the orbs in the given order collects them in any case, so a board unsolvable in one particular order may be solvable in some other. These boards are exactly that case. Lemma 4 is the only place the order is used, and it carries real weight: without it the beam may leave a rail through one of its shared lines, reach the clause half early, and still arrive at the exit having collected everything in some other sequence. The unordered puzzle has to be settled on its own terms, which is what Theorem 2 does, so neither result is a corollary of the other.

How many orbs there are is a separate question. This construction spends one per variable and one per clause, so it says nothing about a board carrying only a handful. Take the number of orbs k as a parameter. At k = 0 the puzzle is the one Theorem 1 settles, and so in P, and whether it is fixed-parameter tractable in k or W[1]-hard, the parameterised counterpart of NP-hard, is open. Nothing here settles even whether it is in P for each fixed k. The k! bound ties the two variants together in one direction only. It is an FPT-reduction from the unordered puzzle to the ordered one, so an FPT algorithm for the ordered version would give one for the unordered, and W[1]-hardness of the unordered version would carry up to the ordered. The converse is not available, for the same reason Theorem 3 does not subsume Theorem 2.