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.

Don't forget to correctly use {} in your if/else statements. — Alexis C.
I edited code, did it fix what you meant? and is the visited[][] look like it is being done correctly? — user2745043
Why don't you just run it and see if it's correct? Though personally I'd prefer to have the base case at the beginning of the method rather than at invocation. — Zong
@ZongZhengLi running code as I have edited above gives a null pointer exception, any ideas? — user2745043

Zong Zong · Accepted Answer · 2013-11-19T18:26:21

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.

maze solver using recursion

1 Answers