Lab Questions
Chapter Number: 13 Recursion

1.1) In this sequence of problems we practice recursion by abandoning our reliance on iteration.  We resolve to solve a sequence of problems without using while or for loops.  Instead we will think recursively and look at the world through a different lens.

Recursion is all about solving a large problem by using the solution to a similar smaller problem.  The brilliant thing about recursion is that you can assume you already know how to solve the smaller problem.  The goal is to demonstrate how the smaller solution relates to the larger problem at hand.  For example, suppose you want to print all binary strings of length 3 and you already know how to print all binary strings of length 2.  Here they are:

                00
                01
                10
                11

How can we solve the larger problem with a list of strings of length 2?  Add a “0” or “1”, right?  So here is the solution to the larger problem:

                00 + 0 = 000
                01 + 0 = 010
                10 + 0 = 100
                11 + 0 = 110
        and 
                00 + 1 = 001
                01 + 1 = 011
                10 + 1 = 101
                11 + 1 = 111    Voila!

Not every binary string problem can be solved in terms of a smaller one.  At some point we have to declare the smallest problem we are interested in and just solve it.  In the case of binary strings, we might agree that the smallest problem we will solve is the 1 digit problem and that the solution is simply 0 and 1.  When we write solutions to problems using recursion we will always solve the smallest problem first, so our programs will usually have a similar structure:

if this is the smallest problem
   Just solve it by hand.
else
   Solve the large problem by using a solution to a smaller version of the same problem.

Now let’s tackle a real problem.  Suppose our goal is to produce an ArrayList with Integer objects 1, 2, 3, …, n by building a method called makeList(int n).  We want to end up with a stand-alone method so we will package the method as a static method.  Remember we are refusing to use while and for loops – think recursively! 

Here is the skeleton code:

import java.util.*;

public class ListMethods
{
   public static ArrayList<Integer> makeList(int n)
   {
      ArrayList<Integer> tempList = null;
      if (n <= 0)  // The smallest list we can make
      {

      }
      else        // All other size lists are created here
      {

      }
      return tempList;
   }
}

The smallest problem we will solve is building and returning an ArrayList when n <= 0.  In that case we want to return an empty ArrayList.  Leave the else block empty for the moment and write the code that will solve this smallest problem.  Test it using the test harness listed below:

import java.util.ArrayList;

public class ListMethodsRunner
{
   public static void main(String[] args)
   {
      ArrayList<Integer> tempList = ListMethods.makeList(0);
      if (tempList.size() == 0)
      {
          System.out.println("The list is empty");
      }
      else
      {
         for (Integer i : tempList)
         {
            System.out.println(i);
         }
      }
   }
}

1.2) We left the else block empty in the last problem.  Let’s fill it in now.  

This is where we need to show how we can solve the large problem (building an ArrayList with 1, 2, 3, …, n) by using a smaller version of the same problem.  What is the next smallest problem?  Yes, building an ArrayList with 1, 2, 3, …, n - 1 .  How can we do that?  Here’s the brilliant part:  We can solve that problem by calling makeList(n – 1) – the very same method we are trying to write!  That’s what makes the recursion happen.  Whenever a method calls itself, the method is recursive.  By calling the same method again, each instance of a problem is solved using the solution to a smaller instance.  Logically, this process has to stop somewhere.  In the case of our ArrayList problem, it stops when we call makeList(0).  This is the problem we solved by hand in Lab 13.1.1.  

Whenever we call makeList(n - 1) we receive an ArrayList with 1, 2, 3, …, n - 1.  How can we use that to produce an ArrayList with 1, 2, 3, …, n?  

Add that code to the else block and complete the makeList method.  Test your code with the test harness by changing the argument that is passed to makeList.  Can you make a list with 100 items?

1.3) Let’s add another static method to class ListMethods with this header:

public static ArrayList<Integer> reverseList(ArrayList<Integer> list) 

This method is passed an ArrayList<Integer> and returns another ArrayList<Integer> that contains the same collection of objects in reverse order.  There is a version of reverse in the Collections class that would reverse our list for us, but for practice we will write our own recursive algorithm to do this.  

