# Is this a true backtracking algorithm?

Posted on

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

initRowPosition = initRow;
initColPosition = initCol;
}

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];
int tCol = moveLocs[r];
if (isValid(tRow, tCol)){
Cell neighbor = new Cell(tRow, tCol);
}
}
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{
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.