One solution uses the coins to implement a well-known graph algorithm called depth-first search. To simplify the description of how it works, let us assume that each room has at least two corridors out of it. Let us call the first time you traverse a corridor an advance, and the second time a retreat.

If you advance from end A to end B of a corridor, place a coin tails up by the doorway at A and a coin heads up by the doorway at B. If you later retreat from B to A, turn the coin at doorway B over so that it is a tails.

Observe the following protocol:

• If you advance to a room that already has coins in it, retreat immediately through the corridor you used to get there.

• If you advance to a room that has no coins in it, advance through a different corridor out of the room.

• If you retreat to a room that has unmarked corridors, advance through one of them.

• If you retreat to a room where all corridors are marked, retreat through the unique corridor that is marked with heads.

Figure out why the algorithm works; understanding why this is so will help you solve this week's problem.