Pruning

Cut dead branches early to save time.

Pruning

Pruning cuts infeasible branches early, reducing returns. It speeds up backtracking.

Good pruning can turn an exponential algorithm polynomial-like; this is why it matters.

Pruning shrinks the search space and makes a big difference in practice; especially for N-queens.

Early check

Pruning is a check before taking a step. If infeasible the branch is never expanded.

In N-queens, same-column or diagonal checks are examples; a queen placement is rejected early.

Early checks prevent needless recursive calls and save time.

Exercise Count N-queens

Write count_n_queens(n). Count placements of n non-attacking queens on an n×n board with backtracking. Print 2 with print(count_n_queens(4)).

Show example solution

def count_n_queens(n):
    # Count queens
    def safe(cols, row, col):
        for r in range(row):
            c = cols[r]
            if c == col or abs(c - col) == row - r:
                return False
        return True
    count = 0
    def backtrack(row, cols):
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            if safe(cols, row, col):
                cols[row] = col
                backtrack(row + 1, cols)
    backtrack(0, [0] * n)
    return count
print(count_n_queens(4))

Test yourself

Pruning: match the terms

prune

Prune
early check

Early check
branch

Branch
feasible

Feasible
When is pruning done?
- At the start
- Before a step
- At the result
- After a step
Show answer

Before a step — Before a step.
Pruning condition
```
if not ____:
```
Show answer
```
if not feasible:
```

Next lesson: Summary - Backtracking

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies