TITLE

RECURSIVELY FINDING PATHS THROUGH A MAZE

INTRODUCTION

Recursion is a programming technique in which a function calls itself. This project applies recursion to a new problem, and illustrates the recursive implementation of backtracking.

DESCRIPTION

Design, implement, test, and document a program that calls a recursive function to find a path through a maze. The path will extend from an entrance at the top of the maze to an exit at the bottom.

An array of characters represents a maze: blanks represent corridors, and `+' characters represent walls. Indicate the steps along a path with some other character. The program reads a maze from a data file, identifies the path(s) through the maze, and prints out each path. There may be more than one path.

INPUT

The program reads the name of a data file from the terminal. A data file will contain the dimensions of a maze and an array of `+'s and blanks that represent the maze. This array must be no larger than 22 rows by 76 columns, so that it can be displayed on a standard terminal screen. The entrance to the maze will always be the second position on the top row, which must therefore be blank. The exit must be on the maze's bottom row. Except for its entrance and exit, the entire perimeter of the maze must be "wall;" there will be no other entrances or exits.

OUTPUT

The program's output will be the maze with a path through it indicated, one such picture of the maze for each path. Direct output to the terminal.

ERRORS

The program should recover gracefully if the user enters the name of an input file that does not exist. Otherwise, it may assume that the input is correct; it need not detect any errors.

EXAMPLE

This is a typical instance of this problem. The input file maze.dat is on the left. Corresponding output might look like the right figure.

 20 20 A path through the maze: + ++++++++++++++++++ +@++++++++++++++++++ + + ++ +++ +@@@@@@@@@@+ ++ +++ +++ ++++++ ++ ++ +++ ++++++@@@++ ++ + +++ +++ ++++ + +++@@@@+++@@@@++++ + + ++ ++++++ + + +@++@++++++@@@@+ +++ ++ ++ ++ + +++@@@++@@@@@++ ++@+ + +++ ++++ ++ ++ + +@@@+++ ++++@++ ++@+ + ++++ ++ +++++ + +@++++ ++@@@+++++@+ + + +++ +++ + +@ + +++@+++ @@+ + ++ + +++ ++++++ ++ +@++ + +++@++++++@++ + +++++ +++ ++ +@ +++++@@@+++@@@@++ + +++ ++++ ++ ++ +@+++ @++++@@++ ++ + ++++ +++ + +@@@++++@@@@@@+++ + +++ +++++++++++ + +++@ +++++++++++ + ++ +++++++ + ++@@+++++++ + ++ +++ ++++++++ + ++@+++ ++++++++ + ++ ++++++ + + ++@++++++@@@@@@@@+ + + +++ ++++++ +++ + @@@+++@@++++++@+++ ++++ +++ +++ ++++@@@@@+++ @@@@+++ +++++++++++++ ++++++ +++++++++++++@++++++ 

OTHER REQUIREMENTS

Use a recursive function to identify each step of a path through the maze. Your program should be able to handle mazes of any dimensions up to 22 by 76; read the dimensions of each maze from its file. (The example above is 20 by 20.) Test the program with examples that are at least 16 by 16. Note that larger examples are more entertaining.