It appears I won

Well, John tells me I won the Ninth MSO World Programming Contest, held in September, 2000. Below, I've included links to my source code, as well as a brief description of my algorithm.

Use the Source, Luke

These snippets of code are hereby made available under the GNU General Public License. This means you're free to download, compile, and use this software however you like. If you incorporate changes into this code, or you incorporate this code into another project, and you choose to redistribute the result, you must redistribute that code under the GPL. The GPL License only applies to this source code directly. If you reimplement these ideas yourself in your own code, the resulting code is unrestricted.

A Quick Explanation of the Algorithm

The maze solver uses a breadth-first search of the maze in order to find the shortest path from the starting point to the ending point. The breadth-first traversal is a queue-oriented algorithm that is at its heart quite simple. The queue holds a list of maze locations, and the algorithm works on the contents of the queue.
The algorithm starts by seeding the queue with a single element which corresponds to the starting position in the maze. (Actually, I use the first blank position to the right of the 's' in the maze, as the 's' is actually "outside" the maze in my conceptual model of the maze.) This initial position is marked in the map as "visited by moving right" (meaning, I was moving to the right when I moved into this position).
The "main loop", if you will, is a simple loop which operates on the top element of the queue. The loop withdraws the head of the queue, and then determines whether it is possible to exit by moving down, left, right, or up. For the purpose of this loop, a given direction is legal if that direction has an open walkway that has not been previously visited. For each viable exit direction, the corresponding position is marked as "visited by moving whatever direction", and that position is inserted at the tail of the queue.
The algorithm iterates until either the final position is found, or the queue goes empty. If the queue goes empty, the maze has no solution. If the final position is found, we report our answer by retracing our steps. As you may recall, the main loop has marked each location according to the direction moved to enter that location. Retracing at this point is trivial.
The "alphabetical order" requirement for equal-length paths was met by exploring maze exits in alphabetical order -- down, left, right, up. By doing this, we guarantee that alphabetically-earlier paths will be evaluated earlier than than other paths, and will thus "lock out" the other equal-length paths by visiting the squares first.
At this point, some pictures may be useful.

A Quick Example Maze

