CSE 326 Data Structures Project 2

CSE 326 Data Structures
Project 2
Solving a Maze

Code due: Wenesday, February 10, 1999, 11:30pm
Documentation due: Thursday, February 11, 1999, in section

Objectives

Design data structures for representing sparse graphs.
Develop algorithms for graph traversal, and apply them to solve graph search problems.

Overview

Graphs are a useful abstract representation for many different problems, and graph search methods provide a way of solving those problems. Mazes, for example, can be viewed as being fully connected, undirected graphs. For example, a maze with 9 rooms is given below:

          +-+-+-+                     
 Start -> |0 1 2|          
          +-+ +-+                      
          |3 4 5|                      
          + +-+-+                      
          |6 7 8| <- Finish            
          +-+-+-+

The corresponding graph for this maze is:

where 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 on BFS see pp. 335-339, and for DFS see pp. 362-374.

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 would you do it? In general, if we can color a graph using two colors such that no two adjacent nodes are the same color, we say the graph is "2-colorable." How might you determine whether a given maze is 2-colorable?

Assignment

For this assignment, you are required to write a program mzsolve that finds routes through mazes and solves the 2-coloring problem. Your program will take a maze as input (in a file format described below) and output a solution path for the maze and a strategy for 2-coloring the maze. To accomplish this, you will implement a Maze ADT to represent the maze as a graph. You will implement Maze ADT operations to construct a graph from a maze file, search the graph for solution paths using DFS and BFS, and determine a two color painting scheme for the maze.

What we've provided

As a starting point we've provided a few files:

mzsolve.C - this is the main driver code for the program that we've partially implemented. Mostly, this will just make calls to the Maze ADT and output their results.
Maze.h,Maze.C - these contain a skeleton of the specification and implementation of the Maze ADT as a C++ class. You will implement the internal representation of the the maze. You are free to use any implementation you prefer. Be aware that some representations are better than others, and we will evaluate your choice. The data structure should be able to handle arbitrary mazes (thus, arbitrary graphs). At the minimum, you will need to implement these methods:
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
Stack.h, Queue.h - implementations of Stack and Queue ADTs as C++ template classes. These are provided for convenience, as you may need them to implement your algorithms.
Makefile - make mzsolve will use this to build your program.

All provided files can be found in the project directory:

/cse/courses/cse326/1999wi/project2

Input files

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> -1

For 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 -1

There 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 -1

since both methods compute the same solution path given by:

After 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 -1

since 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.

Handing in the code

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:

Maze.h, Maze.C, mzsolve.C, Makefile
Stack.h, Queue.h - Turn these in if you used them.
Any additional files you used or changed.

Turn your files in electronically using turnin:

% cd ~/326stuff/myproj2dir % make clean % cd ../ % turnin -c cse326=AA -p project2 myproj2dir

Handing in the documentation

Your documentation should be one or two typewritten pages. Your figures can be hand drawn. It should contain the following:

A description of your choice of data structure for the maze, and a brief explanation of why you chose this particular structure.
A high level description of your search algorithms.

Also answer the following questions:

Why are all rectangular mazes 2-colorable?
Can you think of any methods for generating random mazes?

Additional utilities

We've provided a few utilities to help you develop and test your program. These are located in the directory project2/bin.

Maze generator

The executable mzgen generates random mazes to standard output. For example, invoking:

      % ./bin/mzgen -r20x10 -m > mazefile

will 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/mzsolve < mazefile > mazesoln

will solve mazefile and put the paths into the file mazesoln

Maze viewer

The executable mzshow displays a maze and solution paths read from standard input. For example, invoking:

      % cat mazefile mazesoln | ./bin/mzshow

will display the maze and solution paths from above in a window. The BFS path will be shown in purple, and the DFS path will be shown in yellow.

Utility scripts

We have also provided two scripts, called maze.sh and soln.sh. We do not support these, but they may make it easier for you to run your program and compare it with our sample solution. Run maze.sh using the same parameters as for mzgen. This will generate a maze and run your program on it, showing results using mzshow. Then run soln.sh to run our mzsolve on the maze, displaying the results using mzshow.