Question

JAVA QUESTION!!! please help!

The following codes are a Maze program. There are TWO traversable paths possible in this maze. The program uses recursion. Can someone please explain to me why the program will pick one path if multiple traversable paths are available? Why does the program choose one path over a different path? (I believe it has something to do with the recursion terminating when a solution is found but I'm not sure.)

Thank you!!!!

The codes:

public class Maze
{
   private final int TRIED = 3;
   private final int PATH = 7;

   private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{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,1,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;

// 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;
   }
}

---------------------------end of first code-------------------------------

public class MazeSearch
{
   //-----------------------------------------------------------------
   // Creates a new maze, prints its original form, attempts to
   // solve it, and prints out its final form.
   //-----------------------------------------------------------------
   public static void main(String[] args)
   {
Maze labyrinth = new Maze();

System.out.println(labyrinth);

if (labyrinth.traverse(0, 0))
   System.out.println("The maze was successfully traversed!");
else
   System.out.println("There is no possible path.");

System.out.println(labyrinth);
   }
}

Answer 1

1. This program uses recusrion to find the traversible path. Lets have a look into the code

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

As per the code, it will first check whether a DOWN move is valid or not. If its valid, it will skip all others and will move DOWN. If it is not, it will try RIGHT move. If RIGHT move is not valid, then it tries UP and finally LEFT if UP is an invalid move. If you observe carefully, as soon as it finds a valid path, it simply ignores all other directions and continues with that path.

Now, assume that continuing in a current path, if it does not find anymore valid moves, then it will backtract till the point where multiple paths are available and then continue with the other possible direction.

if (row == grid.length-1 && column == grid[0].length-1)
done = true; // the maze is solved

This above lines of code check if the maze is already solved or not, if it already solved, then it does not check for any other alternative paths and simply return true (meaning that a path is found).