🔄 Backtracking in Data Structures & Algorithms

**Backtracking** is an algorithmic technique used for **solving recursive problems** by **exploring all possible solutions** and eliminating the ones that **fail to satisfy the constraints**. It is commonly used in **combinatorial problems, constraint satisfaction, and optimization problems**.

⚙️ How Does Backtracking Work?

Backtracking **explores possible paths recursively** and **abandons a path as soon as it determines that the path cannot lead to a valid solution**.

🔹 Steps of Backtracking Algorithm

1. ✅ Choose a possible **solution candidate**.
2. 🔍 Check if it **satisfies the problem constraints**.
3. 🔁 If valid, **recursively explore** the next step.
4. ❌ If not valid, **backtrack** (remove last choice and try another option).

🛠️ Backtracking Algorithm (Recursive Structure)

                function BACKTRACKING_SOLUTION(problem, solution):
                    if SOLUTION_COMPLETE(solution):
                        return solution
                    for CHOICE in POSSIBLE_CHOICES:
                        if CHOICE_VALID(CHOICE, solution):
                            solution.add(CHOICE)
                            BACKTRACKING_SOLUTION(problem, solution)
                            solution.remove(CHOICE)  // Backtrack if needed
                

📌 Types of Backtracking Problems

🔢 1. Decision Problems

Checking if a solution exists.

📊 2. Optimization Problems

Finding the **best** solution among multiple valid solutions.

🎯 3. Enumeration Problems

Finding **all possible solutions** to a problem.

🔥 Famous Backtracking Problems

🔷 1. N-Queens Problem

The **N-Queens problem** is a classic **constraint satisfaction problem** where we need to place **N queens on an N×N chessboard** such that **no two queens attack each other**.

🛠️ N-Queens Algorithm (C++)

                bool isSafe(int board[][N], int row, int col) {
                    for (int i = 0; i < col; i++)
                        if (board[row][i]) return false;
                    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
                        if (board[i][j]) return false;
                    for (int i = row, j = col; j >= 0 && i < N; i++, j--)
                        if (board[i][j]) return false;
                    return true;
                }
            
                bool solveNQueens(int board[][N], int col) {
                    if (col >= N) return true;
                    for (int i = 0; i < N; i++) {
                        if (isSafe(board, i, col)) {
                            board[i][col] = 1;
                            if (solveNQueens(board, col + 1)) return true;
                            board[i][col] = 0; // Backtrack
                        }
                    }
                    return false;
                }
                

🧩 2. Sudoku Solver

The **Sudoku Solver** uses **backtracking** to fill missing cells while ensuring **no repetition** in rows, columns, and sub-grids.

🛠️ Sudoku Solver Algorithm (C++)

                bool isValid(int board[N][N], int row, int col, int num) {
                    for (int x = 0; x < N; x++)
                        if (board[row][x] == num || board[x][col] == num) return false;
                    int startRow = row - row % 3, startCol = col - col % 3;
                    for (int i = 0; i < 3; i++)
                        for (int j = 0; j < 3; j++)
                            if (board[i + startRow][j + startCol] == num) return false;
                    return true;
                }
            
                bool solveSudoku(int board[N][N]) {
                    for (int row = 0; row < N; row++) {
                        for (int col = 0; col < N; col++) {
                            if (board[row][col] == 0) {
                                for (int num = 1; num <= 9; num++) {
                                    if (isValid(board, row, col, num)) {
                                        board[row][col] = num;
                                        if (solveSudoku(board)) return true;
                                        board[row][col] = 0; // Backtrack
                                    }
                                }
                                return false;
                            }
                        }
                    }
                    return true;
                }
                

🏃‍♂️ 3. Rat in a Maze

The **Rat in a Maze problem** finds a **path from the start to the exit** in a **grid-based maze** using **backtracking**.

🛠️ Algorithm for Rat in a Maze (C++)

                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]) {
                    if (x == N-1 && y == N-1) return true;
                    if (isSafe(maze, x, y)) {
                        sol[x][y] = 1;
                        if (solveMaze(maze, x + 1, y, sol)) return true;
                        if (solveMaze(maze, x, y + 1, sol)) return true;
                        sol[x][y] = 0; // Backtrack
                    }
                    return false;
                }
                

⏳ Time Complexity Analysis of Backtracking

🌍 Real-World Applications of Backtracking

• 🔢 **AI & Machine Learning** - Constraint satisfaction.
• 📂 **Data Security** - Encryption & decryption.
• 🎮 **Game Development** - Pathfinding in **puzzle-solving games**.
• 💡 **Optimization Problems** - Scheduling & resource allocation.

🔗 Next Topics

• 🎯 Dynamic Programming
• 📡 Graph Algorithms