In designing this method we will insist that the original list that is passed into the method, and the elements it contains, are left unchanged by the method.  Because our ArrayList<Integer> is passed by reference, any changes we make to its elements are reflected in the passed list.  Our reverseList algorithm will invoke a remove operation on the list, altering it, so we need to make a copy or a “clone” of the original list.  

Although there is a clone method that is inherited by ArrayList, it is a “shallow” clone and doesn’t make copies of the elements of the ArrayList.  It simply copies references to the original elements.  To solve this problem, we create a method called deepClone that returns a new ArrayList that contains references to the copies of the original elements.  Here is the code:

public static ArrayList<Integer> deepClone(ArrayList<Integer> tList)
{
   ArrayList<Integer> list = new ArrayList<Integer>(); 
   for (Integer i : tList)
   {
      list.add(new Integer(i));
   }
   return list;
}

By adding a call to deepClone at the beginning of the reverseList method, we create a copy of the original ArrayList.  We work with this list inside the method instead of the original list. 

We use the same logic pattern as in Lab13.1.1.  First determine the smallest problem we might need to solve.  What is it?  Sometimes there is more than one “smallest” problem that we need to solve by hand.  In the case of the reverse method, the smallest problem could be an empty list or a list with one Integer.  In both of these cases we can simply return the list unchanged – no need to reverse the list.  How do we test for these cases?  Take the code below and fill in the block to be executed when the condition is true.  Leave the other block empty – we will handle that next.   

Modify reverseList so that it makes and reverses an empty list and a list with one element. 

public static ArrayList<Integer> reverseList(ArrayList<Integer> tList)
{
   ArrayList<Integer> list = ListMethods.deepClone(tList); 
   if (// The list is empty or has one element)
   {
      // Return the list as is – no need to reverse!
   }
   else
   {
      // Use the solution to a smaller version of the problem
      // to solve the general problem
   }
   return list;
}

1.4) Now we will write the recursive part of the program in Lab13.1.3.  In solving the problem of reversing a list with n integers, the obvious smaller problem to use is reversing a list with n - 1 integers.  

Somehow we need to remove an element of the ArrayList.  We can use remove(0) to remove the first element. (Another choice would be to remove the last element.)  Let’s think about how the solution to the smaller problem can help us solve the larger one.  Suppose we have the list {1, 2, 3, 4, 5}.  Removing the first element leaves us holding 1 and the smaller list {2, 3, 4, 5}.  Because we are writing recursively, we can use our own reverseList method on the smaller list to produce the list {5, 4, 3, 2}.  Adding the 1 back to this reversed list produces {5, 4, 3, 2, 1} and we are done.   

Use this idea to write the block to be executed when the condition is false in the  reverseList method.  

Then modify your ListMethodsRunner program to build a list with 100 items and reverse it.

1.5) Now build an even method in the ListMethods class with the following header:

public static ArrayList<Integer> even(ArrayList<Integer> list)

The method returns an ArrayList consisting of the elements of the list argument that are stored at the even indexes 0, 2, 4, … .  For example, if the original list is [1, 2, 3, 4, 5, 6], method even would return [1, 3, 5] – the elements at the even indexes, not the even numbers in the list.

What is the smallest list that we might process?  Hint: It isn’t a list with one element.  

Using logic similar to the previous programs, complete the method by coding the two blocks in the if/else sequence. Be sure your even method leaves the list passed to it unchanged.  

Let’s make a plan for our program by examining how the process could work for the list { 1, 2, 3, 4, 5, 6, 7 }.

1)  Remove and save the first element at index 0. We are left holding 1 and { 2, 3, 4, 5, 6, 7 }.
2)  Remove and discard the new element at the index 0, which is now 2.  We are still holding 1 and { 3, 4, 5, 6, 7 }..
3)  Apply even recursively to {3, 4, 5, 6, 7 }. We see that even({3,4,5,6,7}) generates { 3, 5, 7 }.
4)  Add the element 2 to the front of the list { 3, 5, 7 }.  There is an alternate version of the add method in the ArrayList class that allows you to specify the index of the position where the element will be added.  For example list.add(0, x) would add x at the beginning of list. 

1.6) Next write an odd method – the companion to even — with the following header:

