Classwork:

Trace the maze solver

//********************************************************************
//  Represents a maze of characters. The goal is to get from the
//  top left corner to the bottom right, following a path of 1s.
//********************************************************************
public class Maze
{
   private final int TRIED = 3;
   private final int PATH = 7;
   private int stepCount = 0;
   private int[][] grid = { {1,1,1},
                            {1,0,1},
                            {0,0,1}};

	1	1	1
	1	0	1
	0	0	1

//-----------------------------------------------------------------
   //  Tries to recursively follow the maze. 
   //-----------------------------------------------------------------
   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;
            stepCount--;
         }
      }
      
      return done;
   }
   

 //-----------------------------------------------------------------
   //  Determines if a specific location is valid.
   //-----------------------------------------------------------------
   private boolean valid (int row, int column)
   {
      boolean result = false;
      stepCount++;
      // 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;
   }
}

//********************************************************************
//  MazeSearch.java       Author: Lewis/Loftus/Cocking
//  Demonstrates recursion.
//********************************************************************

public class MazeSearch
{
   //-----------------------------------------------------------------
   //  Creates a new maze, prints its original form, tries 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 solved!");
      else
         System.out.println ("There is no possible path.");

      System.out.println (labyrinth);
   }
}

Assignment:

1. Maze 3 by 3 solver trace
Show the rows and columns visited by the program for this maze:

1 0 1
1 1 1
0 1 1

2. Maze 3 by 3 solver trace using stacks
Show the changes in the stacks as the visit to a path pushes the location information and then the values are pop when they are not part of the solution.
NOTE: If you want to use small pieces of paper to push information into the top of the stack, I have a good number of them for you to use.

Here is the trace for the 3 by 3 above:
(row,column)
( 0 , 0)
( 1 , 0)
( 2 , 0)
( 1 , 1)
( 0 , 0)
( 1 , -1)
( 0 , 1)
( 1 , 1)
( 0 , 2)
( 1 , 2)
( 2 , 2)