Question

Maze Solving with Stacks

Problem Statement

Consider a maze made up of rectangular array of squares, such as the following one:

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

Figure 1--- A sample maze

The “X” blocks represent a blocked square and form the walls of the maze. Let us 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, find 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 by an X character.

Let a two-dimensional array represent the maze. Use a stack data structure to find a path through the maze. Some mazes might have more than one successful path, while others might have no path.

Hints:

• The primary consideration is that if you reach a dead end, you need to be able to backtrack along the path to the point where you can try a different path. The stack data structure makes it possible to store the current path and backtrack if necessary. Every clear position visited in the current path is pushed to the stack and if a dead end is reached, the previous position is popped from the stack to backtrack. You need to have a loop that begins with the start position and pushes it into the stack then moves to a neighboring cell until either the goal position is reached, or the stack becomes empty.
• Make sure to mark each clear array cell you move to as visited to avoid checking it again and getting stuck in an infinite loop. For example, each array cell can have three different values: “X” for blocked, “V” for visited, and “ “ for clear.
• A dead end is an array cell whose all neighbors are either blocked or already visited.

What you need to do:

There are four files you should pay attention to:

• 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 equal’s method that checks for equality of two Position objects.
• Maze.java: a class to store a maze. It has 3 attributes: a two-dimensional character array which represents the maze, a Position object to represent the start location, and another Position object to represent the stop location.
• MazeSolver: This class contains one static method, solve. It accepts a maze and returns an array of Positions that is used to traverse the maze if the maze is solvable. If the maze is not solvable then an empty array is returned.
  • Keep in mind that stacks store objects in reverse order so be sure to return the position array in the correct order.

You only need to implement the solve method in the MazeSolver.java class. This method receives the maze to solve as a parameter and returns an array of Position objects which stores a solution to the maze if such solution exists; otherwise, it returns an empty array.

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. You can do whatever order you want if the maze is solved. For instance,

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.

You may create any additional helper methods to aid you. For instance, you may make a method to convert the stack to a necessary array. Just remember, when you grab the information from a stack you are getting in the reverse order you push them.

You must solve the problem using a Stack. You may use the built-in stack library but use of any other data structure is prohibited apart from constructing the final Position array result.

Recursion is also not allowed.

What you need to turn in:

You need to submit the MazeSolver.java file containing your implementation of the solve method.

Additional Notes and Helpful Hints

First hint I have is to not be afraid of creating additional variables to store information. For instance, you must move up, down, left, and right (or north, south, west, and east). Creating Position objects to represent these movements is perfectly acceptable. You will also want to create an object that is the walker of the maze. This walker keeps the current position in the maze.

Other than push, pop, and peek on the Stack class, isEmpty is also a useful method.

The maze class contains a bunch of methods that is meant to help you. Read what the methods do and decide which ones you want to use for your solution. Read the code given to you FIRST before starting to write your code so you can utilize it. It is there to make your life easier, not harder.

Try to translate what you want to do in terms of the stack operations. For instance, if you find yourself at a dead end then you want to move back to a previous position. This means you will need to first pop the top position, which contains the spot located at the dead end, then peek to see where you need to be.

Your stack should be declared and initialized as such:

                Stack<Position> __Give it a name__ = new Stack<Position>();

where you can name it whatever you want.

Moving in a two-dimensional array requires the following math:

Move up (North)	Row + 1
Move down (South)	Row - 1
Move left (West)	Column - 1
Move right (East)	Column + 1

Maze.java class:

