I am trying to write a recursive method to backtrack the steps in 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 solving the 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 by marking that spot on the maze (path[row][column]) with a 2. The code 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 0 1 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 1 0 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 0 1 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 1 1 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 0 1 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 1 0 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 1 1 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 1 0 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 0 1 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 0 1 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 1 0 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 0 1 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 1 1 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 1 1 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 0 1 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 1 1 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 1 1 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 1 0 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 0 1 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 1 1 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 0 1

import java.util.*;

/**

* MazeSolver attempts to recursively traverse a Maze. The goal is to get from the

* given starting position to the bottom right, following a path of 1's. Arbitrary

* constants are used to represent locations in the maze that have 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 and that

* 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 = new LinkedList();

stack.push(pos);

while (!(done) && !stack.isEmpty())

{

pos = stack.pop();

maze.tryPosition(pos.getx(),pos.gety()); // this cell has been tried

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

for (int j=0; j

if (path[i][j] == 2) {

System.out.println(i + ", " + j);

}

}

}

}

}

else

{

push_new_pos(pos.getx() - 1,pos.gety(), stack);

push_new_pos(pos.getx() + 1,pos.gety(), stack);

push_new_pos(pos.getx(),pos.gety() - 1, stack);

push_new_pos(pos.getx(),pos.gety() + 1, stack);

}

}

return done;

}

public boolean traceRoute(Maze solvedMaze, int currentX, int currentY) {

// checks if pos is at the end of the maze

if( currentX == solvedMaze.getRows() -1 && currentY == solvedMaze.getColumns()-1 ) {

return true;

}

// checks to see if move is within the maze

if (currentX >= 0 && currentX < solvedMaze.getRows() && currentY >= 0 && currentY < solvedMaze.getColumns()) {

//mark position

path[currentX][currentY] = 2;

//move right

if (traceRoute(solvedMaze, currentX +1, currentY) ) {

System.out.println("right");

return true;

}

//move down

if (traceRoute(solvedMaze, currentX , currentY - 1) ) {

System.out.println("down");

return true;

}

//move left

if (traceRoute(solvedMaze, currentX -1, currentY) ) {

System.out.println("left");

return true;

}

//move up

if (traceRoute(solvedMaze, currentX , currentY +1) ) {

System.out.println("up");

return true;

}

//else if no one direction works out then change path[][] at this location to 1

path[currentX][currentY] = 1;

return false;

}

return false;

}

/**

* Push a new attempted move onto the stack

* @param x represents x coordinate

* @param y represents y coordinate

* @param stack the working stack of moves within the grid

* @return stack of moves within the grid

*/

private void push_new_pos(int x, int y,

Deque 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 from the * top left corner to the bottom right, following a path of 1's. Arbitrary * constants are used to represent locations in the maze that have been 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 given file. * Throws a FileNotFoundException if the given file is not found. * * @param filename the name of the file to load * @throws FileNotFoundException if the given file is not found */ 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 < numberRows; i++) for (int j = 0; j < numberColumns; 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 the PATH */ public void markPath(int row, int col) { grid[row][col] = PATH; }

/** * Determines if a specific location is valid. A valid location * is one that is on the grid, is not blocked, and has not been TRIED. * * @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 < grid.length && column >= 0 && column < grid[row].length)

// check if cell is not blocked and not previously tried 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 = " ";

for (int row=0; row < grid.length; row++) { for (int column=0; column < grid[row].length; column++) result += grid[row][column] + ""; result += " "; }

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 to 0,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 be traversed.

*

* @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) throws FileNotFoundException

{

Scanner scan = new Scanner(System.in);

System.out.print("Enter the name of the file containing the maze: ");

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);

}

}