N-Queens: Backtracking with Pruning

1. The N-Queens Problem

The problem is stated as follows: Given an integer N, place N chess queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal.

A brute-force approach of trying all possible placements of N queens on N² squares is computationally infeasible. A smarter approach is needed, which begins with a powerful initial observation.

The first and most important form of pruning comes from this constraint: since no two queens can be in the same row, we must place exactly one queen in each row. This insight reduces the problem from choosing N squares out of N² to deciding which column to place a queen in for each row. This transforms the problem into a structure perfect for our backtracking template.

Our recursive function, let's call it backtrack(row), will be responsible for placing a queen in the given row.

2. A Backtracking Strategy with Efficient Pruning

Our strategy follows the template from the previous lesson:

1. Base Case: If we have successfully placed a queen in every row (i.e., row == N), we have found a valid solution. We record the board configuration and return.
2. Choices: For the current row, iterate through all possible columns (col from 0 to N-1).
3. Constraint Check (Pruning): For each column, check if placing a queen at (row, col) is valid. A placement is valid only if the square is not under attack by any previously placed queens.
4. Explore: If the placement is valid:
   • Choose: Place the queen at (row, col) and update our state to reflect this choice.
   • Explore: Call backtrack(row + 1) to solve for the next row.
   • Unchoose: Remove the queen from (row, col) and revert our state. This is the backtracking step that allows us to explore other columns in the current row.

The most critical part of this algorithm is the constraint check. A naive check would involve iterating through all previously placed queens, which would be slow. For an O(1) check, we need a way to instantly know if a column or diagonal is already occupied. Given your familiarity with data structures, you might already be thinking of using hash sets for this.

• Column Check: A hash set (occupied_cols) can store the indices of all columns that contain a queen. Checking if a column c is free is an O(1) lookup.
• Diagonal Check: This is the clever part. We can observe a mathematical property of diagonals on a grid:
  • For any square (r, c) on a positive diagonal (top-left to bottom-right, like /), the value of r + c is constant.
  • For any square (r, c) on a negative diagonal (top-right to bottom-left, like \), the value of r - c is constant.

We can use two more hash sets, pos_diagonals and neg_diagonals, to store these constant values for each occupied diagonal. This allows us to check for diagonal attacks in O(1).

The following resource explains this core optimization strategy in detail.

3. Code Implementation

Now, let's put all these pieces together into a Python implementation. The following video walks through the code, combining the row-by-row strategy with the three-set pruning technique.

Let's summarize the structure of the solution presented in the video:

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        # Sets to store occupied columns and diagonals
        col_set = set()
        pos_diag_set = set() # (r + c)
        neg_diag_set = set() # (r - c)
        
        res = []
        board = [["."] * n for i in range(n)]

        def backtrack(r):
            # Base Case: All queens have been placed
            if r == n:
                # Format the board from a list of lists to a list of strings
                copy = ["".join(row) for row in board]
                res.append(copy)
                return

            # Recursive Step: Try placing a queen in each column of the current row 'r'
            for c in range(n):
                # Constraint Check (Pruning)
                if c in col_set or (r + c) in pos_diag_set or (r - c) in neg_diag_set:
                    continue
                
                # 1. Choose
                col_set.add(c)
                pos_diag_set.add(r + c)
                neg_diag_set.add(r - c)
                board[r][c] = "Q"
                
                # 2. Explore
                backtrack(r + 1)
                
                # 3. Unchoose (Backtrack)
                col_set.remove(c)
                pos_diag_set.remove(r + c)
                neg_diag_set.remove(r - c)
                board[r][c] = "."

        backtrack(0)
        return res

This implementation is a model answer for an interview setting. It's clean, efficient, and demonstrates a deep understanding of both backtracking and how to optimize constraint checks.

4. Complexity Analysis

Finally, let's briefly analyze the algorithm's performance.

• Time Complexity: The search space is roughly bounded by N! (N choices for the first row, N-1 for the second, and so on). For each valid solution found, we take O(N^2) time to copy the board. Therefore, a loose upper bound is O(N! * N^2). While this is a worst-case analysis, the heavy pruning makes the actual runtime much better for typical values of N. Answering O(N!) in an interview is generally sufficient.

• Space Complexity: The primary space is used to store the board, which is O(N^2). The recursion depth is N, so the call stack uses O(N) space. The three sets also use O(N) space each. Thus, the space complexity is dominated by the board, making it O(N^2).

The "Hello Algo" page you reviewed earlier has a good summary of this under its "Code Implementation" section.

Conclusion

In this lesson, you've applied the backtracking template to a more complex constraint satisfaction problem. You've gone beyond simple generation and implemented intelligent pruning to make an intractable problem solvable.

Key Takeaways:

• N-Queens is a classic constraint satisfaction problem solved with backtracking.
• The first level of pruning is to adopt a row-by-row placement strategy, reducing the decision at each step to "which column to choose?"
• The key to an efficient solution is O(1) constraint checking. This is achieved by using hash sets (or boolean arrays) to track occupied columns and diagonals.
• Diagonals can be uniquely identified by the constant values of row + c (positive diagonals) and row - c (negative diagonals).

In our next and final lesson of this module, we'll explore how to optimize recursive algorithms that solve the same subproblem multiple times. We will introduce memoization, a technique that caches the results of expensive function calls, which serves as a perfect bridge from recursion to our next major topic: Dynamic Programming.