due: Monday, May 5, 1997, 11:30pm
+-+-+-+ Start -> |0 1 2| +-+ +-+ |3 4 5| + +-+-+ |6 7 8| <- Finish +-+-+-+The corresponding graph for this maze is:
0-1-2 | 3-4-5 | 6-7-8where rooms in the maze correspond to nodes in the graph and hallways in the maze correspond to edges in the graph. Finding a route through the maze from start to finish corresponds to finding a path from the start node to the finish node in the path. Thus, solving mazes reduces to searching the graph, beginning at the start node, and looking for the finish node.
The two graph traversal algorithms that we have mentioned in class, Depth First Search (DFS) and Breadth First Search (BFS), can be directly applied to solving mazes. A DFS of a maze involves following some path through the maze as far as we can go, until a dead end or previously visited location is met. When this occurs, the search backtracks to try another path. BFS proceeds differently: it visits the nodes in order of their distance from the start node. First it visits all the nodes one step away, then it visits all nodes that are two steps away, and so on, until the finish node is found. Because of this, BFS has the nice property that it will naturally discover the shortest route through the maze. For more details, see p. 329 of the book.
Graph traversal can also be applied to solve this problem: suppose you wanted to paint the rooms in a maze, but only have two colors of paint. To avoid monotony, you've decided to paint the rooms in such a way that no two adjacent rooms are the same color. How might you determine whether a given maze is 2-colorable?
What we've provided
As a starting point we've provided a few files:
Maze(istream &inFile); // construct a maze from input stream data
DFSolve(); // solve using DFS
BFSolve(); // solve using BFS
TwoColor(); // determine whether a maze is 2-colorable
The executable mzsolve reads a maze file from the standard input. The file format is just a listing of nodes with their adjacencies. There is some header information at the front that gives the number of nodes, the start and finish nodes, and so on. Specifically, a maze file has this format:
<number of nodes> <index of start node> <index of finish node> <minimum x coord> <max x coord> <min y> <max y> 0 <coordinates of node 0> <list of adjacent nodes> -1 1 <coordinates of node 1> <list of adjacent nodes> -1 ... n-1 <coordinates of node n-1> <list of adjacent nodes> -1For example, the maze in the overview would be specified by this file:
9 0 8 0 2 0 2 0 (0,0) 1 -1 1 (1,0) 0 2 4 -1 2 (2,0) 1 -1 3 (0,1) 4 6 -1 4 (1,1) 3 5 1 -1 5 (2,1) 4 -1 6 (0,2) 3 7 -1 7 (1,2) 6 8 -1 8 (2,2) 7 -1There are some sample input files in the directory project2/inputs that you can use to test your program.
Outputting a solution
The program should spit out two solution paths: one computed by DFS, the other by BFS. Each path is given by a sequence of node indices from the start node to the finish node, terminated by -1. For example, the path output for the maze above would be:
0 1 4 3 6 7 8 -1 0 1 4 3 6 7 8 -1since both methods compute the same solution path given by:
0-1 2 | 3-4 5 | 6-7-8After outputting the paths, the program needs to output whether the given maze is 2-colorable. If the maze is 2-colorable, then the nodes can be partitioned into two sets based on their color. Your program should output the nodes in one of these sets followed by -1. For example, the 2-coloring output for the maze above would be:
0 2 4 6 8 -1since the maze is two colorable and the listed nodes can all be painted the same color. If the given maze is not 2-colorable, output -1.
What to hand in
You are required to hand in your project2 directory with your implementation of the Maze data structure. Included in this directory should be at least these files:
% cd ~/326stuff/myproj2dir % make clean % cd ../ % turnin -c cse326=AA -p project2 myproj2dir
The executable mzgen generates random mazes to standard output. For example, invoking:
% ./bin.alpha/mzgen -r20x10 -m > mazefilewill put a rectangular maze with 20 rows and 10 columns into mazefile. Using -t instead of -r will generate a triangular maze. The -m option asks for a maze with multiple paths from start to finish, rather than a maze with a single solution. Type mzgen -h to see all its options.
Sample maze solver
The executable mzsolve is our sample solution for this assignment. Use it to see what we expect from you. Note:your solution paths may be different from ours if you store the adjacencies in a different order. This is ok.
% ./bin.alpha/mzsolve < mazefile > mazesolnwill solve mazefile and put the paths into the file mazesoln
The executable mzshow displays a maze and solution paths read from standard input. For example, invoking:
% cat mazefile mazesoln | ./bin.alpha/mzshowwill display the maze and solution paths from above in a window.