CS - C++ Lesson 19:  Recursive Array Programming

 INTRODUCTION:               Suppose you were trapped in a maze and you needed to find your way out.  Your initial attempts are random and due to the same appearance of the white walls, you begin wasting time and energy trying the same routes over and over.  After some thought and remembering a computer science algorithm, you take advantage of a tool in your pocket, a marking pen.  You begin marking the walls with some notes and a time stamp.  At each branch point, you mark the direction you are about to attempt with an arrow.  If a dead-end is encountered just around the corner, you retreat to the branch point, mark “dead-end” for that direction, and try another direction. By marking which directions have failed, you avoid trying them again.  This 2 dimensional problem and the required backtracking leads us to a recursive matrix problem!  After defining the problem, an entire solution will be covered in the outline.  Your programming exercise will also be a recursive matrix problem.

                                                 The maze searching problem is translated from,

                                                Oh! Pascal!, 2nd edition.[1]

  The key topics for this lesson are:

  A.  Defining the Maze Problem

B.   Developing the Recursive Solution

C.  The Solution to the Maze Problem

D.  Declaring enum Data Types

VOCABULARY:                   BACKTRACKING

DISCUSSION:                       A.  Defining the Maze Problem

1.   The maze will be defined as a 2-D grid of asterisks (marking walls) and blanks (marking potential paths).  The size of the grid will be 12 x 12 and the starting location will be at 6,6.

2.   The data structure for this problem will be an apmatrix of char.  The array will be declared as a 13 x 13 grid so that we can use locations 1..12 by 1..12.  Row 0 and column 0 will not be used in the data structure.

3.   The initial grid is stored as a text file and will be loaded into the array.

{Here is a copy of the mazeData.txt file}

*** ********

***    *****

*** **  ****

***   *  ***

***** ** ***

***** ** ***

***** ******

*****   ****

****  * ****

*   **  ****

* *    *****

* **********

4.   A potential path out of the maze will be traced with a !, with moves limited to horizontal or vertical directions.

5.   We will be at an exit point if we arrive at row 1 or MAXROW, or at column 1 or MAXCOL.

6.   The solution is a backtracking algorithm involving a series of trial and error attempts.  If a dead-end is hit, back up and try a different direction.

B.   Developing the Recursive Solution

1.   In developing a recursive solution, consider the base cases first.  What situation(s) cause the algorithm to stop?

a.   We have arrived at a location which is off the data structure.  It is important to catch this situation first to avoid an array indexing error.

b.   Encountering a '*' character means that we have run into a wall.  The algorithm should stop.

c.   Arriving at a location which has a row or column value equal to 1 or MAXROW or MAXCOL.  We have found an exit point.

2.   The general case of encountering a blank space requires the following steps:

a.   Change the character value from the blank space to the '!' character.

b.   Check to see if we are at an exit point.  If we are, print the maze with a trail of '!' markers to the exit point.

c.   If we are not at an exit point, make 4 recursive calls to check all 4 directions, feeding the new coordinates of the 4 neighboring cells.

3.   When a recursive call is made, a value parameter will be used in the formal parameter list of the function.  Each recursive call will work with a copy of the array.  Why is this?  If a reference parameter was used the placement of ! marks would be permanent in the data structure.  However, when an exit point is found we want to print only the successful trail of ! marks which leads to an exit.

C.  The Solution to the Maze Problem

// program threadTheMaze

#include <iostream.h>

#include <apmatrix.h>

#include <fstream.h>

const int MAXROW = 12, MAXCOL = 12;

const char BLANK = ' ';

void loadTheMaze (apmatrix<char> &maze);

void printMaze (const apmatrix<char> &maze);

void traceMaze (apmatrix<char> maze, int row, int col);

void loadTheMaze (apmatrix<char> &maze)

/*    When reading text from disk, you cannot use the extraction operator,

        >>, because it skips white space.  You need to use the stream member

        function get, as used below.  You will also need to get rid of the

        end-of-line marker, which is a single ASCII code 10 in C++ text file

        processing. */

