Solving N-Queens with Backtracking

1. Understanding the N-Queens Problem

First, let's formally define the problem and its constraints. A queen in chess can attack any piece in the same row, column, or either of the two diagonals. The N-Queens problem asks us to place N queens on an N×N board so that none of them are under attack.

To get a clear picture of the problem, let's start with a short video.

A brute-force approach might be to try every possible placement of N queens among the $N^2$ squares. The number of combinations would be $\left(\genfrac{}{}{0ex}{}{N^2}{N}\right)$, which is astronomically large even for a standard 8x8 board. We need a much smarter strategy.

2. Structuring the Problem for Backtracking

As we learned in the last lesson, the key to applying backtracking is to frame the problem in terms of choices that build a solution incrementally. A critical first step is to simplify the search space. We know that any valid solution must have exactly one queen per row. This observation allows us to drastically reduce our choices.

Instead of deciding where to place each of the N queens on the whole board, we can simply decide which column to place a queen in for each row, one row at a time.

This gives us the three components for our backtracking algorithm:

• Choice: For the current row, which column (from 0 to N-1) should we place a queen in?
• Constraints: The chosen column must not be attacked by any queen in a previous row. This means it cannot be in the same column or on the same diagonal as any previously placed queen.
• Goal: We have successfully placed a queen in all N rows.

Let's watch a segment that visualizes this row-by-row placement and backtracking process.

This sequence of choices naturally forms the state-space tree we discussed. The root is the empty board. The nodes at depth k represent partial solutions with k queens placed in the first k rows. When we find that we cannot place a queen in the current row without violating a constraint, we backtrack.

This image shows the state-space tree for the 4-Queens problem. It's a perfect illustration of how our algorithm will explore and prune the search space.

3. The Backtracking Algorithm and the "isSafe" Check

With the problem structured, we can now outline the recursive algorithm. The core pattern is "choose, explore, unchoose".

1. Base Case: If we need to place a queen in a row beyond the board (e.g., row == N), it means we've successfully placed all N queens. We've found a valid solution.
2. Recursive Step: For the current row:
   • Loop through each column from 0 to N-1.
   • Check Constraint: If placing a queen at (row, column) is safe.
   • If it is safe:
     • Choose: Place the queen on the board at (row, column).
     • Explore: Recursively call the function to solve for the next row (row + 1).
     • Unchoose: Remove the queen from (row, column). This is the crucial backtracking step. It restores the state so we can explore placing the queen in the next column of the current row.

The following resource provides a detailed explanation of this recursive logic and the importance of the backtracking step.

The effectiveness of this algorithm hinges on the isSafe() check, which implements our pruning.

Naive isSafe() Check: O(N)

The most straightforward way to implement isSafe(row, col) is to check the three potential attack vectors from previously placed queens (i.e., in rows 0 to row-1):

1. Check the column col upwards.
2. Check the upper-left diagonal.
3. Check the upper-right diagonal.

This requires a loop that runs up to row times, making the check an O(N) operation.

Optimized isSafe() Check: O(1)

We can do much better. By observing the properties of the board's grid, we can perform the safety check in constant time, O(1). This is a significant optimization.

• Columns: We can use a boolean array or a hash set, say occupied_cols, to track which columns are already in use. Checking if a column is taken is then an O(1) lookup.
• Diagonals:
  • For any anti-diagonal (top-left to bottom-right), the value of row - col is constant.
  • For any main diagonal (top-right to bottom-left), the value of row + col is constant.

We can use two more hash sets or boolean arrays (occupied_main_diag and occupied_anti_diag) to track which diagonals are attacked. When we want to check isSafe(row, col), we just look up col, row - col, and row + col in our three tracking structures. All three lookups are O(1).

The Design Gurus article you just looked at explains this trick. Please reread that section, this time focusing on how the sets (cols, main_diag, anti_diag) are used for an O(1) check. The GeeksforGeeks article N Queen Problem also provides an excellent explanation under the section "Optimized Approach".

When you implement the recursive step, you'll perform these actions:

• Choose: Mark col, row-col, and row+col as occupied.
• Explore: Recurse.
• Unchoose: Unmark col, row-col, and row+col.

4. Advanced Optimization: Bitmasking

For someone with your software engineering background, it's worth knowing about an even more advanced optimization. The sets or boolean arrays for tracking occupied columns and diagonals can be replaced with integers, where each bit acts as a flag. This is called bitmasking.

Instead of array lookups, you perform fast bitwise operations (|, &, ~, <<, >>) to check for safety and update the board state. This doesn't change the overall O(N!) time complexity, but it significantly reduces the constant factors, making the algorithm much faster in practice.

Conclusion

In this lesson, we deconstructed the N-Queens problem and built a backtracking solution from the ground up. We saw how a simple observation—one queen per row—dramatically simplifies the problem and defines the choices for our state-space search.

Key Takeaways:

• The N-Queens problem is a classic example of a constraint satisfaction problem perfectly suited for backtracking.
• The state-space tree is built by making a choice at each row: which column to place the queen in.
• The core of the algorithm is a recursive function that follows the "choose, explore, unchoose" pattern.
• The efficiency of the solution heavily depends on the isSafe() check. We can optimize this from a naive O(N) loop to an O(1) lookup using arrays or sets to track attacked columns and diagonals.
• For ultimate performance, bitmasking can be used to perform these O(1) checks with highly efficient bitwise operations.

Preview of the Next Lesson:

Now that you've seen backtracking applied to a board-based problem, we'll look at another common application area in the next lesson: combinatorial search problems. We will apply the same fundamental backtracking pattern to solve a Sudoku puzzle, where the constraints are different but the underlying "choose, explore, unchoose" methodology remains the same.