I am trying to write a recursive method to backtrack the steps in a maze. The pr
ID: 3876854 • Letter: I
Question
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 sample 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);
}
}
Explanation / Answer
the code has modified and corrected
import java.util.*;
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.*;
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;
}
}
-------------------------------------------------------------------------------------------------
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.
*/
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);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.