Console Maze Solver

• Convert a maze into a graph
• Solve a maze using a graph shortest path algorithm
• Modify a graph implementation to display required information from the graph
• Test and debug a complex application

This assignment is heavily oriented towards solving a graph problem using Java. You are given a Graph class that implements core graph functionality and algorithms. You should use that class (with one minor modification) to solve this graph problem. The major work involves extending a maze generating algorithm from a previous assignment. First, you must convert the generated maze into a graph. Then you feed the graph data into the supplied Graph class and request that it find the shortest path from start to finish.

1. Use the Graph class covered in class. It is available as Graph.java.

2. Use your previous code that created a maze. You will need to add some code to the very end of the constructor.
3. You will need to create an identifier for each cell in the maze. Use something simple like R1C5 for the cell at row 1, column 5. You can create these identifiers on the fly. Each cell will be entered into the graph as a vertex. Each connection between cells will be entered into the graph as an edge. Since the graph will automatically take care of vertices if you just add edges, you only have to add the edges - but you need a String ID for the vertices (cells) the edge connects. That's why you will have to create String IDs for the cells.
4. Do the following:
   1. Create a new Graph object.
   2. For each cell in the board
   1. If the cell is not in the first row and it does not have a wall on its north side, then add an edge to the graph that represents the connection between this cell and the cell to its north.
   2. If the cell is not in the first column and it does not have a wall on its west side, then add an edge to the graph that represents the connection between this cell and the cell to its west.
   3. The Board class has methods for getting the start and end cells. Get the start and end cells, and send their IDs to the graph's shortest path method. You should get back a String. Print it.
5. The shortest path method in the Graph class outputs internal vertex numbering. Change it to output the vertex name instead. The spot you want to make the modification is near the very end of the shortestPath method. There is a for loop which is assembling the output String. All you need to do is take the number it wants to add to the String and use that number as an index into the vertex list to get the vertex name instead.

• (40 pts) Maze correctly converted into a graph
• (10 pts) Graph code modified to display readable output as shown in sample output