DAY 22: Mastering Recursion with Backtracking, Rat in Maze, and N Queens Problem | My DSA Journey – Recursion

---

Introduction

Welcome to Day 22 of my DSA Journey!
Over the past few weeks, I’ve been diving deep into one of the most fundamental and powerful concepts in data structures and algorithms — Recursion.

I explored Backtracking and solved classic problems like Rat in a Maze and the N Queens problem. These challenges helped me understand how recursion, combined with backtracking, can be used to solve complex problems efficiently.

I'm sharing my journey publicly to stay consistent in my learning and to help others who are starting their own DSA path from scratch.

Here’s what I learned over the last 3 days:

Day 19

• Backtracking

Day 20

• Rat in a Maze Problem

Day 21

• N Queens Problem

Let’s break down each of these topics below 👇

---

1. Backtracking :

In my previous DSA blog, I solved problems like:

• Letter Combinations of a Phone Number
• Dice Throw
• Permutations (with both visited array and in-place swapping)
• Palindrome Partitioning

All of these solutions applied Backtracking in one form or another — even before I fully understood the depth of the technique.
Now that I've studied it thoroughly, here’s a complete breakdown of Backtracking — what it is, how it works, and when to use it.

What is Backtracking?

Backtracking is a problem-solving technique that incrementally builds candidates to the solution and abandons ("backtracks") a path as soon as it determines that it won't lead to a valid solution.

It’s a refined version of brute force that avoids unnecessary paths by applying constraints early.

How Does Backtracking Work?

At its core, backtracking follows this process:

1. Choose: Make a choice (e.g., pick a number, letter, etc.)
2. Explore: Recursively proceed with that choice

3. Un-choose (Backtrack): If it doesn’t lead to a valid solution, undo the choice and try something else

   void backtrack(parameters) {
    if (solution found) {
        store or print the solution
        return;
    }
   
    for (possible choice) {
        if (choice is valid) {
            make choice
            backtrack with new state
            undo choice // backtrack
        }
    }
   }
   

Characteristics of Backtracking Problems:

• Recursive in nature
• Decision tree representation – we explore all possible branches
• Often deals with combinations, permutations, and partitions
• Uses pruning or constraints to eliminate bad paths early
• Requires undoing state after the recursive call (i.e., backtracking)

Time Complexity of Backtracking:

Backtracking problems are usually exponential in nature, and their time complexity depends heavily on:

• The number of decisions at each step
• The depth of the decision tree
• Whether you apply pruning (cut off invalid paths early)

Example Complexities:

• Permutations of N elements → O(N!)
• Subset generation → O(2^N)
• N-Queens Problem → O(N!) (with pruning, performs significantly better)

Backtracking is often exponential, but efficient pruning makes many problems solvable in practice.

When to Use Backtracking:

We should consider using backtracking when:

• We're asked to generate all combinations or possible solutions
• We need to explore multiple paths to find the correct one
• Constraints exist that can invalidate certain paths early
• We don’t know the exact path, but can build it step by step

Backtracking is perfect for problems where we incrementally build a solution and abandon paths that don’t lead to a valid result.

Key Takeaways:

• Backtracking is a powerful algorithmic technique used to explore all potential solutions.
• It is recursive and works by making a choice, exploring further, and undoing the choice if it doesn't work out.
• Problems involving combinations, permutations, subsets, or partitions are ideal candidates.
• Pruning invalid paths improves efficiency and avoids unnecessary computation.
• Although often exponential in time complexity, backtracking remains practical for many problems due to intelligent pruning and early exits.
• I’ve already applied backtracking in problems like Letter Combinations, Dice Throw, Palindrome Partitioning, and Permutations — now I understand the underlying logic better.

Mastering backtracking enhances our ability to solve complex problems by breaking them into manageable decision steps.

---

2. Rat in a Maze Problem:

Given an N x N maze represented as a boolean matrix, where:

• true indicates a valid cell (the rat can move there)
• false indicates a blocked cell (wall or obstacle)

