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.

Answer 3

You do not have anything in your code to detect places you've already been before. If your maze contains any passages in which you can go in a circle or loop back to someplace you've been before without backtracking, it will continue to recurse down that same path infinitely.

Answer 4

your running out of memory allocated on the stack. aka your recursion is multiply too fast where you exceed the resources of the JVM at the given time.

you can increase memory and then kill all the other iterations of this method, or change your algorithim. Changing the stacksize would be a poor solution but it may work even though your code if flawed howto increase the stacksize in eclipse I would suggest marking which areas you already visited

the maze is Cell[][] maze

  public class Cell{
    boolean visited = false;
    Wall left;
    Wall right;
    Wall up;
    Wall bottom;
    boolean end;

    //Settters and Getters
    }

set that visited variable to true each time you hit it and then change your code to

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].getButton() == null)&&(maze[i][j].visited==false)){
            return solveMaze(maze,i,j+1); 
        }

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

I wont implement it unless you have issues doing it yourself, with interview questions I think its neat if you solve them yourself with hints that way you get the feeling that you could solve something similar again, where if you just read and understand an answer you may be able to reiterate the answer to the same problem but you may not be able to come up with a novel answer to a similar problem using similar strategies.

Answer 5

First you go down until you reach a wall. Then, one up - then down again. And one up, and one down - until java detects that this is pretty silly and stops with a StackOverFlowError ;)