Recursion - Java Software Solutions: Foundations of Program Design - page 594

LISTING 12.2 continued

// check if cell is in the bounds of the matrix
if (row >= 0 && row < grid.length &&
column >= 0 && column < grid[row].length)

// check if cell is not blocked and not previously tried
if (grid[row][column] == 1)
result = true ;

return result;
}

//-----------------------------------------------------------------
// Returns the maze as a string.
//-----------------------------------------------------------------
public String toString ()
{
String result = "\n";
for ( int row=0; row < grid.length; row++)
{
for ( int column=0; column < grid[row].length; column++)
result += grid[row][column] + "";
result += "\n";
}

return result;
}
}

The only valid moves through the maze are in the four primary directions:
down, right, up, and left. No diagonal moves are allowed. In this example, the
maze is 8 rows by 13 columns, although the code is designed to handle a maze
of any size.
Let's think this through recursively. The maze can be traversed successfully if
it can be traversed successfully from position (0, 0). Therefore, the maze can be
traversed successfully if it can be traversed successfully from any positions adja-
cent to (0, 0), namely position (1, 0), position (0, 1), position (-1, 0), or position
(0, −1). Picking a potential next step, say (1, 0), we find ourselves in the same type
of situation we did before. To successfully traverse the maze from the new current
position, we must successfully traverse it from an adjacent position. At any point,

VideoNote

Tracing the
MazeSearch program.