I am trying to write a recursive method to backtrack the stepsin a maze. The program needs to print the path to exit the maze.The code below is what I have so far. It works as far as solvingthe maze but it will not “delete” the steps it found at a dead end.Any idea how I can get this code to stop adding a “2” in my int[][]path. I am using path to collect all the correct locations bymarking that spot on the maze (path[row][column]) with a 2. Thecode in question is my traceRoute() method. Here is an example of a maze: 21 35

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 01

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 10

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 01

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 11

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 01

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 10

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 11

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 10

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 01

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 01

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 10

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 01

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 11

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 11

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 01

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 11

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 11

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 10

1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 01

1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 11

0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 01 import java.util.*; /** * MazeSolver attempts to recursively traverse a Maze. The goalis to get from the * given starting position to the bottom right, following a pathof 1’s. Arbitrary * constants are used to represent locations in the maze thathave been TRIED * and that are part of the solution PATH. * * @author Lewis and Chase * @version 4.0 */ public class MazeSolver { private Maze maze; private int[][] path;    /** * Constructor for the MazeSolver class. */ public MazeSolver(Maze maze) { this.maze = maze; path = new int[maze.getRows()][maze.getColumns()]; }    /** * Attempts to recursively traverse the maze. Inserts special * characters indicating locations that have been TRIED andthat * eventually become part of the solution PATH. * * @param row row index of current location * @param column column index of current location * @return true if the maze has been solved */ public boolean traverse() { boolean done = false; int row, column; Position pos = new Position(); Deque stack = newLinkedList(); stack.push(pos);    while (!(done) && !stack.isEmpty()) { pos = stack.pop(); maze.tryPosition(pos.getx(),pos.gety()); // this cell has beentried if (pos.getx() == maze.getRows()-1 && pos.gety() ==maze.getColumns()-1) { done = true; // the maze is solved    //run the traceroute method if(traceRoute(maze, 0, 0) == true) { System.out.println(“SOLVED USING THIS PATH: “); for (int i=0; i

= 0 && currentX = 0 &&currentY stack) { Position npos = new Position(); npos.setx(x); npos.sety(y); if (maze.validPosition(x,y)) stack.push(npos); }    } ————————————————————————————————————————— import java.util.*;

import java.io.*; /**

* Maze represents a maze of characters. The goal is to get fromthe

* top left corner to the bottom right, following a path of 1’s.Arbitrary

* constants are used to represent locations in the maze that havebeen TRIED

* and that are part of the solution PATH.

*

* @author Lewis and Chase

* @version 4.0

*/

public class Maze

{

private static final int TRIED = 2;

private static final int PATH = 3; private int numberRows, numberColumns;

private int[][] grid; /**

* Constructor for the Maze class. Loads a maze from the givenfile.  

* Throws a FileNotFoundException if the given file is notfound.

*

* @param filename the name of the file to load

* @throws FileNotFoundException if the given file is notfound

*/

public Maze(String filename) throws FileNotFoundException

{

Scanner scan = new Scanner(new File(filename));

numberRows = scan.nextInt();

numberColumns = scan.nextInt();

  

grid = new int[numberRows][numberColumns];

for (int i = 0; i

for (int j = 0; j

grid[i][j] = scan.nextInt();

}

  

/**

* Marks the specified position in the maze as TRIED

*

* @param row the index of the row to try

* @param col the index of the column to try

*/

public void tryPosition(int row, int col)

{

grid[row][col] = TRIED;

}

  

/**

* Return the number of rows in this maze

*

* @return the number of rows in this maze

*/

public int getRows()

{

return grid.length;

}

  

/**

* Return the number of columns in this maze

*

* @return the number of columns in this maze

*/

public int getColumns()

{

return grid[0].length;

}

  

/**

* Marks a given position in the maze as part of the PATH

*

* @param row the index of the row to mark as part of the PATH

* @param col the index of the column to mark as part of thePATH

*/

public void markPath(int row, int col)

{

grid[row][col] = PATH;

} /**

* Determines if a specific location is valid. A validlocation

* is one that is on the grid, is not blocked, and has not beenTRIED.

*

* @param row the row to be checked

* @param column the column to be checked

* @return true if the location is valid   

*/

public boolean validPosition(int row, int column)

{

boolean result = false; // check if cell is in the bounds of the matrix

if (row >= 0 && row

column >= 0 && column

if (grid[row][column] == 1)

result = true; return result;

} /**

* Returns the maze as a string.

*

* @return a string representation of the maze

*/

public String toString()

{

String result = “n”; for (int row=0; row

{

for (int column=0; column

result += grid[row][column] + “”;

result += “n”;

} return result;

}

} ————————————————————————————————- /**

* @author Lewis and Chase

*

* Solution to Programming Project 4.6.

*/

public class Position

{

private int x;

private int y; /**

* Constructs a position and sets the x & y coordinates to0,0.

*/

Position ()

{

x = 0;

y = 0;

} /**

* Returns the x-coordinate value of this position.

* @return int the x-coordinate of this position

*/

public int getx()

{

return x;

} /**

* Returns the y-coordinate value of this position.

* @return int the y-coordinate of this position

*/

public int gety()

{

return y;

} /**

* Sets the value of the current position’s x-coordinate.

* @param a value of x-coordinate

*/

public void setx(int a)

{

x = a;

} /**

* Sets the value of the current position’s x-coordinate.

* @param a value of y-coordinate

*/

public void sety(int a)

{

y = a;

}

} ———————————————————————————————————————– import java.util.*; import java.io.*; /** * MazeTester uses recursion to determine if a maze can betraversed. * * @author Lewis and Chase * @version 4.0 */ public class MazeTester { /** * Creates a new maze, prints its original form, attempts to * solve it, and prints out its final form. */ public static void main(String[] args) throwsFileNotFoundException { Scanner scan = new Scanner(System.in); System.out.print(“Enter the name of the file containing themaze: “); String filename = scan.nextLine();    Maze labyrinth = new Maze(filename);    System.out.println(labyrinth);    MazeSolver solver = new MazeSolver(labyrinth); if (solver.traverse()) System.out.println(“The maze was successfully traversed!”); else System.out.println(“There is no possible path.”); System.out.println(labyrinth); } } . . .