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.


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;


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 PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use 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;
    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()

By purchasing this solution you'll be able to access the following files:

for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats