CSE 326 Data Structures Project 2

CSE 326 Data Structures
Project 2
Solving a Maze

due: Monday, May 5, 1997, 11:30pm

Objective

To build data structures for representing sparse graphs and 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, 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?

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, 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/97sp/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.

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:

Maze.h, Maze.C, mzsolve.C
README - This is a text file describing your project implementation. It should describe your choice of data structure for the maze and a high level description of your search algorithms. In addition, try to answer these questions:
- Why are all rectangular mazes (where the rooms are on a grid) 2-colorable?
- Can you think of any methods for generating arbitrary mazes?
sample output of your executable from the mazes in the inputs directory.
any additional files you added/changed.

Turn your files in electronically using turnin:

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

Additional utilities

We've provided a few utilities to help you develop and test your program. This are located in the directories project2/bin.alpha (for orcas & sanjuan executables) and project2/bin.RISC (for lynx, wolf, & grizzly).

Maze generator

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

      % ./bin.alpha/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.alpha/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.alpha/mzshow

will display the maze and solution paths from above in a window.