WE LOOKED AT maze solving in class as an example of a recursive algorithm. The assignment is to write a program that implements this algorithm. A maze for this program is represented by a 39-by-39 two-dimensional array. Each position in the array is either part of a "wall" or part of a "corridor". All positions along the edges are walls. The corridors form the maze. Your program will search for a path through the maze between the upper left corner -- the (1,1) position -- and the lower right corner -- the (37,37) position. It will use the recursive algorithm that we discussed in class to do so.
The program is due next Wednesday, April 2.
Here is a picture of the type of maze you will work with. (In this picture, I've used two characters for each position. That is, each element of the array is represented on the screen by two characters. This makes the structure easier to see):
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% %% %% %% %% %% %% %%%%%%%%%% %% %%%%%% %%%%%% %% %%%%%%%%%%%%%% %%%%%%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%% %%%%%%%%%%%%%% %% %% %% %%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%% %% %% %%%%%% %%%%%% %%%%%% %% %% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%% %%%%%%%%%% %%%%%% %%%%%%%%%%%%%% %% %%%%%%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %%%%%%%%%% %%%%%% %% %%%%%% %%%%%% %%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %% %% %% %% %% %%%%%%%%%%%%%%%%%%%%%% %% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%%%%%%%%%% %%%%%%%%%% %% %% %%%%%%%%%% %% %%%%%% %%%%%% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %% %% %%%%%% %%%%%%%%%%%%%%%%%% %% %%%%%% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%% %% %%%%%% %% %%%%%%%%%%%%%% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %% %% %%%%%%%%%% %%%%%% %%%%%% %% %% %%%%%% %% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%%%%%% %% %% %%%%%% %% %%%%%%%%%% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%%%%%%%%%%%%%%%%%% %% %%%%%%%%%% %%%%%% %%%%%% %%%%%% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %%%%%% %%%%%%%%%% %%%%%% %% %%%%%% %%%%%% %% %% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%% %%%%%% %% %%%%%% %% %% %%%%%%%%%%%%%% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %% %%%%%% %%%%%% %% %%%%%% %%%%%% %%%%%% %% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %%%%%% %% %% %%%%%%%%%% %%%%%% %%%%%%%%%%%%%%%%%% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%% %%%%%%%%%%%%%% %% %% %%%%%% %% %% %% %% %% %%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%% %% %% %% %% %% %% %%%%%%%%%% %%%%%% %% %%%%%%%%%% %% %% %% %% %% %% %% %% %% %% %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The compiled program makemaze in the directory /home/cs225/maze creates a random maze, displays it on the screen in this form, and writes the data for the maze to the file named "maze.dat". In the file, a wall is represented by a single '%' character, and a corridor is represented by a single '.' character. (This makes it easier to read the file into a program, but makes it harder to see what the maze looks like by viewing the file.)
You should write a program that reads the description of a maze from a file. The name of the file can be specified on the command line. If no file name is given on the command line, the program should try to read a file named maze.dat. You should do a reasonable amount of error-checking when trying to read the file. The program should use the data from the file to fill in the array that represents the maze. Then it should try to find a path from position (1,1) to position (37,37). If it finds a path, it should display the solution on the screen. If there is no solution, it should display a message saying that no solution exists. The compiled program solvemaze does all this. Your program should behave in the same way. Your program should work for any maze produced by the makemaze program.
Note that since there can be loops in the maze, your program must use four different values in the array: One for representing a wall, one for a corridor position that has not been visited, one for a corridor position that is on the current path being considered, and one for a corridor position that has been completely processed without finding a solution.
Your program must be well-designed, using functions to break the problem up into meaningful, significant tasks. Do not use global variables in the program.