The Nightstar Zoo

Fred and George have a long standing rivalry between them. They both love mazes, and are always writing them for eachother. Fred, however, is much better than George at solving them, and has never been stumped yet.

Today, George is fed up. "Fred, I'm going to stump you this time. I'm gonna make the hardest maze you've ever seen. You'll have to go through trapdoors and secret passages, teleporters, and visit every room. I'll make you lost at every corner and want to quit before you pass the third branch, I will. And I won't give you any restarts either."

Fred thinks for a moment. "George, you go ahead and make that maze, and if everything you say about it is true, then I will have it done in the time that it takes to trace with the pencil."

What makes Fred so sure?

If he has to visit every room, then any room in the maze is on a correct path to the goal.

But that's not necessarily true... I can create a lot of mazes where one of the rules is that you have to visit every room and that you can't retrace your steps... and so entering a particular room at the wrong time can trap you.

Vorn

Depends on your definition of "retracing".

The tradional way of navigating a maze is to always turn in the same direction whenever you have a chance to (usually right, I'm not going to get into the reasons for that now). However this doesn't always work with multi-level mazes.

Still it's a good tip if you're ever trapped in a maze by some supervilian.

The quickest way to get to the end of any maze is to go straight through the walls. In this case, just stop through all the rooms on the way out.

Yes, that's good, but IIRC it doesn't work if the maze has some walls which aren't connected to the outside wall.

Darth has the right idea, but this isn't really the solution, just a key point. Fred is completely confident that he will make the correct choice on the first try every time he reaches a branch in the maze. Why is this?

And can you prove it?

It does work on any finite planar maze in which both the entrance and exit are on the outside wall, regardless of whether there are 'floating' walls.

Where it breaks down is A) When the exit is not on the outside of the maze (ie: in the center), and B) When the maze is nonplanar (ie: trapdoors, teleporters, or secret passages that allow two paths to cross without intersecting). In either of these cases, a loop in the maze can defeat this algorithm.

Because there are no wrong choices. There is nothing in the stated rules that say that Fred can't retrace his steps, and if he has to visit every room *and* there are branches he *must* be allowed to revisit rooms.

In short Fred probably won't choose the quickest path, but there is no way he can fail to solve it on the first try given the stated conditons.

Of course if certain rooms can be declared to be non-revisitable then it would be possible to trap Fred if a wrong choice is made.

Isn't this just one of those "Keep your left hand on the wall at all times" things? Just take the first left (or right if you prefer) at every turn. Upon hitting a dead end turn around and continue.

To defeat any loop, just take the next exit to the right from the left that lead to the trapdoor, teleporter, etc. IE, you're travelling down a previously travelled corridor. You know a teleporter is the next left, so instead of going left, take the second from the left.

In other words, where you would normally loop, don't take the first available left.

Note, <b>They both love mazes, and are always writing them for eachother</b>

If they write/draw them, then of course he'llhave it solved with the trace of a pencil...as it's with a pencil that he makes his way thru!

The original solution to this one had been mostly answered by Darth. The idea was this:

First of all, no hint was made in the boasting that there was any state to the maze besides what room you're in. This allows us to be sure that if you visit the same room twice, your potential options for the rest of the maze are identical both times. It can be assumed that the maze can be represented by a nonplanar directed graph. (I can't think of a reason this wouldn't be true, but if so, please ignore it. Fred and George did)

Most of George's boasting was extraneous information, but the key point to pick out was that George said Fred would have to visit every room. This allows us to make two more assumptions about the maze. The first assumption is that, from any vertex on the graph, there exists a path to the exit. The second assumption is that every correct path in the maze goes through every room, and that, in particular, the optimal (shortest) path goes through every room.

Given these assumptions, it can be proven that, at each vertex in the graph, there is exactly one edge leading to a vertex that has not been visited yet. (Proving so is left as an exercise to the reader... ) Fred's algorithm is to start tracing at the beginning, and at each room, simply move to the next room that doesn't have a pencil line already in it. He will trace the optimal solution to the maze.





Actually, Vorn, I don't believe that such a maze is possible without either keeping state data other than location, or by redefining "room" to include more than one vertex of the graph. (such as a single "room" with a partition and paths on both sides of the partition)

I like my answer...it just screams "Occam's Razor"