Data Structures and Algorithms in C (DSA)

📘 Chapter: Backtracking (N-Queens, Sudoku Solver)

So far, we've explored algorithms that try to find optimal solutions (Greedy, Dynamic Programming) or traverse graphs efficiently. Now, we turn to Backtracking, a general algorithmic technique for solving problems that involve searching for a solution among a set of choices. It's particularly effective for **constraint satisfaction problems** where you need to find all (or some) solutions that satisfy certain conditions. Think of it as systematically trying to build a solution incrementally, and whenever a choice leads to a dead end (violates constraints), you "backtrack" to undo that choice and try a different one.

💡 Core Concepts of Backtracking

• State-Space Tree: Backtracking implicitly explores a "state-space tree" or "search tree." Each node in this tree represents a partial solution, and edges represent choices that extend the partial solution. The goal is to find paths from the root to leaf nodes that represent complete, valid solutions.
• Partial Solution: At any point during the algorithm, we have made a series of choices, resulting in a partial solution.
• Constraints: These are the rules that a valid solution must satisfy. Backtracking uses these constraints to prune the search space early. If a partial solution violates a constraint, we immediately stop exploring that path (pruning).
• Feasibility Check: A crucial function that determines if adding a new choice to the current partial solution is still valid (i.e., doesn't violate any constraints).
• Base Case/Goal: The condition under which a complete, valid solution has been found. When this is met, the solution is typically recorded.
• Recursion: Backtracking is almost always implemented recursively, as it naturally fits the depth-first exploration of the state-space tree.
• "Backtrack" (Undo Choice): This is the defining characteristic. After exploring all possibilities from a given choice, or if a choice leads to a dead end, the algorithm "undoes" that choice to restore the previous state. This allows it to explore alternative paths.

General Backtracking Template:

function solve(current_level, current_state):
    // Base Case: If a complete solution is found
    if current_level has reached the goal (e.g., all decisions made):
        if current_state is valid:
            Add current_state to results
        return

    // Recursive Step: Try all possible choices for the current level
    for each choice in possible_choices_for_current_level:
        // Pruning/Feasibility Check: Is this choice valid with current_state?
        if isValid(current_state, choice):
            // Make the choice (add to current_state)
            apply(choice, current_state)

            // Recurse to the next level
            solve(current_level + 1, current_state)

            // BACKTRACK: Unmake the choice (undo changes to current_state)
            undo(choice, current_state)
  

👑 1. N-Queens Problem

A classic problem to illustrate backtracking.

Problem Statement:

Place $N$ non-attacking queens on an $N \times N$ chessboard such that no two queens threaten each other. This means no two queens can be in the same row, same column, or same diagonal.

Backtracking Approach:

We can try to place one queen per column, starting from the first column. For each column, we iterate through rows to find a safe position.

1. Start with an empty $N \times N$ board.
2. Define a recursive function, say `solveNQueens(col)`, which attempts to place a queen in the given `col`.
3. Base Case: If `col == N`, all $N$ queens have been successfully placed. Record this configuration as a valid solution.
4. Recursive Step: For the current `col`:
   • Iterate through each `row` from 0 to $N-1$:
   • Check if placing a queen at `(row, col)` is `isSafe()` (i.e., it doesn't conflict with any queens already placed in previous columns).
   • If `isSafe(row, col)` is true:
     • Place a queen at `(row, col)` (mark this cell as occupied by a queen).
     • Recursively call `solveNQueens(col + 1)` to place the next queen.
     • After the recursive call returns (whether it found a solution or not), **BACKTRACK**: remove the queen from `(row, col)` (mark cell as empty). This is crucial to explore other possibilities for the current `col`.

`isSafe` function:

To check if `(row, col)` is safe, you need to verify:

• No other queen in the same `row`.
• No other queen in the same `column` (already guaranteed by placing one queen per column).
• No other queen in the same primary diagonal (where `row + col` is constant).
• No other queen in the same secondary diagonal (where `row - col` is constant).

// Conceptual C++ for N-Queens Problem
// Using boolean arrays for faster lookups for safety check
vector<vector<string>> solutions;
vector<string> board;
int N;

vector<bool> row_occupied;
vector<bool> diag1_occupied; // row + col
vector<bool> diag2_occupied; // row - col + (N-1) to make index non-negative

void solveNQueens_util(int col) {
    if (col == N) {
        solutions.push_back(board);
        return;
    }

    for (int row = 0; row < N; ++row) {
        // Check if current position (row, col) is safe
        if (!row_occupied[row] &&
            !diag1_occupied[row + col] &&
            !diag2_occupied[row - col + (N - 1)]) {

            // Place queen
            board[row][col] = 'Q';
            row_occupied[row] = true;
            diag1_occupied[row + col] = true;
            diag2_occupied[row - col + (N - 1)] = true;

            // Recurse for next column
            solveNQueens_util(col + 1);

            // BACKTRACK: Remove queen
            board[row][col] = '.';
            row_occupied[row] = false;
            diag1_occupied[row + col] = false;
            diag2_occupied[row - col + (N - 1)] = false;
        }
    }
}

vector<vector<string>> solveNQueens(int n_val) {
    N = n_val;
    board.assign(N, string(N, '.'));
    row_occupied.assign(N, false);
    diag1_occupied.assign(2 * N - 1, false);
    diag2_occupied.assign(2 * N - 1, false);

    solveNQueens_util(0); // Start from column 0
    return solutions;
}
  

Time Complexity: The worst-case time complexity is roughly $O(N!)$ because, in the worst case, we might explore permutations of N queens. However, due to pruning, it's significantly faster than $N^N$. For N=8, it's quite fast.
Space Complexity: $O(N^2)$ for the board and $O(N)$ for the recursion stack and helper boolean arrays.

🧩 2. Sudoku Solver

Another excellent example of backtracking for constraint satisfaction.

Problem Statement:

Given a partially filled $9 \times 9$ Sudoku grid, fill the empty cells such that each column, each row, and each of the nine $3 \times 3$ subgrids (boxes) contains all of the digits from 1 to 9 exactly once.

Backtracking Approach:

We iterate through the grid, and whenever we find an empty cell, we try placing digits from 1 to 9.

1. Define a recursive function, say `solveSudoku(board)`. This function will try to find an empty cell.
2. Base Case: If no empty cells are found, the Sudoku is solved, return `true`.
3. Recursive Step: Find the next empty cell `(row, col)`.
   • For each digit `num` from 1 to 9:
   • Check if placing `num` at `(row, col)` is `isValid()` according to Sudoku rules.
   • If `isValid(row, col, num)` is true:
     • Place `num` at `(row, col)`.
     • Recursively call `solveSudoku(board)`.
     • If the recursive call returns `true` (meaning a solution was found down that path), then propagate `true` upwards.
     • Else (if the recursive call returned `false`, meaning this `num` didn't lead to a solution), **BACKTRACK**: remove `num` from `(row, col)` (set it back to empty).
4. If all digits 1-9 have been tried for the current cell `(row, col)` and none led to a solution, return `false`.

`isValid` function:

To check if `num` is valid at `(row, col)`, verify:

• `num` is not present in the current `row`.
• `num` is not present in the current `col`.
• `num` is not present in the $3 \times 3$ box containing `(row, col)`.

// Conceptual C++ for Sudoku Solver
bool is_valid(const vector<vector<char>>& board, int row, int col, char num) {
    // Check row
    for (int x = 0; x < 9; ++x) {
        if (board[row][x] == num) return false;
    }
    // Check column
    for (int x = 0; x < 9; ++x) {
        if (board[x][col] == num) return false;
    }
    // Check 3x3 box
    int startRow = row - row % 3;
    int 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_util(vector<vector<char>>& board) {
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            if (board[row][col] == '.') { // Found an empty cell
                for (char num = '1'; num <= '9'; ++num) {
                    if (is_valid(board, row, col, num)) {
                        board[row][col] = num; // Place the number
                        if (solveSudoku_util(board)) { // Recurse
                            return true; // Solution found!
                        } else {
                            board[row][col] = '.'; // BACKTRACK: Undo the choice
                        }
                    }
                }
                return false; // No number from 1-9 works for this cell
            }
        }
    }
    return true; // All cells filled, Sudoku solved
}

void solveSudoku(vector<vector<char>>& board) {
    solveSudoku_util(board);
}
  

Time Complexity: Exponential in the worst case, roughly $O(9^{N^2})$ where $N$ is the side length of the grid. However, pruning significantly reduces the actual time for valid Sudoku puzzles.
Space Complexity: $O(N^2)$ for the board and $O(N^2)$ for the recursion stack (depth can be up to the number of empty cells).

📌 Real-Life Example (UdaanPath)

Backtracking is invaluable for problems requiring exhaustive search with constraints:

• Configuration Generation: If UdaanPath had complex user profile configurations or course module arrangements with interdependencies, and certain combinations were forbidden, backtracking could be used to generate all valid configurations.
• Resource Allocation with Constraints: Imagine assigning specific lab equipment or special teaching slots to courses, where each assignment has specific requirements (e.g., equipment must be free, slot must fit the instructor's availability). Backtracking could find valid allocation schemes.
• Solving Puzzles/Games: Beyond Sudoku, many logic puzzles or board games (e.g., pathfinding in certain maze-like games) can be modeled and solved using backtracking, as it naturally explores valid moves.
• Combinatorial Optimization (though DP/Greedy are often preferred if applicable): While often less efficient than DP or Greedy for optimization, for small problem sizes or when all solutions are needed, backtracking can find combinations that satisfy complex criteria. Examples include subsets with a given sum, permutations.
• AI in Game Playing: Simple AI agents for games (like chess or checkers) might use a form of backtracking (often combined with minimax) to explore possible moves and counter-moves to find the optimal strategy.

✅ Summary: Smart Exhaustion

• Backtracking is a recursive algorithmic technique for finding solutions by incrementally building a candidate solution and abandoning (backtracking) it when it determines that the candidate cannot possibly be completed into a valid solution.
• It explores a state-space tree, performing feasibility checks and pruning branches that violate constraints.
• Key step: "unmake choice" (backtrack) to explore alternative paths.
• Common applications include:
  • N-Queens Problem: Placing $N$ non-attacking queens on a chessboard.
  • Sudoku Solver: Filling a grid according to rules.
  • Combinatorial problems like permutations, combinations, subset sum.
• Time complexity is often exponential in the worst case but greatly optimized by pruning.

📤 Coming Next: Dynamic Programming (Intro, Memoization, Tabulation)

We've seen how greedy algorithms make local choices and how backtracking exhaustively searches. Our journey continues to another cornerstone of algorithm design: Dynamic Programming. This powerful technique solves complex problems by breaking them down into simpler, overlapping subproblems and storing the results of these subproblems to avoid redundant computations. We'll dive into its core principles, including **Memoization** (top-down) and **Tabulation** (bottom-up).