public static ArrayList<Integer> odd(ArrayList<Integer> list)

The method returns an ArrayList consisting of the elements of the list that are stored at the odd indexes 1, 3, 5, … .  

Using logic similar to the previous programs, complete the method by coding the two blocks in the if/else sequence. Be sure your odd method leaves the list passed to it unchanged.

1.7) Build a merge method with the following header:

public static ArrayList<Integer> merge(ArrayList<Integer> list1, 
      ArrayList<Integer> list2)

The method is passed two sorted lists of type ArrayList<Integer> and returns a sorted  ArrayList<Integer> containing all the elements of the passed lists.  Big Hint:  Removing even one element from either list creates a smaller version of the same problem.  Also, there is a get method in the ArrayList class that returns a reference to an element but doesn’t remove it.  

Use the following test harness to test your method.  Be sure your merge method leaves the lists it is passed unchanged.

import java.util.ArrayList;

public class ListMethodsRunner
{
   public static void main(String[] args)
   {
      ArrayList<Integer> list1 = new ArrayList<Integer>();
      list1.add(2);
      list1.add(3);
      list1.add(5);
      list1.add(9);
      list1.add(22);
      list1.add(38);
      list1.add(56);
      ArrayList<Integer> list2 = new ArrayList<Integer>();
      list2.add(4);
      list2.add(7);
      list2.add(8);
      list2.add(23);
      list2.add(37);      
      ArrayList<Integer> tempList = ListMethods.merge(list1, list2);
      if (tempList.size() == 0)
      {
          System.out.println("The list is empty");
      }
      else
      {
         for (Integer i : tempList)
         {
            System.out.println(i);
         }
      }
   }
}

2.1) The number of permutations of n items is computed as follows: 

     n! = n * (n - 1)! for n > 0;

Here, the number of permutations of n items is written as n!, which is pronounced "n factorial".

It is easy to see why this formula is true. There are n choices for placing the first item. For each of these choices, there are n - 1 places left for the other items. 

When n is 1, there is only one permutation of a single item. Hence

   1! = 1

It is also convenient to set

   0! = 1

From this definition, compute the value of 5! and show your work.

2.2) Complete the following class that counts the number of permutations for n items. Make your solution recursive so it constructs an object that counts the permutations of a smaller number of items.

public class PermutationCounter
{
   private int n;

   public PermutationCounter(int numberOfItems)
   {
      n = numberOfItems;
   }
   
   public long getCount()
   {
      // Your work here
   }
}

2.3) Provide a tester class for your PermutationCounter class.

2.4) Of course, it is also easy to implement the getCount method non-recursively, using the familiar formula 

n! = 1 * 2 * 3 * . . . * n

What is the code for your non-recursive (iterative) getCount method?  Because the integers we are computing get large quickly for small values of n, you should choose to compute them as type long instead of int.  This data type will accommodate much larger results than int.

3.1) A formula for finding the greatest common divisor (GCD) of two numbers was formulated by the mathematician Euclid around 300 bce. The GCD of two numbers is the largest number that will divide into both numbers without any remainder. For example, the GCD of 12 and 16 is 4, the GCD of 18 and 12 is 6.

The basic algorithm is as follows:

Assume we are computing the GCD of two integers x and y. Follow the steps below:

1.  Replace the larger of x and y with the remainder after (integer) dividing the larger number by the smaller one.
2.  If x or y is zero, stop.  The answer is the nonzero value. 
3   If neither x nor y is zero, go back to step 1.

Here is an example listing the successive values of x and y:

  x          y
135         20       %(135 / 20) = 15
 15         20       %(20 / 15) = 5
 15          5       %(15 / 5) = 0    
  0          5       GCD = 5       

Write a recursive method that finds the GCD of two numbers using Euclid’s algorithm. 

public class Arithmetic
{
   public static int gcd(int a, int b)
   {
      // Your work here
   }
}

3.2) Write a tester program for your GCD algorithm.

4.1) OPTIONAL: In this set of exercises, you will write a program to draw the logarithmic spiral recursively.

The logarithmic spiral, or Fibonacci spiral, is a shape often found in nature. The nautilus shell is the classic example of the logarithmic spiral. Seed patterns in sunflowers and pinecones also demonstrate the spiral.

