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

LISTING 12.2 continued

{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1} };

//-----------------------------------------------------------------
// Attempts to recursively traverse the maze. Inserts special
// characters indicating locations that have been tried and that
// eventually become part of the solution.
//-----------------------------------------------------------------
public boolean traverse ( int row, int column)
{
boolean done = false ;

if (valid (row, column))
{
grid[row][column] = TRIED; // this cell has been tried

if (row == grid.length-1 && column == grid[0].length-1)
done = true ; // the maze is solved
else
{
done = traverse (row+1, column); // down
if (!done)
done = traverse (row, column+1); // right
if (!done)
done = traverse (row-1, column); // up
if (!done)
done = traverse (row, column-1); // left
}

if (done) // this location is part of the final path
grid[row][column] = PATH;
}
return done;
}

//-----------------------------------------------------------------
// Determines if a specific location is valid.
//-----------------------------------------------------------------
private boolean valid ( int row, int column)
{
boolean result = false ;