Your program needs to find a way to go from the upper right corner (where you se
ID: 653727 • Letter: Y
Question
Your program needs to find a way to go from the upper right corner (where you see '>' character) to the lower left corner (where you see '<' character). If you see a dot '.', that mean that slot is available to go through, but if you see a pound sign '#', that means that there is an obstacle and you cannot go through there.
Whenever you go though, you need to change the character at that position to '.' to 'x'. It is possible that one path that you try might lead to a dead end. In that case, you need to backtrack to try another path. The position you decide not to include in your solution path should now be changed to 'O' to record that you have already tried that position. Therefore in this assignment, you will store a successful path (a sequence of positions) in a stack. Whenever you proceed to a new position, you need to push that position information onto the stack. When you decide to back track, you need to pop the position that you are not using as part of a solution path.
In this way, when you reach the goal, the stack should contain a sequence of positions that you took from the starting point to the goal. Also, if one sees the result maze, he/she can also track the solution path by following Xs that you recorded in the maze.
Here is an example. Suppose that you are given the following maze:
Then a solution is:
The sequence of Xs shows the solution path. Note that the positions with an O are already visited, but reached a dead end, so it was removed from the solution path.
Instruction:
You will be given a maze with the size of 10 rows and 10 columns. You need to start from the upper right corner (row = 0, column = 9), and check which adjacent position is available (not '#' or 'O' or out of bounds). When you do this checking, you MUSTcheck in the following order:
First check the location below the current position.
If that position is not available to proceed, then check all other 7 positions around the current position in clockwise direction.
Therefore, you always check in the order of 'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right'.
For instance, if your current position is at (i,j) row = i and column = j, then you need to check (i+1,j) position first.
If the position is not available to proceed, then you check (i+1,j-1), (i,j-1), (i-1,j-1), (i-1,j), (i-1,j+1), (i,j+1), (i+1,j+1).
Position class
This class pairs a row number (int) and a column number (int). Its constructor takes a row number and a column number, and it has accessor methods for row and column, getRow() and getColumn().
It also has a face which keeps track of which direction to go from that position so that it can show a solution at the end. It has an accessor method and a mutator method of face and also toString method.
Face values of 0,1,2,3,4,5,6, and 7 represent the direction of 'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right' respectively.
This class is given by the instructor.
Assignment11 class
This class displays a menu for the Maze Problem. If a user enters "E", then it asks to enter an initial maze configuration, then it will display a result for the problem. This class is given by the instructor.
MazeSolver class
The MazeSolver class contains a constructor to set up an initial maze configuration.
It also contains methods to print out a result maze as well as a solution path. These methods are given by the instructor.
You need to complete the following findSolution method based on its pseudo-code.
public boolean findSolution()
You need to write the findSolution method that determines whether there is a solution to the Maze problem. It should return true if a solution is found, false otherwise. If a solution is found, then the program should display the result maze with Xs and Ox. Your program should display intermediate steps by printing "Trying the position of row 2 and column 7".
Each time a choice is made, the choice is pushed onto a stack that already contains all the previously made choices. The following is the pseudo-code for this. It assumes that for a 10-by-10 maze, rows vary from 0 to 9 and columns vary from 0 to 9. You need to start with (0,9), then try to find an adjacent position to move to. (In this case, trying to go to (1,9).If this does not work, then you need to try to go to (1,8), etc.
boolean success = false;
boolean finish = false;
Push (0,9) -- row 0 and column 9 information onto the stack indicating the first choice is (0,9).
while (finish = = false && stackSoln.isEmpty( ) = = false)
{
Check the most recent position from the stack, and check which of eight adjacent positions to move from the recent position,
in the order of 'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right'.
This part requires another nested loop to repeat at most 8 times to check eight adjacent positions.
If such adjacent position is not outside of the maze range,
row and column being greater than or equals to 0 or less than or equals to 9, and being able to move into
(it needs to contain '.' or '<' the goal position),
then we found a position to move to.
As soon as we find a position to move to, save its direction to 'face' variable and get out of the loop
('face' can contain 0,1,2,3,4,5,6, and 7 representing the direction of
'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right' respectively).
If the found adjacent position to move to is the goal position (contains '<'),
then we found a solution path, and set 'success' to true and 'finish' to true.
Also set the face of the current position to 'face' value obtained by the above loop.
If the found adjacent position to move to is not the goal position,
then push the object of such adjacent position onto the stack, and set the adjacent position to 'x'.
Also set the face of the current position to 'face' value obtained by the above loop.
If we cannot find any adjacent position to move to, then set the current position to 'O', if it was 'x'.
Then pop the solution stack, which means not including this position in the solution path.
If the stack is empty at this time, then there is no other place to back track, thus the maze does not have a solution.
Set 'success' to false and 'finish' to true.
} //end of while loop
return success;
Requirements:
You need to implement this method using an object of the Stack class in java.util package. This stack will contain objects of the Position class.
public class Position
{
private int row;
private int col;
private int face; //which direction it is going next
//Initializes the position object using three parameters
public Position(int row, int col, int face)
{
this.row = row;
this.col = col;
this.face = face;
}
//Accessor method for the row number
public int getRow()
{
return row;
}
//Accessor method for the column number
public int getColumn()
{
return col;
}
//Mutator method for the face (direction)
public void setFace(int face)
{
this.face = face;
}
//Accessor method for the face
public int getFace()
{
return face;
}
//toString() returns a string containing
//the current row, col, and face
public String toString()
{
String result = "From row " + row + ", col " + col + ", go to ";
switch(face){
case 0:
result += "Down";
break;
case 1:
result += "DownLeft";
break;
case 2:
result += "Left";
break;
case 3:
result += "UpLeft";
break;
case 4:
result += "Up";
break;
case 5:
result += "UpRight";
break;
case 6:
result += "Right";
break;
case 7:
result += "DownRight";
break;
default:
result += "Error incorrect direction";
break;
} //end of switch
result += " ";
return result;
} //end of toString method
} //end of Position class
// Description: The MazeSolver contains two 2-dimetional character arrays,
// one for the original and another to display the
// solution to the maze, and the size of maze.
// It also contains a stack to keep track of a solution path found.
// Its findSolution method solves the maze problem
// and put the solution in the stack.
import java.util.Stack;
public class MazeSolver
{
private char[][] originalMaze;
private char[][] maze;
private int mazeSize;
private Stack<Position> stackSoln;
//Constructor to initialize the mazeSize,
//initializes two 2-dimensional character arrays.
public MazeSolver(String[] mazeInfo)
{
mazeSize = 10;
setupMaze(mazeInfo);
stackSoln = new Stack<Position>();
}
//the setupMaze method initializes
//two character arrays, using the input array of strings.
public void setupMaze(String[] mazeInfo)
{
maze = new char[mazeSize][mazeSize];
originalMaze = new char[mazeSize][mazeSize];
for (int i=0; i<mazeSize; i++)
{
for (int j=0; j<mazeSize; j++)
{
originalMaze[i][j] = mazeInfo[i].charAt(j);
maze[i][j] = originalMaze[i][j];
}
}
}
//The displayPath methods returns a string describing
//how to go from the starting position to the goal position
public String displayPath()
{
String result = "";
while (stackSoln.isEmpty() == false)
{
result = stackSoln.pop() + result;
}
return " Solution Path: " + result+" ";
}
//the displaySoln method returns a string containing
//a solution of the maze
public String displaySoln()
{
String result = " The maze content: ";
for (int i = 0; i < maze.length; i++)
{
for (int j = 0; j < maze[i].length; j++)
{
result += maze[i][j];
}
result += " ";
}
return result +" ";
}
//The findSolution will return true if a solution is found,
//false otherwise. Please see the pseudo-code of the assignment 11 statement
public boolean findSolution()
{
boolean finish = false; //finish should become true when a solution is found or it is determined that there is no solution
boolean success = false; //success should become true when a solution is found
//The following can be used to compute each of 8 directions
//one can move from their current position (row,column).
int[][] offset ={
{1,0}, //Down
{1,-1}, //DownLeft
{0,-1}, //Left
{-1,-1}, //UpLeft
{-1,0}, //Up
{-1,1}, //UpRight
{0,1}, //Right
{1,1} //DownRight
};
//Push information onto the stack indicating the first choice
//is the position of row 0 and column 9. The last value is face, put -1 as default
Position nextPosition = new Position(0, 9, -1);
stackSoln.push(nextPosition);
while (finish == false && stackSoln.isEmpty( ) == false)
{
//check the last position
int currentRow = stackSoln.peek().getRow();
int currentCol = stackSoln.peek().getColumn();
System.out.println("Trying the position of row "
+ currentRow
+ " and column "
+ currentCol);
/************************************************************************
Check the most recent position from the stack, and check which of eight adjacent positions to move from the recent position,
in the order of 'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right'.
This part requires another nested loop to repeat at most 8 times to check eight adjacent positions.
If such adjacent position is not outside of the maze range,
row and column being greater than or equals to 0 or less than or equals to 9, and being able to move into
(it needs to contain 'x' or '<' the goal position),
then we found a position to move to.
As soon as we find a position to move to, save its direction to 'face' variable and get out of the loop
('face' can contain 0,1,2,3,4,5,6, and 7 representing the direction of
'down', 'down left', 'left', 'up left', 'up', 'up right', 'right', and 'down right' respectively).
row and column of adjacent positions can be written as:
currentRow+offset[k][0]
and
currentCol+offset[k][1]
where k ranges from 0 to 7.
*************************************************************************/
/************************************************************************
If the found adjacent position to move to is the goal position (contains '<'),
then we found a solution path, and set 'success' to true and 'finish' to true.
Also set the face of the current position to 'face' value obtained by the above loop.
************************************************************************/
/************************************************************************
If the found adjacent position to move to is not the goal position,
then push the object of such adjacent position onto the stack, and set the adjacent position to 'x'.
Also set the face of the current position to 'face' value obtained by the above loop.
************************************************************************/
/************************************************************************
If we cannot find any adjacent position to move to, then set the current position to 'O', if it was 'x'.
Then pop the solution stack, which means not including this position in the solution path.
************************************************************************/
/************************************************************************
If the stack is empty at this time, then there is no other place to back track, thus the maze does not have a solution.
Set 'success' to false and 'finish' to true.
************************************************************************/
} //end of while loop
return success;
}//end of findSolution method
}//end of the MazeSolver class
Explanation / Answer
check this part it is not corect
{
String result = "From row " + row + ", col " + col + ", go to ";
switch(face){
case 0:
result += "Down";
break;
case 1:
result += "DownLeft";
break;
case 2:
result += "Left";
break;
case 3:
result += "UpLeft";
break;
case 4:
result += "Up";
break;
case 5:
result += "UpRight";
break;
case 6:
result += "Right";
break;
case 7:
result += "DownRight";
break;
default:
result += "Error incorrect direction";
break;
} //end of switch
result += " ";
return result;
} //end of toString method
} //end of Position class
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.