# Is this a true backtracking algorithm?

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

• Could you provide your main method and the mazeData.txt so that we can try out your code ourselves? – Simon Forsberg May 31 '14 at 10:26
• @SimonAndréForsberg Added the Cell class and Main. – Cristian Gutu May 31 '14 at 12:52

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.

• I think I understand now. You are attempting all possible move by using an enhanced for loop and recursively calling each neighbor until you find a solution and break out of the method. Meanwhile you discard any paths that could possibly lead to a solution. Is this right? – Cristian Gutu May 31 '14 at 21:18