public class Maze { private final char[][] maze; private final Position start, end; public Maze(char[][] maze, Position start, Position end) { this.maze = maze; if (validPosition(start)) { this.start = start; } else { throw new PositionNotValidException("The start position is valid for the maze: " + start); } if (validPosition(end)) { this.end = end; } else { throw new PositionNotValidException("The stop position is valid for the maze: " + end); } } public Position getStart() { return start; } public Position getEnd() { return end; } public int numRows() { return maze.length; } public int numCols(int row) { return maze[row].length; } public boolean validPosition(int row, int col) { if (row >= 0 && row < maze.length) { if (col >= 0 && col < maze[row].length) { return true; } } return false; } public boolean validPosition(Position pos) { return validPosition(pos.getRow(), pos.getColumn()); } public char getAt(Position pos) { if (validPosition(pos)) { return maze[pos.getRow()][pos.getColumn()]; } else { String msg = String.format("The position given is not valid: %s", pos.toString()); throw new PositionNotValidException(msg); } } public char getAt(int row, int column) { if (validPosition(row, column)) { return maze[row][column]; } else { String msg = String.format("The row and column given is not valid: row %d col %d", row, column); throw new PositionNotValidException(msg); } } public void setAt(Position pos, char c) { if (validPosition(pos)) { setAt(pos.getRow(), pos.getColumn(), c); } else { String msg = String.format("The position given is not valid: %s", pos.toString()); throw new PositionNotValidException(msg); } } public void setAt(int row, int column, char c) { if (validPosition(row, column)) { maze[row][column] = c; } else { String msg = String.format("The row and column given is not valid: row %d col %d", row, column); throw new PositionNotValidException(msg); } } public Maze clone() { char clone[][] = new char[maze.length][]; for (int r = 0; r < maze.length; r++) { clone[r] = new char[maze[r].length]; for (int c = 0; c < maze[r].length; c++) { clone[r][c] = maze[r][c]; } } return new Maze(clone, start, end); } public String toString() { StringBuffer sb = new StringBuffer(); for (int r = 0; r < maze.length; r++) { sb.append(maze[r]); sb.append("\n"); } return sb.toString(); } }

MazeSolver.java:

import java.util.Stack; public class MazeSolver { public static Position[] solve(Maze maze) { return null; } }

Position.java

public class Position { private int row; private int column; public Position(int row, int column) { this.row = row; this.column = column; } public boolean equals(Object obj) { if (obj == null) { return false; } if (!(obj instanceof Position)) { return false; } Position otherPosition = (Position) obj; return (otherPosition.row == row && otherPosition.column == column); } public String toString() { return "row:" + row + " column:" + column; } public int getRow() { return row; } public int getColumn() { return column; } }

PositionNotValidException.java

public class PositionNotValidException extends RuntimeException { public PositionNotValidException() { super(); } public PositionNotValidException(String msg) { super(msg); } private static final long serialVersionUID = 4006004488727731444L; }

Answer 1

So in this Program I will be explaining each and every steps of the program and writing down the comments in the program so that you can understand the code more properly my works is to have you proper understanding of the code so I will be first giving the puesdo code so that you know the procedure and then after you approach the code and if you have any query regarding this ask your query in comment I will be there to solve your query as soon as possible I hope you like it

ALGORITHM puesdo code is here

Step 1:Create the package for holding the application.

Step 2• Import the utility package for the stack operation.

Step 3 Create the class TraverseThePathOfMaze for the main application.

Step 4 Create the initialization value final static char T=' ', Z='x', L='s', F='e', P='.'; for the input series.

•Step 5 Stack visitmatrix = new Stack()is used for continuous Stack value operation .

Step 6• Take the private static char[][] valuepath for integer as input from the user.

Step 7• The value is converted to clear path for maze operation.

Step 8• All the input value are created a path value through the visitmatrix.push(new pointmaze(MAZE_R, MAZE_C)) path .

step: 2 of 8

Program:

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

* Stack based algorithm to find a path through a maze in *

* Java. *

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

Start the stack based operation through maze. Import the Java utility package for stack operation. The java utility for chain of data the linked list chain concept is applied here.

import java.util.Stack;

import java.util.LinkedList;

The class TraverseThePathOfMaze for selecting the path.

public class TraverseThePathOfMaze {

/* The character initialization of the maze */

final static char T=' ', Z='x', L='s', F='e', P='.';

/* The maze structure with row and column */

final static int MAZE_R = 1, MAZE_C = 1;

/* The path maze structure with row and column */

final static int PATHMAZE_R = 2, PATHMAZE_C = 9;

/* The input maze value path */

private static char[][] valuepath = {

{Z, Z, Z, Z, Z, Z, Z, Z, Z, Z},

{Z, L, T, T, T, T, T, T, T, Z},

{Z, T, T, T, Z, T, Z, Z, T, F},

{Z, T, Z, Z, Z, T, Z, Z, T, Z},

{Z, T, T, T, T, Z, Z, Z, T, Z},

{Z, Z, Z, Z, T, Z, Z, Z, T, Z},

{Z, Z, Z, Z, T, Z, T, T, T, Z},

{Z, Z, T, Z, T, Z, Z, T, T, Z},

{Z, Z, T, T, T, T, T, T, T, Z},

{Z, Z, Z, Z, Z, Z, T, Z, Z, Z}

};

/* the size of the maze */

public int size() {

/* return the length of the maze*/

return valuepath.length;

}

The function print() is used to print the path and the nested for loop inside it, is used for iteration row and column wise.

/* function to print the path in maze */

public void print()

{

/* The loop for the traversing */

/* double for loop are used for the row and column */

for (int a=0; a

/* The path of the column */

for (int b=0; b

/* The by default maze or valuepath is ready to

print */

System.out.print(valuepath[a][b]);

/* The currentsible path of the maze */

System.out.print(' ');

}

/* The valupath print */

System.out.println();

}

}

/*The traversing path of the data */

public char traverse(int a, int b, char data) {

/* The all points if the maze */

assert(search(a,b));

/* The val is set for the maze path*/

char val = valuepath[a][b];

/* data is locate to the maze */

valuepath[a][b] = data;

/* return the val */

return val;

}

The traversing of the main point and the data set is done using traverse method. It return the value of the traversing data.

step: 3 of 8

public char traverse (pointmaze current, char data) {

/* Return the value of the traversing data */

return traverse(current.a(), current.b(), data);

}

/* The processed path of the maze */

public boolean istraverseed(int a, int b) {

/* Row and column are located */

assert(search(a,b));

/* The matrix return the origin possible path */

return (valuepath[a][b] == P);

}

/* The current processed data of the maze */

public boolean istraverseed(pointmaze current) {

/* The maze data of the path value */

return istraverseed(current.a(), current.b());

}

/* The visit path of the maze */

public boolean visit(int a, int b) {

/* The main search value */

assert(search(a,b));

/* print the path with depend on blocked point */

return (valuepath[a][b] != Z && valuepath[a][b] != P);

}

/*The current value of the visited block of the maze*/

public boolean visit(pointmaze current) {

/* return the current matrix position */

return visit(current.a(), current.b());

}

The main part for checking the possible path of the maze is done using search() method. Inside search, if conditional statement is used to check the possible path exist or not.

public boolean search(int a, int b) {

/* if path passible to this maze */

if (a >= 0 && a= 0 && b

return true;

/* else retun false message */

else return false;

}

/* if path possible, print the data */

public boolean search(pointmaze current) {

/* The path value of the search */

return search(current.a(), current.b());

}

/* The clear path of the maze */

public boolean clearpath( int a, int b) {

/* The path matrix value of the clear path */

return (a== TraverseThePathOfMaze.PATHMAZE_R &&

b == TraverseThePathOfMaze.PATHMAZE_C);

}

/* The point and current maze */

public boolean clearpath(pointmaze current) {

/* The already clear path of the value */

return clearpath(current.a(), current.b());

}

/* Copy the maze value */

public char[][] copy() {

/* The maze copy function */

char[][] mazeCopy = new char[size()][size()];

Nested for loop is used for the path of the matrix. After each iteration copy old value path into new maze.

/* The path size of matrix */

for (int a=0; a< size(); a++)

for (int b=0; b

/* the old valupath copy to new maze */

mazeCopy[a][b] = valuepath[a][b];

/* return the path value */

return mazeCopy;

}

/* The final path value are located */

public void locate(char[][] finalPath) {

/* The row and column of the matrix */

for (int a=0; a< size(); a++)

for (int b=0; b

/* the final path value */

valuepath[a][b] = finalPath[a][b];

}

Main class starts here in which object of class path is created and print the path using valuepath.print().

public static void main(String[] args) {

/* the result of the path */

TraverseThePathOfMaze valuepath = new

TraverseThePathOfMaze();

/* Print the path */

valuepath.print();

/* if the path is present in maze */

System.out.println("\n\n A Path is Exist using Stack

operation : ");

/* The stack path of the maze */

valuepath.stackpath();

/* Alternative path with final value */

System.out.println("\n\n Final Recursive Visited Path

: ");

/* The final visited recursive path */

valuepath.recursivepath();

}

/* The stac function for the vist */

public void stackpath() {

/* The final visted path */

char[][] finalPath = copy();

The stack operation to search the path if it exist. The same up, down, left and right procedure are applied to traverse the blocked path.

/* The use of the stack in the program*/

/* The stack visitmatrix */

Stack visitmatrix = new Stack();

/* The starting point of the stack */

visitmatrix.push(new pointmaze(MAZE_R, MAZE_C));

/* The header and the cursor for visit */

pointmaze header, cursor;

/* Check , if the matrix is empty */

while (!visitmatrix.empty()) {

/* The pop operation of the stack */

header = visitmatrix.pop();

/* the clear function if the path is visited */

if (clearpath(header)) break;

/* if final point selected , the path located */

traverse(header, P);

/* The positional movement of the path */

/*up traversed */

cursor = header.up();

if (search(cursor) && visit(cursor))

visitmatrix.push(cursor);

/* left traversed */

cursor = header.left();

if (search(cursor) && visit(cursor))

visitmatrix.push(cursor);

/* right traversed */

cursor = header.right();

if (search(cursor) && visit(cursor))

visitmatrix.push(cursor);

/* down traversed */

cursor = header.down();

if (search(cursor) && visit(cursor))

visitmatrix.push(cursor);

}

/* path existance */

if (!visitmatrix.empty())

/* if path found */

System.out.println("A possible Path Found ");

/* if path not found */

else System.out.println("If possible path is missing

");

/* print the value */

print();

/* the final valuepath */

locate(finalPath);

}

The final all selecting path are used to set the result path. The final selecting path is used to visit operation in the maze.

/* The final recursive value path */

public void recursivepath() {

/* The all possible path */

if (result(new pointmaze(MAZE_R, MAZE_C)))

/* if path found */

System.out.println("Final Recursive Path Found:

");

/* if path not found */

else System.out.println("If possible path is

missing.");

/* print the value */

print();

}

/* the result function of the value */

public boolean result(pointmaze current) {

/* all the possibilities are located */

if (!search(current)) return false;

if (clearpath(current)) return true;

if (!visit(current)) return false;

/* the current position */

assert(visit(current));

/* full traverse complete */

traverse(current, P);

/* down traversed */

if (result(current.down())) {

return true; }

/* right traversed */

if (result(current.right())) {

return true;

step: 4 of 8

}

/* up traversed */

if (result(current.up())) {

return true;

}

/* left traversed */

if (result(current.left())) {

return true;

}

/* the point value */

traverse(current, T);

/* if all possibilities are nil */

return false;

}

};

/* outer class*/

/* the main maze point analysis */

class pointmaze {

int a, b;

/* the row and column point */

public pointmaze(int a, int b) {

/* the value are acopied */

this.a = a;

this.b = b;

};

/* return row value */

public int a() { return a;}

/* return column value */

public int b() { return b;}

/* print the result */

public void print() {

System.out.println("(" + a + "," + b + ")");

}

/* up traversing */

public pointmaze up() {

return new pointmaze(a-1, b);

}

/* down traversing */

public pointmaze down() {

return new pointmaze(a+1, b);

}

/* left traversing */

public pointmaze left() {

return new pointmaze(a, b+1);

}

/* right traversing */

public pointmaze right() {

return new pointmaze(a, b-1);

}

/* end of program */

}; /*end of operation */

step: 5 of 8

Sample Output:

x x x x x x x x x x

x s x

x x x x e

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

The firs (s) is denoted for the source or the starting point of the maze. At the right hand side the exit(e) position is located

step: 6 of 8

A Path is Exist using Stack operation:

A possible Path Found

x x x x x x x x x x

x . x

x . x x x . e

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

The possible path using stack. All the effective nodes are visited and selected.

step: 7 of 8

Final Recursive Visited Path:

Final Recursive Path Found:

x x x x x x x x x x

x . x

x . x x x . e

x . x x x x x . x

x . . . . x x x . x

step: 8 of 8

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

The final result and original selected path in the maze .