Initially, we start off with a blank maze. Queue: Empty.
We move to the "Right" out of the starting position. We add [0, 2] to the tail of the queue, and mark [0, 2] with an R. Queue: { [0, 2] }
We draw [0, 2] from the head of the queue. We are only able to move Right into [1, 2]. We add [1, 2] to the tail of the queue, and mark [1, 2] with an R. Queue: { [1, 2] }
We draw [1, 2] from the head of the queue. We can move Down into [1, 3]. We add [1, 3] to the tail of the queue and mark [1, 3] with a D. Queue: { [1, 3] }
We can also move Up from [1, 2] into [1, 1]. We add [1, 1] to the tail of the queue and mark [1, 1] with a U. (Notice that this ordering will become important later.) Queue: { [1, 3], [1, 1] }
We draw [1, 3] from the head of the queue. We can only move Down into [1, 4]. We add [1, 4] to the tail of the queue and mark [1, 4] with an D. Queue: { [1, 1], [1, 4] }
We draw [1, 1] from the head of the queue. We can only move Right into [2, 1]. We add [2, 1] to the tail of the queue and mark [2, 1] with an R. Queue: { [1, 4], [2, 1] }
We draw [1, 4] from the queue. We can move Down into [1, 5]. We add [1, 5] to the tail of the queue and mark [1, 5] with a D. Queue: { [2, 1], [1, 5] }
We can also move Right from [1, 4] into [2, 4]. We add [2, 4] to the tail of the queue and mark [2, 4] with an R. Queue: { [2, 1], [1, 5], [2, 4] }
We draw [2, 1] from the queue. We can only move Right into [3, 1]. We add [3, 1] to the tail of the queue and mark [3, 1] with an R. Queue: { [1, 5], [2, 4], [3, 1] }
We draw [1, 5] from the queue. We can only move Down into [1, 6]. We add [1, 6] to the tail of the queue and mark [1, 6] with a D. Queue: { [2, 4], [3, 1], [1, 6] }
We draw [2, 4] from the queue. We can only move Right into [3, 4]. We add [3, 4] to the tail of the queue and mark [3, 4] with an R. Queue: { [3, 1], [1, 6], [3, 4] }
We draw [3, 1] from the queue. We can only move Right into [4, 1]. We add [4, 1] to the tail of the queue and mark [4, 1] with an R. Queue: { [1, 6], [3, 4], [4, 1] }
We draw [1, 6] from the queue. We can only move Right into [2, 6]. We add [2, 6] to the tail of the queue and mark [2, 6] with an R. Queue: { [3, 4], [4, 1], [2, 6] }
We draw [3, 4] from the queue. We can only move Up into [3, 3]. We add [3, 3] to the tail of the queue and mark [3, 3] with a U. Queue: { [4, 1], [2, 6], [3, 3] }
We draw [4, 1] from the queue. We can only move Right into [5, 1]. We add [5, 1] to the tail of the queue and mark [5, 1] with an R. Queue: { [2, 6], [3, 3], [5, 1] }
We draw [2, 6] from the queue. We can only move Right into [3, 6]. We add [3, 6] to the tail of the queue and mark [3, 6] with an R. Queue: { [3, 3], [5, 1], [3, 6] }
We draw [3, 3] from the queue. We can only move Right into [4, 3]. We add [4, 3] to the tail of the queue and mark [4, 3] with an R. Queue: { [5, 1], [3, 6], [4, 3] }
We draw [5, 1] from the queue. We can only move Down into [5, 2]. We add [5, 2] to the tail of the queue and mark [5, 2] with a D. Queue: { [3, 6], [4, 3], [5, 2] }
We draw [3, 6] from the queue. We can only move Right into [4, 6]. We add [4, 6] to the tail of the queue and mark [4, 6] with an R. Queue: { [4, 3], [5, 2], [4, 6] }
We draw [4, 3] from the queue. We can only move Right into [5, 3]. We add [5, 3] to the tail of the queue and mark [5, 3] with an R. Queue: { [5, 2], [4, 6], [5, 3] }
We draw [5, 2] from the queue. We can't move anywhere! We could've moved down into [5, 3] had we gotten here earlier, but the other path got here first. Indeed, both paths would've been the same length, but the one that got here first was earlier alphabetically. We add nothing to the queue and mark nothing. For clarity in the diagram, I marked this path purple, but the algorithm itself does nothing. Queue: { [4, 6], [5, 3] }
We draw [4, 6] from the queue. We can only move Right into [5, 6]. We add [5, 6] to the tail of the queue and mark [5, 6] with an R. Queue: { [5, 3], [5, 6] }
We draw [5, 3] from the queue. We can only move Down into [5, 4]. We add [5, 4] to the tail of the queue and mark [5, 4] with a D. Queue: { [5, 6], [5, 4] }
We draw [5, 6] from the queue. We can only move Up into [5, 5]. We add [5, 5] to the tail of the queue and mark [5, 5] with a U. Queue: { [5, 4], [5, 5] }
We draw [5, 4] from the queue. We can't move anywhere! As before, another path got here first. And again, in this case, it's another path whose length would be the same as this one, but this path got here first because it's earlier alphabetically. We add nothing to the queue and mark nothing. Queue: { [5, 5] }
We draw [5, 5] from the queue. We can only move Right into [6, 5]. We add [6, 5] to the tail of the queue and mark [6, 5] with an R. Queue: { [6, 5] }
We draw [6, 5] from the queue. We can only move Right, and that hits the finishing point. At this point, we retrace our steps, adding our result letters to our string in reverse. When we're done, we print out RRDDDDRRRRUR.

Related Links