Problem
So my project was to make an algorithm that finds a path out the maze using “backtracking” to help. This is my first time attempting to solve anything with backtracking so I want to be sure if what I did is actually backtracking and if it is an efficient way to apply it to my problem. Bellow is the main logic:
public void solve(Cell cell){
tempMaze[cell.getRow()][cell.getColumn()] = "!";
ArrayList<Cell> neighbors = getNeighbors(cell);
// If cell is at edge of board a solution is found
if ((cell.getRow() == 0 || cell.getRow() == tempMaze.length-1) || (cell.getColumn() == 0 || cell.getColumn() == tempMaze[0].length-1)){
return;
}
// If cell is in initial position and has no neighbors then quit
if ((cell.getColumn() == initColPosition && cell.getRow() == initRowPosition) && neighbors.size() < 1){
return;
}
// If not in initial position and has no neighbors then backtrack
if ((cell.getColumn() != initColPosition || cell.getRow() != initRowPosition) && neighbors.size() < 1){
result.remove(result.size()-1);
solve(result.get(result.size()-1));
}else if (neighbors.size() >= 1){ // If has neighbors then choose one and call the method again
result.add(neighbors.get(0));
solve(neighbors.get(0));
}
}
This is the results array were I keep all the cells that make up the solution to the maze: ArrayList<Cell> result = new ArrayList<Cell>();
This is where, in theory, my backtracking kicks in: solve(result.get(result.size()-1));
So, for example lets say I moved x
amount of times and my result
contains the following cells: a,b,c,d,e
. Because e
happened to be a good cell to move to I moved to it, however when I recursively call solve(e)
to check further possible moves there are no more neighbors
to move to. Because of this I “backtrack.” So if this would happen my code would delete e
from the result
array and call solve(Cell cell)
with the cell before e
. So now my result
array looks as follows: a,b,c,d
and solve was recursively called with d
like this: solve(d)
. Lets pretend that d
also does not have anymore locations to move to, if this happens same process occurs as with e
. Now my array looks as follows if d
also did not have another valid location, or Cell
, to move to: a,b,c
. This time I call solve(Cell cell)
with c
and pretend that it has a location to move to that is different from d
. If this happens I move to that Cell
and add it to my result
array. This process keeps going until one of my base cases is reached.
So is the way I move to previous moves and look for other solutions backtracking or not? Why is it not considered backtracking if my approach is incorrect? If it is correct did I do this in an acceptable manner? If not why?
I would greatly accept your opinions and suggestions.
The rest of my class (without solve()
method):
public class ThreadTheMaze {
ArrayList<Cell> result = new ArrayList<Cell>();
private String[][] maze;
private String[][] tempMaze;
private int initRowPosition;
private int initColPosition;
private int amtOfRows;
private int amtOfCols;
public ThreadTheMaze(int initRow, int initCol){
initRowPosition = initRow;
initColPosition = initCol;
result.add(new Cell(initRowPosition, initColPosition));
}
public void loadMaze(){
try{
Scanner in = new Scanner(new File("mazeData.txt"));
while (in.hasNextLine()){
amtOfCols = in.nextLine().length();
amtOfRows++;
}
in.close();
maze = new String[amtOfRows][amtOfCols];
in = new Scanner(new File("mazeData.txt"));
for (int r = 0; r < amtOfRows; r++){
String line = in.nextLine();
for (int c = 0; c < amtOfCols; c++){
maze[r][c] = line.substring(0,1);
line = line.substring(1);
}
}
tempMaze = new String[maze.length][];
for (int r = 0; r < tempMaze.length; r++){
tempMaze[r] = maze[r].clone();
}
}catch (FileNotFoundException e){
System.err.print(e);
}
}
public void printMaze(){
for (int r = 0; r < amtOfRows; r++){
for (int c = 0; c < amtOfCols; c++){
System.out.print(maze[r][c]);
}
System.out.println();
}
}
public void updateMaze(){
for (int i = 0; i < result.size(); i++){
maze[result.get(i).getRow()][result.get(i).getColumn()] = "!";
}
}
/**
@return ArrayList of objects 'Cell' that are empty and available to move to.
*/
private ArrayList<Cell> getNeighbors(Cell cell){
ArrayList<Cell> neighbors = new ArrayList<Cell>();
int row = cell.getRow();
int column = cell.getColumn();
int[][] moveLocs = {{row-1, column}, {row+1, column}, {row, column+1}, {row, column-1}};
for (int r = 0; r < moveLocs.length; r++){
int tRow = moveLocs[r][0];
int tCol = moveLocs[r][1];
if (isValid(tRow, tCol)){
Cell neighbor = new Cell(tRow, tCol);
neighbors.add(neighbor);
}
}
return neighbors;
}
public boolean isValid(int row, int col){
if(row < 0 || row >= amtOfRows){
return false;
}
if (col < 0 || col >= amtOfCols){
return false;
}
if (!tempMaze[row][col].equals(" ")){
return false;
}
return true;
}
}
UPDATE:
Main:
public class Main {
public static void main(String args[]) throws IOException{
ThreadTheMaze x = new ThreadTheMaze(5,5);
x.loadMaze();
x.solve(new Cell(5,5));
x.updateMaze();
x.printMaze();
}
}
Cell class:
public class Cell{
private int row;
private int column;
Cell(){}
public Cell(int row, int column){
this.row = row;
this.column = column;
}
public int getRow(){
return row;
}
public int getColumn(){
return column;
}
}
mazeData.txt:
************
*** *****
*** ** ****
*** * ***
** *** ***
** * ** ***
***** ******
***** ****
**** ******
* * ****
* *** *****
* **********
* **********
* **********
Note: requirement was that beginning is always at (5,5).
Solution
It is almost backtracking.
There are two very different reasons for solve
to return: either it got stuck, or it reached the goal. The (recursive) caller should react accordingly: inspect another neighbor or return happily. Your code disregards the reason, and forces the caller to keep inspecting other neighbors.
Besides that, special casing initial position is redundant. If cell has no untested neighbours, return is required anyway. Only the (non-recursive) originator should know which cell was an original one.
To summarize, the code should look along the lines of the pseudocode
public int solve(Cell cell)
{
if (isTarget(cell))
return SOLVED;
mark(cell);
path.append(cell);
for (n in maze.neighbors(cell))
if (solve(n) == SOLVED)
return SOLVED;
path.pop();
return STUCK;
}
PS: That said, the code is broken, so I am voting to close it.