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).
mazeData.txt
so that we can try out your code ourselves? – Simon Forsberg♦ May 31 '14 at 10:26Cell
class andMain
. – naitsirc May 31 '14 at 12:52