Suppose that you are given a maze as depicted below; you start at the position marked o and try to reach the position marked with a *, without going through any walls (#). You are allowed to move up, down, left, or right only. No diagonal movements are allowed. Is there a solution to the maze (can you traverse it from start to finish on the given open paths)?

Example maze:

########
#.##..*#
#.##.###
#.#..###
#.##...#
#o...#.#
########

Theory

The problem of solving a maze is actually a graph traversal problem. A graph is simply a representation of a set of objects, where some objects may be connected, as depicted in the picture below:

In terms of a graph, you are to determine wether a path exists from one object to another. There are two common algorithms to do this:

• A depth-first search, in which you search the child objects before the sibling objects. In other terms, travel as far as you can until you reach a dead end, then backtrack to the last spot with more paths. This is generally implemented using a stack or via recursion. A depth-first search cannot be used to find the shortest path.
• A breadth-first search, in which you search the sibling objects before the child objects. In other terms, this is kind of like pouring water in the maze to see if the finish gets wet. This is generally implemented using a queue. A breadth-first search can be used to find the shortest path. How? This is up to you to figure out.

Both of these algorithms have many applications in Computer Science and Mathematics. For example, if you have ever used Microsoft Paint, you may be familiar with the fill bucket tool, which recursively finds all adjacent pixels to the one you click with the same color, and fills it with the new color.

Program Interaction

The interaction for this program is quite simple, prompt the user for an input maze file (or get the filename via a command line argument), open the file and read it into memory, and finally, print wether the maze is solveable or not.

The maze files will look like the example maze at the top of this page. You can download sample inputs here.

For debugging purposes, you may find it useful to print the maze each step as you solve it. For example, you could use the @ symbol to show the places you have visited.

Hints

You are going to need to keep track of where you have visited, and where you haven't. There are a few ways to do this. I'm certain you are smart enough to figure out how to do this.

Lasty, try and stick to one of the two algorithms on this page, and you will have an easier time.

Extensions

If you have extra time, you may want to try and figure out how to show only the shortest path to the finish. You will need to use a breadth-first search to find the shortest path.

Credit

This project was based off of the Mazes assignment by Dr. Christopher Painter-Wakefield for CSCI-262 at Colorado School of Mines. Used with permission.