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.
Vorn the Unspeakable wrote:
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.
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)