Backtracking

What is Backtracking?

Backtracking is a recursive algorithmic technique for solving problems by exploring all possible options. It systematically builds solutions and abandons (backtracks from) those that fail to meet the problem's constraints, making it ideal for problems that require finding all solutions or the best one.

Key Concepts in Backtracking

1. Recursive Exploration: Problems are solved by exploring decisions step by step.
2. Constraint Checking: At each step, the algorithm checks whether the current state is valid.
3. Backtracking: If the current state is invalid or does not lead to a solution, it undoes the last decision and tries a different one.

Time & Space Complexities

• Time Complexity: Highly problem-dependent; can range from O(k^n) (exponential) for n decisions with k options each, to more optimized solutions using pruning.
• Space Complexity: Depends on the recursion depth, often O(n) for problems with n levels of decisions.

When to Use Backtracking

Backtracking is commonly used for:

• Combinatorial problems (e.g., generating permutations, subsets).
• Solving constraint satisfaction problems (e.g., N-Queens, Sudoku).
• Pathfinding problems (e.g., finding all paths in a maze).
• Optimization problems when brute force can be pruned.

Code Examples

Below is an example of solving the N-Queens problem using backtracking.

def is_safe(board, row, col, n):
    for i in range(row):
        if board[i][col] == "Q":
            return False
        if col - (row - i) >= 0 and board[i][col - (row - i)] == "Q":
            return False
        if col + (row - i) < n and board[i][col + (row - i)] == "Q":
            return False
    return True

def solve(board, row, n, solutions):
    if row == n:
        solutions.append(["".join(row) for row in board])
        return

    for col in range(n):
        if is_safe(board, row, col, n):
            board[row][col] = "Q"
            solve(board, row + 1, n, solutions)
            board[row][col] = "."  # Backtrack

def solve_n_queens(n):
    solutions = []
    board = [["." for _ in range(n)] for _ in range(n)]
    solve(board, 0, n, solutions)
    return solutions

# Example usage
n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    for row in solution:
        print(row)
    print()

Problems to Solve

Important Problems on Backtracking

Backtracking [NeetCode]

Resources

• Backtracking by Aditya Verma