The rat starts from the top-left corner (0, 0) and must reach the bottom-right corner (N-1, N-1) by moving in any of the four directions:
U → Up, D → Down, L → Left, R → Right.

The goal is to print all possible paths the rat can take to reach the destination without revisiting any cell in the same path.

Example:

Input: board =
[
[true, true, true],
[true, false, true],
[true, true, true]
]

The rat starts at (0, 0) and wants to reach (2, 2).

Blocked cell at (1, 1) must be avoided.

Valid paths are:

• DDRR → Down → Down → Right → Right
• RRDD → Right → Right → Down → Down

Approach:

This is a classic backtracking problem:

1. Start at the top-left (0, 0) and try all 4 directions.
2. If a move leads to a blocked or already visited cell, backtrack.
3. Mark the current cell as visited before moving.
4. Unmark (backtrack) after exploring all paths from that cell.
5. When we reach the destination cell (N-1, N-1), print the path.

Recursive Tree Visualization:

Given board:

[  [T, T, T],
  [T, F, T],
  [T, T, T]
]

Where:

• T = true (open cell)
• F = false (blocked cell)
• Start = (0, 0)
• End = (2, 2)

Recursive Tree

We denote:

• D = Down
• R = Right
• U = Up
• L = Left

Start: (0,0), path = ""

├── D → (1,0), path = "D"
│   ├── D → (2,0), path = "DD"
│   │   ├── R → (2,1), path = "DDR"
│   │   │   └── R → (2,2), ✅ "DDRR"
│   │   └── (L/U) → blocked or visited
│   └── R → (1,1) ❌ BLOCKED
│
└── R → (0,1), path = "R"
    └── R → (0,2), path = "RR"
        └── D → (1,2), path = "RRD"
            └── D → (2,2), ✅ "RRDD"

Final Valid Paths

• DDRR
• RRDD

All other paths are either blocked (e.g., (1,1)) or lead to revisiting already visited cells.

Code:

public class MazePaths {
    public static void main(String[] args) {
        boolean[][] board = {
            {true, true, true},
            {true, false, true},
            {true, true, true}
        };

        allPaths("", board, 0, 0);
    }

    static void allPaths(String path, boolean[][] maze, int r, int c) {
        if (r == maze.length - 1 && c == maze[0].length - 1) {
            System.out.println(path);
            return;
        }

        // If cell is false (blocked), stop here
        if (!maze[r][c]) {
            return;
        }

        // Mark current cell as visited
        maze[r][c] = false;

        // Explore all four directions
        if (r < maze.length - 1) allPaths(path + 'D', maze, r + 1, c);
        if (c < maze[0].length - 1) allPaths(path + 'R', maze, r, c + 1);
        if (r > 0) allPaths(path + 'U', maze, r - 1, c);
        if (c > 0) allPaths(path + 'L', maze, r, c - 1);

        // Unmark cell during backtracking
        maze[r][c] = true;
    }
}

Key Takeaways:

• This is a perfect example of backtracking with multiple choices at each step.
• The line maze[r][c] = false prevents cycles by marking the current cell as visited.
• After exploring all paths from a cell, we restore its state with maze[r][c] = true — this is the "backtrack" step.
• The function uses DFS (Depth-First Search) combined with backtracking to explore all possible safe paths.
• Handles boundaries and obstacles gracefully by validating moves before proceeding.

---

3. N Queens Problem:

The N-Queens problem is a classic example of a backtracking problem in which the goal is to place N queens on an N×N chessboard so that no two queens threaten each other.

Place N queens on an N×N chessboard such that:

• No two queens share the same row
• No two queens share the same column
• No two queens share the same diagonal

Example (4x4 Board):

We need to place 4 queens on a 4x4 board.
One possible valid solution is:
X Q X X
X X X Q
Q X X X
X X Q X

This means:

• 1st queen is at (0, 1)
• 2nd queen is at (1, 3)
• 3rd queen is at (2, 0)
• 4th queen is at (3, 2)

