Rat in a Maze

Backtracking O(4^(N²)) O(N²)

Finds a path from the top-left to the bottom-right of a grid, marking the route and undoing it at dead ends.

Rat starts top-left, exit is bottom-right. Walls are dark cells.

1/52

Step onto (0, 0).

InvariantThe marked cells form one open path from the entrance to the current cell, with no repeats.

tryingon pathdead endbacktrack

rat-in-a-maze.c

#define N 4
 
int solve(int maze[N][N], int r, int c, int sol[N][N]) {
    if (r < 0 || c < 0 || r >= N || c >= N ||
        maze[r][c] == 0 || sol[r][c] == 1)
        return 0;
 
    sol[r][c] = 1;
    if (r == N - 1 && c == N - 1)
        return 1;   /* exit reached */
 
    if (solve(maze, r + 1, c, sol)) return 1;   /* down  */
    if (solve(maze, r, c + 1, sol)) return 1;   /* right */
    if (solve(maze, r - 1, c, sol)) return 1;   /* up    */
    if (solve(maze, r, c - 1, sol)) return 1;   /* left  */
    sol[r][c] = 0;   /* backtrack */
    return 0;
}

How Rat in a Maze works

From each cell try the four directions in a fixed order, marking the path as you go and unmarking on retreat. The marks double as a visited check so the search never loops.

When to use it

Path existence in grids and simple maze solving; a stepping stone to BFS/DFS on grids.