maze solver using recursion

Question

I was given some code that builds a maze and whatever else is needed, the abstract maze class contains a abstract method 'makeMove (int row, int col)' this is the method I am trying to write to solve the maze, moving left, right, up, down.

I just started working on this, and below is all I have so far.

int MAX_ROWS = endRow + 1;
int MAX_COLS = endCol + 1;
boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];
protected void makeMove( int row, int col )
{
    boolean found = false;
    //boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];
    //visited[startRow][startCol] = true;
    if (row < 0 || row >= MAX_ROWS  || col < 0 || col >= MAX_COLS  || visited[row][col] || maze[row][col] == 1)
        return;

    visited[row][col] = true;
    found = row == endRow && col == endCol;

    if (!found) {
        makeMove(row, col - 1);
        makeMove(row, col + 1);
        makeMove(row - 1, col);
        makeMove(row + 1, col);
    }

    }
    /*if(row == endRow && col == endCol) {
        found = true;
    }
    if(!found && maze[row][col - 1]!=1 && !visited[row][col]) { // move left
        makeMove(row, col -1);
        visited[row][col -1] = true;
    }
    if(!found && maze[row - 1][col]!=1 && !visited[row-1][col]) { // move up
        makeMove(row-1, col);
        visited[row-1][col] = true;
    }
    if(!found && maze[row][col + 1]!=1 && !visited[row][col + 1]) { // move right
        makeMove(row, col + 1);
        visited[row][col + 1] = true;
    }
    if(!found && maze[row + 1][col]!=1 && !visited[row + 1][col]) { // move down
        makeMove(row + 1, col);
        visited[row + 1][col] = true;
    }*/

Ok I have the code working to where I no longer get the error.

Thanks for any and all help.

Answer 1

boolean[][] visited = null;

declares a local variable. You need to declare it as a member of the class so it can persist between invocations of makeMove. You'll also want to initialize it properly:

boolean[][] visited = new boolean[...][...];

You also need to perform bounds checking. After a few recursive calls you'll hit the edge of the maze and go outside the range of the array.

Thus the code might look like:

int MAX_ROWS = ...
int MAX_COLS = ...

boolean[][] visited = new boolean[MAX_ROWS][MAX_COLS];

protected void makeMove(int row, int col) {
    if (row < 0 || row >= MAX_ROWS 
     || col < 0 || col >= MAX_COLS 
     || visited[row][col] 
     || maze[row][col] == 1)
        return;

    visited[row][col] = true;
    found = row == endRow && col == endCol;

    if (!found) {
        makeMove(row, col - 1);
        makeMove(row, col + 1);
        makeMove(row - 1, col);
        makeMove(row + 1, col);
    }
}

where MAX_ROWS and MAX_COLS correspond to the dimensions of the maze. Note that by default visited is initialized with all false. If you want to call this method multiple times on different mazes, you should wrap it in a method that will reinitialize visited.