Rat in a Maze

Find a path of open cells from the top-left corner of a maze to the bottom-right corner.

The idea

From the current cell, try stepping down, right, up, then left. A step is only taken if it stays on the board, lands on open floor, and has not been visited yet. If none of the four steps reach the goal, undo the visited mark on this cell so a different route through it is possible from elsewhere, and report failure upward.

Code

public static bool Solve(int[][] maze, int r, int c, int n, bool[][] visited) {
    if (r == n - 1 && c == n - 1) { visited[r][c] = true; return true; }
    if (r < 0 || c < 0 || r >= n || c >= n) return false;
    if (maze[r][c] == 0 || visited[r][c]) return false;
    visited[r][c] = true;
    if (Solve(maze, r + 1, c, n, visited) || Solve(maze, r, c + 1, n, visited) ||
        Solve(maze, r - 1, c, n, visited) || Solve(maze, r, c - 1, n, visited)) return true;
    visited[r][c] = false; // backtrack
    return false;
}

Tips

• Marking visited[r][c] before recursing, not after, is what stops the search from walking in a circle between two open cells.
• Trying down and right before up and left is just a convention: any fixed order works, as long as all four are tried.

In the .NET library

Unmarking on failure is essential here, unlike Number of Islands: that problem permanently sinks visited land because it never needs to revisit a cell from a different path. A maze does, since a cell that fails as part of one route might still belong to a different, working route.