Backtracking Algorithm

Backtracking is a general algorithmic technique that involves exploring all possible solutions for a problem by building a solution incrementally, and removing solutions that fail to satisfy the constraints (i.e., backtracking).

It is used to solve constraint satisfaction problems like puzzles, path-finding, permutations, and N-Queens.

Key Idea:

• Choose → Explore → Un-choose (backtrack)
• It is a form of Depth First Search (DFS)
• Only valid (safe) solutions are explored

How It Works (Steps):

1. Start from an empty solution.
2. At each step, try adding a candidate element.
3. If it violates constraints, backtrack and try another option.
4. If a complete solution is formed, save/return
5. Repeat until all possibilities are explored.

Example: N-Queens (N = 4)

• Place 4 queens on a 4×4 chessboard so that no two queens attack each other (i.e., no same row, column, or diagonal).

Backtracking Code Logic (Generic Template)

def backtrack(state):

    if is_solution(state):

        output(state)

        return

    for choice in choices(state):

        if is_valid(choice, state):

            state.add(choice)

            backtrack(state)

            state.remove(choice)  # <– Backtrack

Backtracking Logic for N-Queens

def solve_n_queens(n):

    board = []

    def is_safe(row, col):

        for r, c in board:

            if c == col or abs(row – r) == abs(col – c):

                return False

        return True

    def backtrack(row):

        if row == n:

            print(board)

            return

        for col in range(n):

            if is_safe(row, col):

                board.append((row, col))

                backtrack(row + 1)

                board.pop()  # Backtrack

    backtrack(0)

Time Complexity:

• For N-Queens: O(N!) (worst case)

Common Problems Solved Using Backtracking:

• N-Queens Problem 👑
• Sudoku Solver 🧩
• Maze Solving 🧭
• Subset/Combination/Permutation Generation
• Graph Colouring 🎨