Recursively Solving a Maze
Due: Thursday, June 16th at 11:59PM

Introduction

This programming assignment asks you to write a program, using recursion, that solves mazes. The mazes will be provided with simple text files and the programs output will be the correct path through the maze.

For simplicity, the program only needs to solve mazes with a single starting point and a single finishing point.

The Maze Class

The Maze Class is the basis of Maze object. Maze objects, much like their paper equivalents, contain a grid of cells, each of which is either a wall or a path. They also contain special path cells, the start and finish cells.

The Maze uses a two-dimensional array of booleans to model the array. "true" represents paths and "false" represents walls. This array is constructed from a data file.

This data file consists of a header that identifies the number of rows, e.g. "Rows: 6", the number of columns, e.g. "Columns: 6", the start cell's (row, column), e.g. "Start: (2,3)", and the finish cell's (row, column), e.g. "Finish: (4,5)".

After the header is a list of cells that are part of path's (as contrasted from walls). By default, all cells in a maze are walls. Only those cells that are individually listed as being part of the paths are path cells. The start and finish cells should also be listed as path cells.

We have provided one sample maze for you. You should, of course, create many more mazes for testing. The figure below represents is another representation fo the maze within the sample file.

We didn't want to make you go through the time consuming process of coding up the parts of the code that involved parsing the file input, so we provided that code for you, as well as a few other pieces. But, there are several pieces of the Maze class left for you to implement.

Please click here to view the Maze class skeleton.

Maze Solver Class

The really interesting part of this assignment is the MazeSolver class. The solve() method of this class calls upon the solve_recursive() method to recursively solve the maze. The solve() method, through solve_recursive(), should have two results:
• It should return "true", if it succeeded in solving the maze or "false" if it could not solve the maze (the case where there is no path between the start and finish).
• It should record the correct path in some data structure so that it can be recovered later via the toString() method.

Please note that this method shold only consider cells to be adjacent if they are in the same column or in the same row -- but not diagnal.

Please click here to view the MazeSolver skeleton. If you'd like to see our solution's output for the sample maze given earlier, we've made our sample output available, too.