A First Recursive Search

There is a way to think about solving a maze that leads to a simple recursive solution. The idea is to check whether the cell we are standing on is the exit. If not, run the same maze-solving method from each of the adjacent cells. We can think of each adjacent cell as the start of a smaller maze than the one that includes the current cell.

From each cell, we will try the four adjacent cells in turn, without checking them first. So some of those steps will be invalid moves. Every time we arrive on a cell, we do three quick checks before trying to move again:

  1. If the cell is outside the maze, the step that brought us here went off the edge. That was an invalid move, so there is no path from here.
  2. If the cell is a wall, the step that brought us here went into a wall. That was also an invalid move, so there is no path from here.
  3. If the cell is the exit, we have solved the maze.

What I mean by “solved the maze” is that we have found a path from the start to the exit.

If the cell is not outside the maze, not a wall, and not the exit, then we can perhaps stay at the cell and ask a friend to solve the maze from one of the adjacent cells. If any of those adjacent cells can lead us to the exit, then we have solved the maze because we could move to that cell and then follow the path from there to the exit.

Now replace the “ask a friend” part with “call the same method recursively”. That gives us a recursive search. The method will take the maze and the current position as parameters. Here is a first version:

public static boolean hasPath(char[][] maze) {
  return search(maze, 0, 0);
}

private static boolean search(char[][] maze, int row, int col) {
  if (!isOpen(maze, row, col)) {
    return false;
  }
  if (isExit(maze, row, col)) {
    return true;
  }

  return search(maze, row, col + 1)  // right
      || search(maze, row + 1, col)  // down
      || search(maze, row, col - 1)  // left
      || search(maze, row - 1, col);  // up
}

The base cases are the two if statements. We defined isOpen and isExit in the previous section.

After the base cases, the method tries the four possible next moves, in the order right, down, left, up. There is nothing special about this order. It only says which direction we try first, and you can change it however you like. A different order can find a different path in the same maze.

The || operator in the return statement is useful here because it stops as soon as one side is true. If moving right eventually reaches the exit, the method does not try down, left, or up.

This first version follows the idea, but it has a problem. Suppose the maze starts like this:

┌───┬───┬───┐
│ S │   │ █ │
├───┼───┼───┤
│   │ █ │ E │
└───┴───┴───┘

From (0, 0), the method tries right to (0, 1). From (0, 1), right and down both fail, so it tries left back to (0, 0). From (0, 0), it tries right again. The method keeps moving between (0, 0) and (0, 1) until the program crashes with a StackOverflowError, and it never returns to the original call to try moving down from the start.

The problem is that the search has no memory. It must remember where it has already been.