Rat in a Maze: Backtracking Algorithm with C++ Code

The rat in a maze problem is a standard backtracking interview question that tests recursive thinking, base-case design, and the ability to correctly restore state when a path fails.

What Is the Rat in a Maze Problem?

You are given an N×N binary grid. Each cell maze[i][j] equals 1 if it is open or 0 if it is blocked. A rat starts at the top-left corner (0, 0) and must reach the bottom-right corner (N-1, N-1). The task is to print one valid path through the grid, or output -1 if none exists.

Backtracking is the direct approach. The algorithm builds the path one cell at a time, marks each cell it includes in a solution matrix, and un-marks it if the path turns out to be a dead end. That un-marking step is the backtrack.

The 4×4 Example Grid

Consider this grid, where 0 cells are blocked and 1 cells are open:

maze[][] = {
  {1, 0, 0, 0},
  {1, 0, 0, 0},
  {1, 1, 1, 1},
  {0, 0, 0, 1}
}

Start: (0,0). Destination: (3,3). One valid path exists: (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (2,3) → (3,3).

The solution matrix for that path marks each visited cell as 1:

1 0 0 0
1 0 0 0
1 1 1 1
0 0 0 1

Backtracking Algorithm: Step by Step

Three components make up the algorithm: a safety predicate, a base case, and the explore-then-backtrack block.

Safety Predicate

A cell (x, y) is safe to enter when all three conditions hold:

• Row index x is within bounds: x >= 0 and x < N.
• Column index y is within bounds: y >= 0 and y < N.
• The cell value maze[x][y] equals 1 (open, not blocked).

bool isSafe(int maze[N][N], int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}

Recursive Logic

Once the safety check passes, the function follows these steps:

• Step 1: If x == N - 1 and y == N - 1, the destination is reached. Mark sol[x][y] = 1 and return true.
• Step 2: Mark sol[x][y] = 1 to include the current cell in the path.
• Step 3: Recurse right — call solveMaze(maze, x, y + 1, sol). If it returns true, return true.
• Step 4: Recurse down — call solveMaze(maze, x + 1, y, sol). If it returns true, return true.
• Step 5: Both directions failed. Set sol[x][y] = 0 (backtrack) and return false.

The key discipline here is Step 5. Without it, the solution matrix would accumulate every cell the algorithm ever tried, not just the cells on the actual path.

C++ Implementation

The full program below uses a #define N 4 for the grid size. In production code you would pass N as a parameter; for placement interviews the fixed macro is acceptable.

#include <iostream>
using namespace std;

#define N 4

void printSolution(int sol[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << sol[i][j] << " ";
        cout << "\n";
    }
}

bool isSafe(int maze[N][N], int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}

bool solveMaze(int maze[N][N], int x, int y, int sol[N][N]) {
    // Base case: destination reached
    if (x == N - 1 && y == N - 1 && maze[x][y] == 1) {
        sol[x][y] = 1;
        return true;
    }
    if (isSafe(maze, x, y)) {
        sol[x][y] = 1;                                     // include cell
        if (solveMaze(maze, x, y + 1, sol)) return true;  // move right
        if (solveMaze(maze, x + 1, y, sol)) return true;  // move down
        sol[x][y] = 0;                                     // backtrack
        return false;
    }
    return false;
}

int main() {
    int maze[N][N] = {
        {1, 0, 0, 0},
        {1, 0, 0, 0},
        {1, 1, 1, 1},
        {0, 0, 0, 1}
    };
    int sol[N][N] = {0};
    if (!solveMaze(maze, 0, 0, sol))
        cout << "-1\n";
    else
        printSolution(sol);
    return 0;
}

Running this on the 4×4 grid produces the solution matrix shown in the problem statement:

1 0 0 0
1 0 0 0
1 1 1 1
0 0 0 1

Tracing the 4×4 Example

Walking through the recursive calls shows exactly where the algorithm goes and why it does not need to backtrack on this input:

• solveMaze(0, 0): maze[0][0] = 1, mark sol[0][0] = 1. Try right: (0,1) has maze[0][1] = 0, fails isSafe. Try down: (1,0).
• solveMaze(1, 0): maze[1][0] = 1, mark sol[1][0] = 1. Try right: (1,1) = 0, blocked. Try down: (2,0).
• solveMaze(2, 0): maze[2][0] = 1, mark sol[2][0] = 1. Try right: (2,1) = 1. Move right.
• solveMaze(2, 1): mark sol[2][1] = 1. Try right: (2,2) = 1. Move right.
• solveMaze(2, 2): mark sol[2][2] = 1. Try right: (2,3) = 1. Move right.
• solveMaze(2, 3): mark sol[2][3] = 1. Try right: (2,4) out of bounds, fails isSafe. Try down: (3,3) = 1.
• solveMaze(3, 3): x == N-1 and y == N-1 and maze[3][3] = 1. Mark sol[3][3] = 1. Return true.

Each return true propagates up the call stack unchanged. The solution matrix is complete. Because the single valid path succeeded on first attempt, Step 5 (backtrack) never executes on this input. A denser grid with more dead ends would trigger it at several points along the way.

Time and Space Complexity

For the formal derivation framework, see FACE Prep’s space complexity guide. For the right/down rat-in-a-maze specifically:

• Time complexity: At each of the N² cells, the algorithm chooses between at most 2 directions. In the worst case every combination of cells is explored, giving O(2^(N²)). In practice the safety check prunes dead ends early, so actual runtime stays well below this ceiling.
• Space complexity: O(N²) for the sol[][] solution matrix, plus O(N²) for the recursion stack in the worst case (a winding path through every cell). Total auxiliary space is O(N²).

Both figures belong in your written answer during a placement interview: examiners deduct marks for citing time complexity only.

Common Interview Variations

Placement rounds, including the advanced section of AMCAT Automata, add these variants to the core problem. Knowing them saves you from being caught off-guard by a follow-up.

All Four Directions

Extend movement to right, left, down, and up. Add a visited[N][N] array initialised to all zeros. Before entering any cell, add visited[x][y] == 0 as a fourth condition in isSafe. Set visited[x][y] = 1 before the recursive calls and reset it to 0 after the recursive calls (a second backtrack step). Without the visited array, the four-direction version cycles through previously visited cells and the recursion never terminates.

Print All Paths

To enumerate every valid path, remove the early return on success. When the destination is reached, call printSolution(sol), then un-mark sol[N-1][N-1] and return false so the recursion continues. This collect-and-continue pattern shows up across backtracking problems: finding all symmetric pairs in an array uses the same structure in its brute-force enumeration version.

Count Solutions Only

If only the total count of valid paths is needed, replace the solution matrix with a counter. Increment when the destination is reached, then return false. No matrix to maintain, no print step. This variant is common in written rounds alongside problems like the equilibrium index, where both problems demand tracking a running state variable across a traversal without storing the full intermediate structure.

The maze-solving algorithm family includes depth-first search, wall-follower, and Pledge’s algorithm. The backtracking version you have just implemented is a depth-first search with explicit state restoration, which is the clearest framing to use in an interview.

The mark-then-backtrack pattern in this solution captures something beyond maze navigation: systematic exploration with state management. Language models use beam search on the same principle, keeping partial token sequences that score above a threshold and discarding the rest. TinkerLLM at ₹299 gives you a hands-on playground to run model experiments and observe directly how search strategy changes what the model produces, starting from the same explore-and-prune intuition you just built here.