Part A (2 marks each)

Q1. Define backtracking. A systematic search of the solution space by building partial solutions, abandoning ("backing up") any partial solution that cannot be completed into a valid full solution.

Q2. Give two classical backtracking problems.

1. N-Queens — place $N$ queens so none attacks another.
2. Sudoku — fill empty cells respecting row, column, and box constraints.

Q3. What is the difference between backtracking and brute force? Brute force enumerates every candidate; backtracking explores the same space but prunes branches that violate constraints early — saving exponential work in practice.

---

Part B (20 marks)

Q. Explain backtracking as an algorithm design technique. Discuss its template, illustrate with the N-Queens problem, and relate it to Branch and Bound for optimisation.

Backtracking idea.

Backtracking is a smart brute force. It builds partial solutions by exploring a tree of choices depth-first; whenever a partial solution violates a constraint, the algorithm abandons that subtree and backs up to try a different choice.

Template.

backtrack(partial):
    if complete(partial):
        record(partial); return
    for choice in candidates(partial):
        if feasible(partial + choice):
            backtrack(partial + choice)
            # undo choice if needed

Key ingredients.

1. State — partial solution so far.
2. Choices — candidate extensions.
3. Constraints — must-hold for any complete solution.
4. Pruning — drop infeasible branches early.
5. Goal check — complete solution found.

Example — N-Queens.

Problem: place $N$ queens on an $N \times N$ chessboard so that no two attack each other (no two share row, column, or diagonal).

State. List board[col] = row of the queen in column col.

Choices. For each column, try each row.

Constraints.

• No two queens in the same row.
• No two on the same diagonal.

Pseudo-code.

def attacked(row, col, board):
    for c in range(col):
        r = board[c]
        if r == row or abs(r - row) == abs(c - col):
            return True
    return False

def solve(col=0, board=[None]*N, solutions=[]):
    if col == N:
        solutions.append(board[:]); return
    for row in range(N):
        if not attacked(row, col, board):
            board[col] = row
            solve(col + 1, board, solutions)

Example for $N = 4$. Two solutions exist: [1,3,0,2] and [2,0,3,1]. Without backtracking we would explore $4^4 = 256$ placements; pruning cuts this to a handful.

Pruning strategies.

• Constraint propagation — at each step check constraints.
• Forward checking — eliminate impossible future choices.
• MRV (Minimum Remaining Values) — assign the most-constrained variable next.
• Memoisation — cache visited states.

Branch and Bound.

For optimisation problems, backtracking is extended with a cost bound:

• Keep best-so-far solution cost.
• Down each branch, compute a lower bound on the achievable cost.
• If the lower bound is worse than the current best, prune the branch.

Used for:

• 0/1 Knapsack — lower bound = current value + fractional knapsack of remaining.
• Travelling Salesman Problem (TSP) — lower bound via MST or assignment relaxation.
• Integer Linear Programming (ILP) — solve LP relaxation as bound.

Comparison with other paradigms.

Paradigm	Use when
Brute force	Small $n$, no structure
Greedy	Locally best = globally best
DP	Overlapping sub-problems
Backtracking	State-space search with feasibility constraints; no overlap
Branch & Bound	Backtracking + cost bounds for optimisation

Complexity. Worst-case still exponential ($O(b^d)$ where $b$ = branching factor, $d$ = depth) — but pruning often makes real-world instances tractable.

Applications.

• Constraint Satisfaction Problems (CSP) — timetables, sudoku.
• SAT solvers — DPLL is backtracking with unit propagation.
• Game-tree search — minimax + α-β pruning is backtracking with cost bound (used in chess, Go).
• AI planning — STRIPS-style planners.
• Hyperparameter trees in AutoML.

Take-away. Backtracking + pruning is one of the most general algorithmic paradigms — used wherever a problem requires searching a combinatorial space with constraints. Branch and Bound extends it to optimisation by adding cost-based pruning.