Trying Write Recursive Method Backtrack Steps Maze Program Needs Print Path Exit Maze Code Q26268330

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.

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<Position> stack = newLinkedList<Position>();

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<maze.getRows(); i++) {

for (int j=0; j<maze.getColumns(); 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, intcurrentY) {

// 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[][] atthis 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<Position> 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 < 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 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 < 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 = “n”;

for (int row=0; row < grid.length; row++)
{
for (int column=0; column < grid[row].length; 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);

}

}

“We Offer Paper Writing Services on all Disciplines, Make an Order Now and we will be Glad to Help”

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published.