Position.java: a class to store the position of an array cell. It has two attrib
ID: 3813762 • Letter: P
Question
Position.java: a class to store the position of an array cell. It has two attributes: row andcolumn along with their accessor and mutator methods. It also has an equals method thatchecks for equality of two Position objects.
•Maze.java: a class to store and traverse a maze. It has one attribute: a two dimensionalcharacter array which represents the maze. It also has a method “traverse” which finds asolution to the maze.
•MazeTester: a sample driver class which calls the traverse method on the maze shown in figure1.To ensure that your program works correctly for all mazes, try to test your program for atleast a couple more mazes in addition to the one in figure 1.
You only need to implement the traverse method in the Maze.java class. This method receives the start and goal positions as parameters and returns an array of Position which stores a solution to the maze if such solution exists; otherwise, it returns null.
*************************************************************************************************
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[] traverse(Position start, Position goal)
{
//Your implementation goes here.
}
*************************************************************************************************
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;
}
}
*************************************************************************************************
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.traverse(new Position(1,0), new Position(5,12));
if (sol!= null)
{
for (int i=0; i<sol.length; i++)
System.out.println(sol[i]);
System.out.println("The goal is reached");
}
else
System.out.println("This maze has no solution");
}
}
Explanation / Answer
package com.cheggtest;
/* Finding the solution out of a maze.
This problem illustrates searching using stacks (depth-first search)
and queues (breadth-first search).
Laura Toma
csci 210
*/
import java.util.Stack;
import java.util.LinkedList;
public class Maze {
final static char C=' ', X='x', S='s', E='e', V='.';
final static int START_I = 1, START_J = 1;
final static int END_I = 2, END_J = 9;
private static char[][] 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'}
};
public int size() {
return maze.length;
}
public void print() {
for (int i=0; i<size(); i++) {
for (int j=0; j<size(); j++) {
System.out.print(maze[i][j]);
System.out.print(' ');
}
System.out.println();
}
}
public char mark(int i, int j, char value) {
assert(isInMaze(i,j));
char tmp = maze[i][j];
maze[i][j] = value;
return tmp;
}
public char mark (MazePos pos, char value) {
return mark(pos.i(), pos.j(), value);
}
public boolean isMarked(int i, int j) {
assert(isInMaze(i,j));
return (maze[i][j] == V);
}
public boolean isMarked(MazePos pos) {
return isMarked(pos.i(), pos.j());
}
public boolean isClear(int i, int j) {
assert(isInMaze(i,j));
return (maze[i][j] != X && maze[i][j] != V);
}
public boolean isClear(MazePos pos) {
return isClear(pos.i(), pos.j());
}
//true if cell is within maze
public boolean isInMaze(int i, int j) {
if (i >= 0 && i<size() && j>= 0 && j<size()) return true;
else return false;
}
//true if cell is within maze
public boolean isInMaze(MazePos pos) {
return isInMaze(pos.i(), pos.j());
}
public boolean isFinal( int i, int j) {
return (i== Maze.END_I && j == Maze.END_J);
}
public boolean isFinal(MazePos pos) {
return isFinal(pos.i(), pos.j());
}
public char[][] clone() {
char[][] mazeCopy = new char[size()][size()];
for (int i=0; i< size(); i++)
for (int j=0; j<size(); j++)
mazeCopy[i][j] = maze[i][j];
return mazeCopy;
}
public void restore(char[][] savedMaze) {
for (int i=0; i< size(); i++)
for (int j=0; j<size(); j++)
maze[i][j] = savedMaze[i][j];
}
public static void main(String[] args) {
Maze maze = new Maze();
maze.print();
System.out.println(" Find a path using a stack: ");
maze.solveStack();
System.out.println(" Find a path using a queue: ");
maze.solveQueue();
System.out.println(" Find a path recursively: ");
maze.solveRec();
}
//THE GOAL IS TO FIND A PATH FROM START TO END
public void solveStack() {
//save the maze
char[][] savedMaze = clone();
//declare the locations stack
Stack<MazePos> candidates = new Stack<MazePos>();
//insert the start
candidates.push(new MazePos(START_I, START_J));
MazePos crt, next;
while (!candidates.empty()) {
//get current position
crt = candidates.pop();
if (isFinal(crt)) break;
//mark the current position
mark(crt, V);
//put its neighbors in the queue
next = crt.north();
if (isInMaze(next) && isClear(next)) candidates.push(next);
next = crt.east();
if (isInMaze(next) && isClear(next)) candidates.push(next);
next = crt.west();
if (isInMaze(next) && isClear(next)) candidates.push(next);
next = crt.south();
if (isInMaze(next) && isClear(next)) candidates.push(next);
}
if (!candidates.empty())
System.out.println("You got it!");
else System.out.println("You're stuck in the maze!");
print();
//restore the maze
restore(savedMaze);
}
public void solveQueue() {
//save the maze
char[][] savedMaze = clone();
//declare the locations stack
LinkedList<MazePos> candidates = new LinkedList<MazePos>();
//insert the start
candidates.add(new MazePos(START_I, START_J));
MazePos crt, next;
while (!candidates.isEmpty()) {
//get current position
crt = candidates.removeFirst();
if (isFinal(crt)) break;
//mark the current position
mark(crt, V);
//put its neighbors in the queue
next = crt.north();
if (isInMaze(next) && isClear(next)) candidates.add(next);
next = crt.east();
if (isInMaze(next) && isClear(next)) candidates.add(next);
next = crt.west();
if (isInMaze(next) && isClear(next)) candidates.add(next);
next = crt.south();
if (isInMaze(next) && isClear(next)) candidates.add(next);
}
if (!candidates.isEmpty())
System.out.println("You got it!");
else System.out.println("You're stuck in the maze!");
print();
//restore the maze
restore(savedMaze);
}
public void solveRec() {
if (solve(new MazePos(START_I, START_J)))
System.out.println("Got it: ");
else System.out.println("You're stuck in the maze.");
print();
}
public boolean solve(MazePos pos) {
//base case
if (!isInMaze(pos)) return false;
if (isFinal(pos)) return true;
if (!isClear(pos)) return false;
//current position must be clear
assert(isClear(pos));
//recurse
//first mark this location
mark(pos, V);
//try to go south
if (solve(pos.south())) {
//we found a solution going south: if we want to leave the
//maze clean, then unmark current cell and return; if we
//want to mark the path in the maze, then don't unmark
//mark(pos, C);
return true; }
//else west
if (solve(pos.west())) {
//we found a solution going west: if we want to leave the
//maze clean, then unmark current cell and return; if we
//want to mark the path in the maze, then don't unmark
//return
//mark(pos, C);
return true;
}
//else north
if (solve(pos.north())) {
//we found a solution going north: if we want to leave the
//maze clean, then unmark current cell and return; if we
//want to mark the path in the maze, then don't unmark
//return
// mark(pos, C);
return true;
}
//else east
if (solve(pos.east())) {
return true;
}
mark(pos, C);
//if none of the above returned, then there is no solution
return false;
}
};
class MazePos {
int i, j;
public MazePos(int i, int j) {
this.i = i;
this.j = j;
};
public int i() { return i;}
public int j() { return j;}
public void print() {
System.out.println("(" + i + "," + j + ")");
}
public MazePos north() {
return new MazePos(i-1, j);
}
public MazePos south() {
return new MazePos(i+1, j);
}
public MazePos east() {
return new MazePos(i, j+1);
}
public MazePos west() {
return new MazePos(i, j-1);
}
};