Maze recursion solving StackOverflow error

Question

I'm trying to solve a maze using recursion. It's declared Cell [][] maze.

public class Cell {
    private Wall left;
    private Wall right;
    private Wall up;
    private Wall down;
    private boolean end;

    // Setters and getters not shown
}

If there is no Wall for some side of the cell then it has value null, else it refers to a Wall object. Wall references are consistent: Both cells adjacent to single wall refer to it with the appropriate fields. If a wall is missing, then both adjacent cells have corresponding null entries. Here is the search:

public boolean solveMaze(Cell[][] maze, int i, int j) {

    if (maze[i][j].isEnd()){
        System.out.println(maze[i][j].toString());
        return true;
    }
    if (maze[i][j].getDown() == null) {
        return solveMaze(maze, i, j + 1); 
    }
    if (maze[i][j].getUp() == null) {
        return solveMaze(maze, i, j - 1) ;
    }
    if (maze[i][j].getLeft() == null) {
        return solveMaze(maze, i - 1, j);
    }
    if (maze[i][j].getRight() == null) {
        return solveMaze(maze, i + 1, j) ;  
    }
    return false;
}

I'm getting a Stack Overflow error. What is wrong with my recursion stop condition?

Update:

With your highly appreciated help I solved this problem: This is correct solution which works flawless:

public boolean solveMaze(Cell[][] maze, int i, int j){

    if (maze[i][j].isEnd()){
        System.out.println("Maze Exit :["+i+","+j+"]" );
        return true;
    }

    if (maze[i][j].isVisited()){
        return false;
    }

    maze[i][j].setVisited(true);

    if ((maze[i][j].getButtom() == null) ){
        if (solveMaze(maze,i,j+1)==true)
            return true;
    }

    if ((maze[i][j].getUp() == null) ){
    if ( solveMaze(maze,i,j-1) ==true )
        return true;
    }

    if ((maze[i][j].getLeft() == null)){
        if (solveMaze(maze,i-1,j))
            return true;
    }

    if ((maze[i][j].getRight() == null)){
        if (solveMaze(maze,i+1,j)) 
            return true;
    }

    maze[i][j].setVisited(false);
    return false;
} 

may be it will be helpful for any body in the future.

Answer 1

If the maze has a cycle, the solver can run around this cycle forever, which will cause the stack overflow you're seeing. You need a way of determining when you're seeing a maze square that's already been seen. In this case you should backtrack immediately.

This can be done either with a boolean flag visited in each cell initially set to false and then set true for each square you search, or you can maintain a separate Set of (i,j) pairs that have been searched, which is initially empty.

NB: Your use of i and j is unconventional. If someone else wrote the maze reading code with the conventional usage, this could be causing a problem. In math, i is usually used for the row number and j for the column. With this convention your wall tests do not agree with your increments and decrements. Missing the bottom wall would require you to increment i for example.

Answer 2

It seems to me like you're running in circles in your solver method.
I suggest you familiarize yourself with Breadth-First Search, which is often used for not too big state-search problems.

If you have some "knowledge", a heuristic, on how to search the maze then you might also take a look at A-Star Search

---

What BFS could do in your case is the following: (BTW, be nice and use appropriate construtors, getters and setters)

public class Cell {
    public int x;
    public int y;
    public Cell parent;

    @Override
    public boolean equals(Object obj) {
        // TODO Override equals so it only incudes x and y coorinates, and not parent
        return true;
    }

    @Override
    public int hashCode() {
        // TODO Override hash code as well
        return 0;
    }
}

---

public Cell seachFor(Cell start, Cell finish) {
    Queue<Cell> open = new LinkedList<>();
    Set<Cell> closed = new HashSet<>();

    open.add(start);

    while (!open.isEmpty()) {
        Cell current = open.poll();
        if (current.equals(finish)) {
            return current;
        }

        closed.add(current);

        for (Cell neighbour : getNeighbours(current)) {
            if (!closed.contains(neighbour)) {
                open.add(neighbour);
            }
        }
    }

    return null;

}

---

private List<Cell> getNeighbours(Cell current) {
    /* TODO Set the neighbour's "parent"
     * Return valid adjacent neighbour cells
     */
    return null;
}

---

public Deque<Cell> pathfinder(Cell start) {
    Deque<Cell> path = new ArrayDeque<>();
    path.push(start);

    Cell current = start;

    while (current.parent != null) {
        current = current.parent;
        path.push(current);
    }

    return path;
}

---

public static void main(String[] args) {
    Cell start = maze.getStart();
    Cell finish = maze.getFinish();
    Deque<Cell> path = pathFinder(searchFor(start, finish))
    while (!path.isEmpty()) {
        Cell current = path.pop();
        maze.moveTo(current);
    }
}

---

Note that this is a mock code and you need to refine it before it works.