Recursive Backtracking

The maze is a char[][] where '#' is a wall and any other character is an open cell. The start is (0, 0) and the exit is the bottom-right cell. One move goes up, right, down, or left by one step, never off the maze and never into a wall.

Two helpers are already written. isOpen(maze, row, col) returns true when (row, col) is inside the maze and not a wall. isExit(maze, row, col) returns true when (row, col) is the exit.

The public method creates the visited array and starts the search at the start cell:

public static boolean hasPath(char[][] maze) {
  boolean[][] visited = new boolean[maze.length][maze[0].length];
  return search(maze, visited, 0, 0);
}

The search tries the four directions in the order right, down, left, up.

Exercise

Write search. It returns true when there is a path from (row, col) to the exit that does not pass through a visited cell.

private static boolean search(
    char[][] maze, boolean[][] visited, int row, int col) {
  // TODO
}

Solution

private static boolean search(
    char[][] maze, boolean[][] visited, int row, int col) {

  if (!isOpen(maze, row, col)) {
    return false;
  }
  if (visited[row][col]) {
    return false;
  }
  if (isExit(maze, row, col)) {
    return true;
  }

  visited[row][col] = true;

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

Exercise

Suppose search neither checks nor sets visited. Describe what happens when hasPath runs on this maze.

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

Solution

The call on (0, 0) tries right and calls search on (0, 1). From (0, 1), right and down are walls, so it tries left and calls search on (0, 0) again. That call tries right again. The two calls keep alternating, each one adding a frame, until the program ends with a StackOverflowError. The original call never gets to try down from the start, so the path along the left column is never found.

Exercise

Trace hasPath on this maze. List the open cells in the order search first enters them.

    0   1   2   3
  ┌───┬───┬───┬───┐
0 │ S │   │   │   │
  ├───┼───┼───┼───┤
1 │   │ █ │ █ │ █ │
  ├───┼───┼───┼───┤
2 │   │   │   │ E │
  └───┴───┴───┴───┘

Solution

(0,0), (0,1), (0,2), (0,3), (1,0), (2,0), (2,1), (2,2), (2,3).

Solution

The calls on (0,3), (0,2), and (0,1) return false after exhausting all four directions, in that order. These returns back the search out of the dead end along the top row. A call on a cell that is already visited returns false right away, without trying any directions. Those returns are not in this list.

Solution

From top to bottom:

top ──▶ search(2,3)
        search(2,2)
        search(2,1)
        search(2,0)
        search(1,0)
        search(0,0)

Solution

Moving forward to a neighbor is a recursive call on that neighbor. A call whose four directions all return false returns false to its caller. The caller then tries its next direction. If the caller has no direction left, it returns false as well. Each return moves the search back one cell. The returns continue until they reach the most recent cell that still has an untried direction. The search ends when a call reaches the exit and true returns through every call on the way back, or when the original call runs out of directions and returns false.