Spring 1996
Assignment 7, due Thursday March 28 at 2PM
In this assignment you will use recursion to find a path through
a maze.
Your source files are to be electronically submitted by using the
submit program on csa. The code
you submit should
conform with the
program assignment guidelines.
The assignment consists of three source files (a7p1.c,
a7p2.c, and
a7p3.c) that should be compiled and linked together to make
your maze solving program. In addition, you will need to create a
header file a7.h that contains the structure type
definitions and function prototypes needed for your program.
This header file must be included in all three source files.
Finding a Path Through a Maze
Write a program that uses recursive backtracking search to solve a
maze. This should be a fairly short program but will
take some thought, so don't put it off. Think about what the base
case(s) are and what the recursive step will be. Remember that with
recursion, the idea is to handle one step of the problem and then let
the rest be solved in the same way.
Maze Representation
A maze is represented as a 2D array of characters, where
characters are interpreted as follows:
- ' '(blank)
- represents empty space
- '*'
- represents a wall (a cell your solution cannot occupy)
- '?'
- represents a cell that was considered and rejected by
your algorithm
- '@'
- represents a cell on the solution path
- 'S'
- represents the starting position in the maze
- 'E'
- represents the ending position in the maze
When you read the maze data, each cell will contain either a blank or a '*'.
Here is an example maze.
As you solve the maze, update blank cells to one of the other
symbols ('?','@','S','E'). Here is an
example solution to the above
maze, for a path starting at (10,9) and ending at (16,18).
Input File Format
Maze test data will be provided in an input file. The file
contains information for a structure mazeType
- first line: mazeWidth mazeHeight
- second line: startRow startColumn
- third line: endRow endColumn
- lines thereafter: rows defining maze
Note that the upper-left corner of the maze is (0,0).
Your program must handle mazes of any size.
Naturally, you'll want to start with some tiny maze while you're developing
your code.
Later, you will want to test using a larger maze. Here is the
input file for the previous
example maze.
This maze has width=20 and height=18. The start
position is row=10 and column=9. The end position is row=16 and
column=18.
Part 1: Maze Maintainance Functions a7p1.c
This file should contain all routines having to do with maze
maintainance. Write (at least) the following
functions:
- mazeType *readMaze(char *fname);
-
Reads a maze file, allocates and loads a structure of mazeType.
Your program should be able to solve a maze of any size. In other words, you
need to dynamically allocate a two dimensional array based on dimensions read
from the data file. When successful, this function
returns a pointer to maze structure. Otherwise it returns NULL.
- int freeMaze(mazeType *maze);
-
Frees a maze structure. Returns 0 if unsuccessful, non-zero otherwise.
- int printMaze(mazeType *maze);
-
Prints the maze out. Returns 0 if unsuccessful, non-zero otherwise.
- int checkMaze(mazeType *maze);
-
Verifies that the start and
end points are within the maze boundaries and that they
are blank cells in the initial maze. Returns 0 if maze is
invalid, non-zero otherwise.
Create a header file a7.h that contains the structure type
definition for mazeType and function prototypes for your
maze management routines.
This header file must be included in all ".c" source files
for this assignement.
Part 2: Recursive Maze Solving Function a7p2.c
Write a function
int solveMaze(mazeType *maze, int x, int y);
that
uses recursive backtracking search to solve a maze. The
arguments x,y specify the current position in
the maze.
The function should recursively search the maze and
return 0 if the end of the maze was
not reached, or 1 if successful.
This should be a fairly short function but will
take some thought. Think about what the base
case(s) are and what the recursive step will be. Remember that with
recursion, the idea is to handle one step of the problem and then let
the rest be solved in the same way.
Hint: Your program will first mark the starting point
in the maze with 'S' and the ending point with 'E'. The symbols '@'
and '?" should be inserted in the maze as you recursively solve it.
To speed up the search, only consider moves in the N, E, W, and S
directions from the current position. The exact solution you get will
depend on the order in which you search these four directions.
Include a function prototype for your recursive function
in a7.h.
Part 3: Maze Solver Main Program a7p3.c
Use the above functions to develop a maze solver main program. Your
program should take one command-line argument: the maze file name.
If the maze can be solved, print the solution in the presribed
format.
If the maze cannot be solved, print an appropriate message.
You will submit four files for this assignment:
a7p1.c, a7p2.c, a7p3.c, and a7.h.
Programming assignments are due before class on the
assignment due date.
Late assignments will be levied a late penalty of 10% per day. Late
assignments will only be accepted up to 4 days late.
Academic Honesty and Collaboration
It is reasonable to discuss with others possible general approaches to
problems. It is unreasonable to work together on a detailed solution,
to copy a solution, or to give away a solution. If your common
discussion can be detected by looking at the solutions, then there is
too much collaboration. Such instances of academic dishonesty will
result in a course grade of F or expulsion from Boston University.
Do not allow your work to be used by others:
- Set the permissions so that they are not readable by others.
- Do not recycle old printouts. Take them home to throw them out.
- Do not e-mail your solution to anyone.
Warning: If someone cheats by using your work, you will also be penalized
Page Created: Feb 6, 1995
Maintained by: Stan Sclaroff