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:

.........>
#....#..x#
#....##.x#
....#.##x.
#..#.x..x.
.###x#xx#.
..#x##xx..
#xxxO#x##.
x##xO#O###
<.#O###OOO
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 MUST check 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 '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).

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.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

// 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 "\nSolution Path:\n" + result+"\n\n";
   }


//the displaySoln method returns a string containing
//a solution of the maze
public String displaySoln()
   {...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Java Program For Restaurants
Homework Solution
$18.00
Java
Restaurants
Computer Science
Programming
Tips
Variables
Functions
Dollar Amounts
Functions
Input
Output
Statements
Multiplication
Bills
Percentage
Division
NumberFormat Class
5 Commandments For Computer Ethics
Homework Solution
$10.00
Computer Science
Programming
Commandments
Computer Ethics
Examples
Harm
Stealing Files
False Witness
Software
Resources
Authorization
Intellectual Output
Social Consequences
Respect
Builder Dash Game in Java
Homework Solution
$163.00
Java
Programming
Computer Science
Codes
Algorithms
Classes
Timers
Statements
Variables
Moves
Instances
Graphics
Animations
ChatBot Using Java Programming
Homework Solution
$7.00
Java
Programming
Coding
Chatting
Bot
Users
Computers
Sentences
Symbols
Instant Messaging
Input
Output
Special Characters
Even Numbers
Odd Numbers
Binary Tree in Java
Homework Solution
$40.00
Java
Programming
Coding
Computer Science
Binary Tree
Data
Generic Types
Functions
Variables
Recursive Methods
Nodes
Input
Output
Arrays in Programming Language Java
Homework Solution
$20.00
Java
Programming
Computer Science
Arrays
Integers
Random Numbers
Methods
Functions
Even Elements
Odd Elements
Prime Numbers
Minimum Values
Maximum Values
Average Values
Loops
Conditions
Statements
Get help from a qualified tutor
Live Chats