Consider a maze made up of rectangular array of squares.

A sample maze The X blocks represent a blocked square and form the walls of the maze. Lets consider mazes that have only one entrance and one exit, as in our example. Beginning at the entrance at the top left side of the maze, fund a path to the exit at the bottom right side. You can move only up, down, left, or right. Square is either clear or blocked.

Let a two dimensional array represent the maze. You should write two alternative methods to find a path through the maze. One of the methods should find the path recursively while the other method is non-recursive and must use a stack data structure to find a path. Some mazes might have more than one successful path, while others might have no path.

What you need to do:

I have attached three files with this assignment spec:

Position.java: a class to store the position of an array cell. It has two attributes: row and column along with their accessor and mutator methods. It also has an equals method that checks for equality of two Position objects.

Maze.java: a class to store and traverse a maze. It has one attribute: a two dimensional character array which represents the maze. It also has two methods traversewithStack which finds a solution to the maze using stack and traverseRecursive which finds the solution recursively.

MazeTester: a sample driver class which calls the traverse method on the maze shown in figure 1. To ensure that your program works correctly for all mazes, try to test your program for at least a couple more mazes in addition to the one in figure 1.

Your job is to implement the two methods : traverseWithStack and traverseRecursive in the Maze.java class. Both of these methods receive the start and goal positions as parameters and return an array of Position which stores a solution to the maze if such solution exists; otherwise, they return null.

Note: There might be more than one possible solution to a maze, depending on the ordering in which the neighboring cells are visited at each location. Please follow the following order in visiting the neighbor positions:

First move left, if the left neighbor is not clear, then move right, if the right neighbor is not clear, then move up, if it is not clear, then move down.

To get a full credit, it is very important that you comply with this ordering rules, so that your method produces a solution that matches the correct solution in my test harness You also need to validate the parameters passed to the traverse method.

For example, the start and end positions should be valid array positions and contain blank. You also need to check for a null or an empty array (array with all null elements).

What you need to turn in:

You need to submit the Maze.java file containing your implementation of traversewithStack and traverseRecursive methods.

*********************************************************************************

/**

* A class to store a position in a maze

* @author esahe2

*

*/

public class Position{

/***************************

* Attributes

****************************/

private int row;

private int column;

/***************************

* Constructor

* @param row

* @param column

***************************/

public Position(int row, int column)

{

this.row = row;

this.column= column;

}

/**************************

* Checks two positions for equality. Two positions are equal if the have the same row and column numbers.

*************************/

public boolean equals(Object obj)

{

Position otherPosition= (Position)obj;

return (otherPosition.row==row && otherPosition.column==column);

}

public String toString()

{

return "row:"+ row + " column:"+ column;

}

/**************************

* Getter and Setter methods

* @return

*/

public int getRow() {

return row;

}

public void setRow(int row) {

this.row = row;

}

public int getColumn() {

return column;

}

public void setColumn(int column) {

this.column = column;

}

}

************************************************************************

/**

* A simple driver class to test the maze traversal. Please note that this is only provided as a sample test case. In order to make sure that your program is correct you must test it on several test cases.

* @author Ellie

* Below is what should be printed by your traverse method:

row:1 column:0

row:1 column:1

row:1 column:2

row:2 column:2

row:2 column:3

row:2 column:4

row:1 column:4

row:1 column:5

row:1 column:6

row:2 column:6

row:2 column:7

row:2 column:8

row:2 column:9

row:3 column:9

row:4 column:9

row:4 column:10

row:4 column:11

row:5 column:11

row:5 column:12

The goal is reached

*

*/

/**

* Note this is just an example of a main method to test your program. You should test your program.

* You must test your program for more test cases to ensure that it works in all cases

* @author esahe2

*

*/

public class MazeTester {

public static void main(String[] args)

{

char[][] sample_maze ={

{'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'}

};

Maze m = new Maze(sample_maze);

Position[] sol= m.traversewithStack(new Position(1,0), new Position(5,12));

System.out.println("The solution returned by traverseWithStack is: ");

if (sol!= null)

{

for (int i=0; i

System.out.println(sol[i]);

System.out.println("The goal is reached");

}

else

System.out.println("This maze has no solution");

sol= m.traverseRecursive(new Position(1,0), new Position(5,12));

System.out.println("The solution returned by traverseRecursive is: ");

if (sol!= null)

{

for (int i=0; i

System.out.println(sol[i]);

System.out.println("The goal is reached");

}

else

System.out.println("This maze has no solution");

}

}

***************************************************************************************

/****

* A class to store and traverse a maze

* @author esahe2

*

*/

import java.util.*;

public class Maze {

/**

* Two dimensional array to represent a maze

*/

private char[][] maze;

/**

* Constructor initializing the maze array

* @param maze

*/

public Maze(char[][] maze)

{

this.maze= maze;

}

/**

* You need to implement this method

* @param start: The start Position in the maze

* @param goal: The goal Position in the maze

* @return An array of Position which stores a solution to the maze. If a solution is not found a null value should be returned.

*/

public Position[] traversewithStack(Position start, Position goal)

{

//Your implementation goes here.

}

/**

* You need to implement this method

* @param start: The start Position in the maze

* @param goal: The goal Position in the maze

* @return An array of Position which stores a solution to the maze. If a solution is not found a null value should be returned.

*/

public Position[] traverseRecursive(Position start, Position goal)

{

//Your implementation goes here.

}

}