To construct a logarithmic spiral, begin with a golden rectangle. A golden rectangle is a rectangle with sides of length A and fA, where f (Phi) is the golden mean or the value 

(1 + sqrt(5)) / 2   or   1.61803 . . . 

A square with length equal to the smallest side of the rectangle is drawn inside the rectangle. A quarter arc (arcAngle = 90 degrees) is drawn within this square. The remaining rectangle is also a golden rectangle. This remaining rectangle is divided into a square and another smaller golden rectangle. A quarter arc connected to the previous arc is drawn inside the square, and the remaining rectangle is once again subdivided with an arc drawn in it.

Hint:  In Java, the height and width of the Rectangle class are stored as ints. Unless you keep track of a golden rectangle's dimensions as floating-point numbers, you will quickly lose precision and the resulting rectangles will not be drawn correctly.

Create a panel in which to draw the spiral:

public class LogSpiralPanel extends JPanel

Given the dimensions of the panel, draw the largest golden rectangle that will fit within the panel. Part of the code of the class has been provided for you:

import java.awt.Graphics;
import java.awt.Rectangle;
import java.awt.geom.Arc2D;
import javax.swing.JPanel;

public class LogSpiralPanel extends JPanel
{
   private static final double GOLDEN_MEAN = (1 + Math.sqrt(5)) / 2;

   public void paintComponent(Graphics g)
   {
      /* Your code goes here.
         1. Compute the dimensions of the goldenRectangle (you can use getHeight() 
            to obtain the side size)
         2. Draw the golden rectangle
         3. Call the recursive helper method "recursiveDraw" which will draw 
            the spiral.
      */
   }
   
   /**
      Method that recursively draws a logarithmic spiral.
      @param x The x-coordinate of the golden rectangle's upper-left corner  
      @param y The y-coordinate of the golden rectangle's upper-left corner
      @param side the smallest side size of the golden rectangle
      @param angle the angle (0, 90, 180 or 270) where the top of the 
      golden rectangle is located. For the outermost golden rectangle, 
      the angle is 90.
   */
   private void recursiveDraw(Graphics g, double x, double y, double side, int angle)
   {
      . . .
   }
   
   . . .
}

What is the code of your completed paintComponent method?

4.2) Now you will complete the code of the recursive helper method recursiveDraw. To recursively draw the logarithmic spiral, you first need to draw the square. The square's upper-left corner is at position (x, y), and its side size is side. Then you need to draw the arc. You can use the method drawArc that has been provided for you. Then you need to recursively call recursiveDraw to continue drawing the spiral recursively. 

Before making the recursive call you need to calculate the new side size, the new x-coordinate, the new y-coordinate, and the new angle. Two methods calculateNewX and calculateNewY have been provided for you. You can use these methods to calculate the new x and y coordinates, but you need to calculate the new side size and the new angle yourself. Remember that the new side size is the difference between the sizes of the two sides of the current rectangle. The new angle is given by rotating the current angle 90 degrees in clock-wise direction.

public class LogSpiralPanel extends JPanel
{
   private static final double GOLDEN_MEAN =  (1 + Math.sqrt(5)) / 2;

   public void paintComponent(Graphics g)
   {
      . . .
   }
   
   /**
      Method that recursively draws a logarithmic spiral.
      @param x The upper left corner x-coordinate of the golden rectangle
      @param y The upper left corner y-coordinate of the golden rectangle
      @param side the smallest side size of the golden rectangle
      @param angle The angle (0, 90, 180 or 270) where the top of the 
      current golden rectangle is located. For the outermost golden 
      rectangle, the angle is 90.
   */
   private void recursiveDraw(Graphics g, double x, double y, double side, int angle)
   {
      // Recursion ending condition: when the side is very small
      . . .

      // Draw the current square and arc
      . . .

      /* Continue drawing the spiral recursively: calculate the new side 
         size, calculate the new (x, y) coordinates and the new angle. Then, 
         call "recursiveDraw" again. */
      . . .
   }
   