{

        ifstream inFile ("Mac HD:ap96:mazedata.txt",ios::in);

        char c1;  // to dump end-of-line markers

        for (int row=1; row<=MAXROW; row++)

        {

                for (int col=1; col<=MAXCOL; col++)

                        inFile.get(maze[row][col]);

                inFile.get(c1);      // dump eoln marker, ASCII 10's

        }

}

void printMaze (const apmatrix<char> &maze)

{

        for (int row=1; row<=MAXROW; row++)

        {

                for (int col=1; col<=MAXCOL; col++)

                        cout << maze[row][col];

                cout << endl;

        }

        cout << endl << "Hit return to continue ";

        cin.get();

}

void traceMaze (apmatrix<char> maze, int row, int col)

/*    will attempt to find a path out of the maze.  A path will be marked

        with the ! marker.  The function uses value parameters so that only

        the path out will be marked, otherwise extra ! markers will appear in

        the answer.  The function is recursive. */

{

        if (1<=row && row<=MAXROW && 1<=col && col<=MAXCOL)

                // boundary check, if false, a base case

        {

                if (BLANK == maze[row][col])  // if false, base case

                {

                        maze[row][col] = '!';

                        if (1==row || MAXROW==row || 1==col || MAXCOL==col)

                                printMaze (maze);  // base case

                        else

                        {

                                traceMaze (maze,row-1,col);

                                traceMaze (maze,row,col+1);

                                traceMaze (maze,row+1,col);

                                traceMaze (maze,row,col-1);

                        }

                }

        }

}

main ()

{

        apmatrix<char> maze(MAXROW+1,MAXCOL+1);

        loadTheMaze (maze);

        traceMaze (maze,6,6);

        return 0;

}

Here are the two solutions to starting at location (6,6):

1.   It is very significant that a blank space be changed to an '!' mark before the recursive calls are made.  For example, suppose we begin at location 6,6 and a blank space is encountered.  If we did not change the blank to an '!' mark, the recursive call to solve the upward direction receives the location 5,6.  This recursive call will eventually look back down at location 6,6 - the location where it came from.  A blank space would still be there and the recursive calls would go round in circles until the computer runs out of memory.

2.   Changing the blank space to an '!' mark is like leaving a trail of markers.  When a recursive call of a neighboring cell looks back at the cell from which it came it will see a '!' mark and not a blank space.

D.  Declaring enum Data Types

1.   C++ allows for user-defined types which permits the programmer to better simulate real-world values.  For example the 4 suits which make up a deck of cards can be defined as follows:

      enum suitType {Heart, Club, Diamond, Spade};

2.   This new data type called suitType can be used to declare appropriate variables.  The possible values of suitType have analogous integer values.  The compiler will associate Heart as integer value 0, Club as 1, Diamond as 2, and Spade as a 3.

3.   The following program illustrates some preliminary usage of enum types.

#include <iostream.h>

enum suitType {Heart, Club, Diamond, Spade};

main ()

{

        suitType  value = Diamond;      // declare and initialize

        for (suitType loop=Heart; loop<=Spade; loop++)

                if (loop == value)

                        cout << "Diamond == Diamond" << endl;

}

4.   The variable loop is declared as a suitType.  It will loop through the 4 values of the suitType list.  Variables of enum types can be compared using relational operators.

5.   Enum types will be required in the lab exercise of this lesson.  A future lesson (Lesson 27) will cover enum types more thoroughly.

SUMMARY/REVIEW:         Some of the earlier examples of recursion were applied to linear problems.  The factorial or Fibonacci problems were one dimensional, which required only one recursive call within the algorithm.  The maze problem is best solved recursively because of the different directions that the problem solving takes.  Loosely stated, any problem that involves multiple directions and returning to a branch point is a likely candidate for recursion.

ASSIGNMENT:                    Lab Exercise L.A.19.1, Eraseobject