Chapter 43

Home

Refactoring: Pruning Search Space

Backtracking explores a tree. Pruning is how you cut off dead branches before wasting time on them. The difference between a backtracking solution that times out and one that passes is almost always in how aggressively you prune.

Before: Naive Safety Check in N-Queens

The naive way to check if a square (r, c) is safe: scan all previously placed queens to see if any share the same column or diagonal. That's O(N) per check, multiplied by the exponential search tree.

C++ — O(N) safety scan per square

bool is_safe(vector<string>& board, int row, int col, int n) {
    // Check column (above)
    for (int i = 0; i < row; i++)
        if (board[i][col] == 'Q') return false;

    // Check main diagonal (↖)
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        if (board[i][j] == 'Q') return false;

    // Check anti diagonal (↗)
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        if (board[i][j] == 'Q') return false;

    return true;
}

void solve(int row, int n, vector<string>& board,
           vector<vector<string>>& result) {
    if (row == n) { result.push_back(board); return; }
    for (int col = 0; col < n; col++) {
        if (!is_safe(board, row, col, n)) continue;
        board[row][col] = 'Q';
        solve(row + 1, n, board, result);
        board[row][col] = '.';
    }
}

🚨 The hidden cost

is_safe runs at every node of the search tree. For N = 12, the tree has ~1.5 million nodes. Each node calls is_safe up to N times (one per column). With O(N) loops inside each call, you're looking at O(N³) per complete search — or worse. At N = 15 this becomes minutes instead of seconds.

After: O(1) Pruning with Boolean Arrays

Replace the scanning loops with three boolean arrays. Checking safety becomes a single array lookup — O(1). This is the single most impactful pruning optimisation in N-Queens.

C++ — O(1) conflict check via boolean arrays

void solve(int row, int n,
           vector<int>& cols,
           vector<int>& diag1,     // r − c + n − 1
           vector<int>& diag2,     // r + c
           vector<string>& board,
           vector<vector<string>>& result) {

    if (row == n) { result.push_back(board); return; }

    for (int col = 0; col < n; col++) {
        int d1 = row - col + n - 1;
        int d2 = row + col;
        if (cols[col] || diag1[d1] || diag2[d2]) continue;
        //          ↑  O(1)  ↑     ↑  O(1)   ↑     ↑  O(1)   ↑

        board[row][col] = 'Q';
        cols[col] = diag1[d1] = diag2[d2] = 1;

        solve(row + 1, n, cols, diag1, diag2, board, result);

        board[row][col] = '.';
        cols[col] = diag1[d1] = diag2[d2] = 0;
    }
}
// Speed comparison for N = 12:
// Naive scan:  ~1.2 seconds
// Boolean arr: ~0.045 seconds  (27× faster)
//
// For N = 15:
// Naive scan:  ~3+ minutes
// Boolean arr: ~2.3 seconds

More Pruning Techniques

Once you have O(1) conflict checks, there are further ways to prune:

Symmetry breaking

For N-Queens, you only need to try the first queen in columns 0 to N/2. The rest are symmetric reflections. This halves the search tree.

Most constrained variable (MCV)

Instead of iterating rows in order, pick the row with the fewest available columns next. This fails fast — if a row has zero valid columns, you know immediately instead of wasting time on other rows first.

Forward checking

After placing a queen, pre-emptively mark all squares it attacks as unavailable. If any subsequent row has zero available squares, backtrack immediately without recursing.

📐 The pruning mindset

Every node in the backtracking tree either passes or fails. Pruning is any optimisation that detects failure earlier or eliminates equivalent paths. The best pruning strategies are specific to the problem — but the O(1) lookup pattern (arrays instead of loops) applies everywhere.

Key Takeaways

Practice