   /**
      Draws the arc of the current iteration.
      @param x The x-coordinate of the square's upper-left corner  
      @param y The y-coordinate of the square's upper-left corner
      @param side The size of the side of the square (or the arc's radius)
      @param angle The angle (0, 90, 180 or 270) where the top of the 
      current golden rectangle is located. For the outermost golden 
      rectangle, the angle is 90.
   */
   private void drawArc(Graphics g, double x, double y, double side, int angle)
   {
      double auxX = x;
      double auxY = y;
      if (angle == 0 || angle == 270 )
      {
         auxX = x - side;
      }
      if (angle == 270 || angle == 180)
      {
         auxY = y - side;
      }
      g.drawArc((int) auxX, (int) auxY, (int) side * 2, (int) side * 2, angle, 90);
   }   
   private double calculateNewX(double x, double angle, double side, double newSide)
   {
      if (angle == 0)
         x = x + side - newSide;
      else if (angle == 90)
         x = x + side;
      else if (angle == 270)
         x = x - newSide;
      return x;
   }

   private double calculateNewY(double y, double angle, double side, double newSide)
   {
      if (angle == 0)
         y = y + side;
      else if (angle == 180)
         y = y - newSide;
      else if (angle == 270)
         y = y + side - newSide;
      return y;
   }
}

What is the code of your recursiveDraw method?

4.3) Create a LogSpiralFrame class that will contain the LogSpiralPanel.

4.4) Now write a viewer class to display the frame and log spiral. What is the code of your LogSpiralViewer class?

5.1) The golden mean, often referred to as the golden ratio, divine proportion, or the golden number is represented by the Greek letter phi ( f ). The value of the golden mean is 

(1 + sqrt(5)) / 2     or   1.61803 . . . 

The golden mean is found in nature and art and tends to yield the most "aesthetically pleasing" arrangements of objects.

Fibonacci numbers are directly related to the golden mean. Computing ratios of Fibonacci numbers can approximate the value of the golden mean. The value of

     fib(n) / fib(n - 1) 

approximates the golden mean as n goes to infinity.

These values can be computed recursively as well. Note that

g(n) = (fib(n - 1) + fib(n - 2)) / fib (n - 1)

Simplify this expression so that g(n) is expressed in terms of g(n - 1).

1) What is your recursive definition for g(n)?
2) When does the recursion stop?

5.2) Write a recursive method 

public static double goldenMean(int n)

that computes the nth iteration of the golden mean. What is the code of your method?

5.3) What is the tenth approximation of the golden mean?

5.4) As you learned in the textbook, the recursive computation of fib(n) can be inefficient. Add trace statements 

"Entering goldenMean: n = "

to verify that your method for computing goldenMean(n) does not calculate each number more than once. What is the output after you add trace messages?

6.1) OPTIONAL: In one variant of the game of Nim, two players alternately take marbles from a pile. In each move, a player chooses how many marbles to take. The player must take at least one but at most half of the marbles. Then the other player takes a turn. The player who is left with one marble loses.

Clearly, if you start with two marbles, you are going to win. Take one marble, and your opponent loses right away. We therefore say that 2 is a winning position.

In general, a winning position is a position in which you can force a win. That is, there is at least one move that leads to a losing position.

Conversely, a losing position is a position that is either an outright loss, or in which every move leads to a winning position.

Following these definitions, write mutually recursive methods

public class NimCalculator
{
   public boolean isWinningPosition(int n)
   {
      for (int i = 1; i <= n / 2; i++) { . . . }
   }
   public boolean isLosingPosition(int n) { . . . }
}

What is the code for your methods?

6.2) Run a test program using your methods. Which values between 2 and 100 are losing positions?

6.3) Why does this recursion run so slowly?  Print a trace message each time you enter isWinningPosition or isLosingPosition so we can determine why it runs so slowly.  Be sure to print the method name and the parameter value at entry to each method.

6.4) You can speed up the methods by remembering for which numbers you have already determined the answers. Use an array to store known positions.

public class NimCalculator
{
   private int[] knownPositions = new int[10000];

   public boolean isWinningPosition(int n) { . . . }
   public boolean isLosingPosition(int n) { . . . }
}

Here, knownPositions[i] should be 1 if i is known to be a winning position, -1 if i is known to be a losing position, and 0 if it is not known to be either.

