CodeBlanks Logo Icon CodeBlanks
Login Register

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.

Practice 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)).

Starter code

solution.py
def count_n_queens(n):
    # Count queens

Sample solution

solution.py
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))

Expected output

2

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Pruning: match the terms

Term Meaning
prune Prune
early check Early check
branch Branch
feasible Feasible

2 When is pruning done?

  • At the start
  • Before a step Correct answer
  • At the result
  • After a step

Explanation: Before a step.

3 Pruning condition

Question 
if not ____:
Answer 
if not feasible:

Explanation: feasible is right.

All lessons in Intermediate

1 Merge sort

  1. Divide and conquer
  2. Merge operation
  3. Full merge sort
  4. Summary - Merge sort

2 Quick sort

  1. Pivot selection
  2. Partitioning
  3. Recursive quick sort
  4. Summary - Quick sort

3 Heap sort

  1. What is a heap?
  2. Heapify
  3. Build heap and sort
  4. Summary - Heap sort

4 Counting sort

  1. Counting idea
  2. Count array
  3. Output array
  4. Summary - Counting sort

5 Radix sort

  1. Radix idea
  2. Digit pass
  3. Stable sub-sort
  4. Summary - Radix sort

6 Sorting project

  1. Project: Overview
  2. Score array
  3. Apply merge sort
  4. Print statistics

7 Tree

  1. What is a tree?
  2. Node and edge
  3. Binary tree
  4. Summary - Trees

8 Binary search tree

  1. BST rule
  2. BST insert
  3. BST search
  4. Summary - BST

9 AVL tree

  1. Balanced tree
  2. Rotation
  3. Balance after insert
  4. Summary - AVL tree

10 Heap

  1. Min and max heap
  2. Insert
  3. Extract
  4. Summary - Heap

11 Priority queue

  1. What is a priority queue?
  2. Heap-based implementation
  3. Push and pop
  4. Summary - Priority queue

12 Data structures project

  1. Project: Overview
  2. Undo stack
  3. Pending queue
  4. Print the state

13 Graph basics

  1. What is a graph?
  2. Adjacency list
  3. Adjacency matrix
  4. Summary - Graph

14 Breadth-first search

  1. BFS idea
  2. Using a queue
  3. Marking visited
  4. Summary - BFS

15 Depth-first search

  1. DFS idea
  2. Stack or recursion
  3. Backtracking
  4. Summary - DFS

16 Greedy algorithms

  1. Greedy approach
  2. Coin change
  3. Greedy limits
  4. Summary - Greedy

17 Divide and conquer

  1. Three steps
  2. Recursive structure
  3. Master theorem
  4. Summary - Divide and conquer

18 Backtracking

  1. What is backtracking?
  2. State tree
  3. Pruning
  4. Summary - Backtracking

19 Graph project

  1. Project: Overview
  2. City graph
  3. BFS for reachability
  4. Print the result

20 Intermediate final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4