Lesson 18: 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. The key topics for this lesson are: A. Defining the Maze Problem |
|||
|
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 2 dimensional array 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? 2. The general case of encountering a blank space requires the following
steps: 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 import apcslib.*;
class ThreadTheMaze
{
private final static int MAXROW = 12;
private final static int MAXCOL = 12;
private final static char BLANK = ' ';
public void loadMaze(char[][] maze)
{
TextReader inFile = new TextReader("mazeData.txt");
for (int row = 1; row <= MAXROW; row++)
{
for (int col = 1; col <= MAXCOL; col++)
{
maze[row][col] = inFile.readAnyChar();
}
inFile.readLine();
}
}
public void printMaze(char[][] maze)
{
TextReader kbd = new TextReader();
for (int row = 1; row <= MAXROW; row++)
{
for (int col = 1; col <= MAXCOL; col++)
{
System.out.print("" + maze[row][col]);
}
System.out.println();
}
System.out.println();
char anyChar = kbd.readAnyChar();
}
/**
* Will attempt to find a path out of the maze. A path will
* be marked with the ! marker. The method makes a copy of
* the array each time so that only the path out will be
* marked, otherwise extra ! markers will appear in the
* answer. The function is recursive.
*/
public void traceMaze(char[][] maze, int row, int col)
{
// make a local copy of maze
char[][] mazeCopy = new char[maze.length][maze[0].length];
for (int r = 0; r < mazeCopy.length; r++)
{
for (int c = 0; c < mazeCopy[0].length; c++)
{
mazeCopy[r][c] = maze[r][c];
}
}
if (1 <= row && row <= MAXROW && 1 <= col && col <= MAXCOL)
{
// boundary check, if false, a base case
if (BLANK == mazeCopy[row][col])
{
// if false, base case
mazeCopy[row][col] = '!';
if (1 == row || MAXROW == row ||
1 == col || MAXCOL == col)
{
printMaze(mazeCopy); // base case
}
else
{
traceMaze(mazeCopy, row - 1, col);
traceMaze(mazeCopy, row, col + 1);
traceMaze(mazeCopy, row + 1, col);
traceMaze(mazeCopy, row, col - 1);
}
}
}
}
public static void main(String[] args)
{
ThreadTheMaze mazeWalker = new ThreadTheMaze();
char[][] maze = new char[MAXROW + 1][MAXCOL + 1];
mazeWalker.loadMaze(maze);
mazeWalker.traceMaze(maze, 6, 6);
}
}
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.
|
|||
|
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. |
|||