What is the code for your modified isWinningPosition and isLosingPosition methods?

6.5)  Now run your program again. Just print out the losing positions < 10000. What pattern do you see?

7) OPTIONAL: Apply the backtracking technique of Section 13.7 to solve the following maze-walking problem:  A maze is specified by a text file like the one below. We use x’s to denote walls, and a’s to denote available cells that can be explored.  A solution is a path that travels from the starting position to the ending position by moving east, west, north or south through cells filled with a’s.   

25 25 1 0 23 24
xxxxxxxxxxxxxxxxxxxxxxxxx
aaaaaaaaaaaaxxxxxxxxxxxxx
xzaxxxaxxxxxxxxxxxxxxxxxx
xxaxxxxxxxxxxxxxxxxxxxxxx
xxaaaaaaaaaxxxxxxxxxxxxxx
xxaxxxxxxxxxxxxxxxxxxxxxx
xxaxxxxxxxxxxxxxxxxxxxxxx
xxaxxxxxxxxxxxxxxxxxxxxxx
xxaaaaaaaaaaaaaaaaaxxxxxx
xxxxxaxxxxxxxxxaxxxxxxxxx
xxxxxaxxxxxxxxxaxxxxxxxxx
xxxxxaxxxxxxxxxaaaaxxxxxx
xxxxxaxxxxxxxxxxxxxxxxxxx
xxxxxaxxxxxxxxxxxxxxxxxxx
xxxaaaxxxxxxxxxxxxxxxxxxx
xxxxxaxxxxxxxxxxxxxxxaxxx
xxxxxaxxxxxxxxxxxxxxxaxxx
xxxxxaxxxxxxxxxxxxxxxaxxx
xxxxxaaaaaaaaaaaaaaaaaxxx
xxxxxaxxxxxxxxxxaxxxxxxxx
xxxxxaxxxxxxxxxxaxxxxxxxx
xxxxxaxxxxxxxxxxaxxxxxxxx
xxxxxaxxxxxxxxxxaxxxxxxxx
xxxxxaxxxxxxxxxxaaaaaaaaa
xxxxxxxxxxxxxxxxxxxxxxxxx

The first two integers in the file specify the number of rows and columns in the maze (25 and 25), the next two integers denote the entrance to the maze (row 1, column 0), and the last two integers denote the exit (row 23, column 24).   Copy the file contents and save it in a file (I saved it in "c:/Maze/maze.txt").  This file is referenced in the main program.

The maze is represented by a class that you will need to complete:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Maze
{
   private String[][] maze;
   private int rows;
   private int cols;
   private int startX;
   private int startY;
   private int endX;
   private int endY;
   private Scanner scan;
   
   public Maze(File filename)
   {
      Scanner scan;
      try 
      {
         scan = new Scanner(filename);
      }
      catch(FileNotFoundException e)
      {
          System.out.println("File not found");
          return;
      }
      rows = scan.nextInt();
      cols = scan.nextInt();
      maze = new String[rows][cols];
      startX = scan.nextInt();
      startY = scan.nextInt();
      endX = scan.nextInt();
      endY = scan.nextInt();
      for (int i = 0; i < rows; i++)
      {
         String temp = scan.next();
         for (int j = 0; j < cols; j++)
         {
            maze[i][j] = "" + temp.charAt(j);
         }
      }
      scan.close();
   }

   public String toString()
   {
      String temp = "";
      for (int i = 0; i < rows; i++)
      {
         for (int j = 0; j < cols; j++)
         {
            temp = temp + maze[i][j] + " ";
         }
         temp = temp + '\n';
      }  
      return temp;
   }

   public boolean search()
   {
      return searchMaze(startX, startY);
   }

   public boolean searchMaze(int i, int j)
   {
      //Your code goes here…
   }
}

Here is the main program.

import java.io.File;

public class MazeRunner
{
   public static void main(String[] args)
   {
      Maze maze = new Maze(new File("c:/Maze/maze.txt"));
      System.out.println(maze);
      maze.search();
      System.out.println(maze);
   }
}