No two queens are in the same row, column, or diagonal.

There are 2 valid solutions in total for the 4-Queens problem.

Approach:

We solve the N-Queens problem using backtracking:

1. We place queens row by row.
2. For each row, we try every column.
3. Before placing a queen, we check if it’s safe using:
   • Vertical column
   • Upper left diagonal
   • Upper right diagonal
4. If safe, we place the queen and move to the next row.
5. If we reach the last row, we print the board.
6. After exploring one path, we backtrack (remove the queen) and try the next position.

How Do We Check If a Position Is Safe?

Before placing a queen at board[row][col], we must ensure it’s not under attack by any other queen already placed.

Since we're placing queens row-by-row from top to bottom, we only need to check the rows above the current row.

We check 3 directions:

1. Same Column Upwards

• Move from (row - 1, col) upward to (0, col)
• We check if any queen is placed in the same column above the current row.

Direction movement:

(row - 1, col), (row - 2, col), ..., (0, col)

2. Upper Left Diagonal

• Move diagonally up-left from current position (row, col)
• At each step, reduce both row and col by 1

Direction movement:

(row - 1, col - 1), (row - 2, col - 2), ...

3. Upper Right Diagonal

• Move diagonally up-right from current position (row, col)
• At each step, reduce row by 1 and increase col by 1

Direction movement:

(row - 1, col + 1), (row - 2, col + 2), ...

Code:

public class NQueens {
    public static void main(String[] args) {
        int n = 4;
        boolean[][] board = new boolean[n][n];

        int ways = queen(board, 0);
        System.out.println(ways);
    }

    static int queen(boolean[][] board, int row) {
        if (row == board.length) {
            display(board);
            System.out.println();
            return 1;
        }

        int count = 0;

        for (int col = 0; col < board.length; col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = true;
                count += queen(board, row + 1);
                board[row][col] = false; // backtrack
            }
        }

        return count;
    }

    static boolean isSafe(boolean[][] board, int row, int col) {
        // Check same column upwar
        for (int i = 0; i < row; i++) {
            if (board[i][col]) return false;
        }

        // Check upper left diagonal
        for (int i = 1; i <= Math.min(row, col); i++) {
            if (board[row - i][col - i]) return false;
        }

        // Check upper right diagonal
        for (int i = 1; i <= Math.min(row, board.length - col - 1); i++) {
            if (board[row - i][col + i]) return false;
        }

        return true;
    }

    static void display(boolean[][] board) {
        for (boolean[] row : board) {
            for (boolean element : row) {
                System.out.print(element ? "Q" : "X");
            }
            System.out.println();
        }
    }
}

Key Takeaways:

• The N-Queens problem is a perfect showcase of backtracking and constraint satisfaction.
• isSafe() function ensures queens are placed safely without attacking each other.
• We backtrack using board[row][col] = false after exploring each possibility.
• Time complexity is O(N!), but backtracking helps prune many invalid paths early.
• The base case row == board.length means a valid board is formed — print it and return.

---

4. What's next:

I’m continuing this journey and will be:

• Posting blogs every 3 days.

• Also learning Web Development — check out my Web Dev Journey Blog.

• You can follow my journey on X (Twitter) where I post regular updates.

---

5. Conclusion

In this blog of my dsa journey, I went beyond just applying backtracking—I focused on truly understanding how and why it works. From its recursive nature to its decision tree exploration, I learned how backtracking helps solve complex problems step by step by exploring options and undoing choices when needed.

We explored two classic problems:

• Rat in a Maze – explored all valid paths using DFS while avoiding cycles.
• N-Queens – a constraint satisfaction problem, solved efficiently using isSafe() to prune invalid placements.

These problems strengthened my skills in decision-making, recursive traversal, and managing constraints during backtracking.

Backtracking is a powerful problem-solving tool, and this foundational understanding will be essential for tougher DSA challenges ahead.

If you're on a similar learning path, feel free to follow along or reach out — let’s grow together.