You will need to supply the code for the searchMaze(int i, int j) method.  This method returns “true” if there is a path to the exit from the current position (row i, column j) that uses only positions filled with “a”.  The method uses a backtracking technique to advance the current path by filling the current cell with a space and moving to a cell that is either east, west, north or south of the current cell.  If there is no path forward to the exit from the current cell, the current cell is marked with a “v” to indicate we have visited the cell, but the current path is a dead end. Here is a listing of a correct run of the main program for the input listed above.

x x x x x x x x x x x x x x x x x x x x x x x x x 
a a a a a a a a a a a a x x x x x x x x x x x x x 
x z a x x x a x x x x x x x x x x x x x x x x x x 
x x a x x x x x x x x x x x x x x x x x x x x x x 
x x a a a a a a a a a x x x x x x x x x x x x x x 
x x a x x x x x x x x x x x x x x x x x x x x x x 
x x a x x x x x x x x x x x x x x x x x x x x x x 
x x a x x x x x x x x x x x x x x x x x x x x x x 
x x a a a a a a a a a a a a a a a a a x x x x x x 
x x x x x a x x x x x x x x x a x x x x x x x x x 
x x x x x a x x x x x x x x x a x x x x x x x x x 
x x x x x a x x x x x x x x x a a a a x x x x x x 
x x x x x a x x x x x x x x x x x x x x x x x x x 
x x x x x a x x x x x x x x x x x x x x x x x x x 
x x x a a a x x x x x x x x x x x x x x x x x x x 
x x x x x a x x x x x x x x x x x x x x x a x x x 
x x x x x a x x x x x x x x x x x x x x x a x x x 
x x x x x a x x x x x x x x x x x x x x x a x x x 
x x x x x a a a a a a a a a a a a a a a a a x x x 
x x x x x a x x x x x x x x x x a x x x x x x x x 
x x x x x a x x x x x x x x x x a x x x x x x x x 
x x x x x a x x x x x x x x x x a x x x x x x x x 
x x x x x a x x x x x x x x x x a x x x x x x x x 
x x x x x a x x x x x x x x x x a a a a a a a a a 
x x x x x x x x x x x x x x x x x x x x x x x x x 

Success
x x x x x x x x x x x x x x x x x x x x x x x x x 
      v v v v v v v v v x x x x x x x x x x x x x 
x z   x x x v x x x x x x x x x x x x x x x x x x 
x x   x x x x x x x x x x x x x x x x x x x x x x 
x x   v v v v v v v v x x x x x x x x x x x x x x 
x x   x x x x x x x x x x x x x x x x x x x x x x 
x x   x x x x x x x x x x x x x x x x x x x x x x 
x x   x x x x x x x x x x x x x x x x x x x x x x 
x x         v v v v v v v v v v v v v x x x x x x 
x x x x x   x x x x x x x x x v x x x x x x x x x 
x x x x x   x x x x x x x x x v x x x x x x x x x 
x x x x x   x x x x x x x x x v v v v x x x x x x 
x x x x x   x x x x x x x x x x x x x x x x x x x 
x x x x x   x x x x x x x x x x x x x x x x x x x 
x x x a a   x x x x x x x x x x x x x x x x x x x 
x x x x x   x x x x x x x x x x x x x x x v x x x 
x x x x x   x x x x x x x x x x x x x x x v x x x 
x x x x x   x x x x x x x x x x x x x x x v x x x 
x x x x x                         v v v v v x x x 
x x x x x a x x x x x x x x x x   x x x x x x x x 
x x x x x a x x x x x x x x x x   x x x x x x x x 
x x x x x a x x x x x x x x x x   x x x x x x x x 
x x x x x a x x x x x x x x x x   x x x x x x x x 
x x x x x a x x x x x x x x x x                   
x x x x x x x x x x x x x x x x x x x x x x x x x

The complete path from entrance to exit is denoted by spaces.  Notice that some cells are labeled “v”.  These cells indicate a path that was explored, but which did not lead to the exit.  Some cells are still labled “a”.  These are available cells that were never explored by our program.  Results may vary for the cells labeled “a” or “v” depending on how you write the searchMaze method.  The path from entrance to exit is unique, so your program should produce exactly the same cells that are filled with spaces as in the solution listed above.