N-Queens Problem — The Classic Backtracking Challenge

In 1848, German chess master Max Bezzel posed a seemingly simple puzzle: Can you place eight queens on a standard 8×8 chessboard such that no two queens threaten each other? What appeared to be a recreational chess problem would become one of the most studied problems in computer science—a perfect crystallization of systematic search, constraint satisfaction, and the elegant power of backtracking.

The N-Queens problem (generalizing to any N×N board) stands as the canonical example of backtracking algorithms. It's the problem that textbooks reach for first, that interviewers ask to test recursive thinking, and that researchers use to benchmark constraint solvers. Understanding N-Queens deeply means understanding backtracking itself.

Before diving into algorithms, we must precisely understand what we're solving. Ambiguity in problem formulation leads to incorrect solutions, so let's establish crystal-clear definitions.

Understanding Queen Movement:

A queen combines the power of a rook (horizontal and vertical movement) and a bishop (diagonal movement). From any position, a queen can move:

1. Horizontally — Along its entire row
2. Vertically — Along its entire column
3. Diagonally — Along both diagonals passing through its position

This means if we place a queen at position (r, c), every other queen must avoid:

• All positions (r, x) for any column x (same row)
• All positions (x, c) for any row x (same column)
• All positions where |row - r| = |col - c| (same diagonal)

Key Insight for Diagonal Detection:

Diagonals have a beautiful mathematical property that makes checking trivial:

• Main diagonal direction (↘): All cells satisfy row - col = constant
• Anti-diagonal direction (↗): All cells satisfy row + col = constant

For example, on an 8×8 board:

• Cells (0,0), (1,1), (2,2), (3,3)... all have row - col = 0 (same main diagonal)
• Cells (0,3), (1,2), (2,1), (3,0) all have row + col = 3 (same anti-diagonal)

This mathematical property will be crucial for efficient constraint checking.

You might wonder: why does a chess puzzle command so much attention in computer science? The answer lies in what N-Queens represents, not merely what it solves.

Historical Significance:

The 8-Queens problem was first posed in 1848 and has attracted contributions from legendary mathematicians including Carl Friedrich Gauss, who worked on it in 1850. The problem has been solved using methods ranging from brute force to genetic algorithms, from constraint propagation to neural networks.

In 1874, S. Günther proved that solutions exist for all N ≥ 4 (N=2 and N=3 have no solutions). The exact formula for counting solutions remains unknown, making it computationally interesting even today.

To appreciate why backtracking is necessary, we must understand the search space—the set of all possible configurations we might consider.

Naive Approach: Brute Force Over All Placements

The most naive approach considers every possible way to place N queens on N² squares:

• Choose N positions from N² squares
• Number of combinations: C(N², N) = N²! / (N! × (N²-N)!)

For an 8×8 board: C(64, 8) = 4,426,165,368 (over 4 billion configurations!)

Even at a million checks per second, this would take over an hour just for N=8. Clearly, brute force is not viable.

First Optimization: One Queen Per Row

Here's a critical insight: since no two queens can share a row, each row must contain exactly one queen. This transforms the problem:

• Instead of choosing 8 positions from 64 squares, we choose one column for each row
• Number of configurations: N^N

For N=8: 8^8 = 16,777,216 (about 17 million)

This is already 250× better than brute force! But we can do even better.

Second Optimization: One Queen Per Column Too

Similarly, each column must contain exactly one queen. This means a valid placement is really a permutation: column assignments such that each column appears exactly once.

• Number of configurations: N!

For N=8: 8! = 40,320

This is another 400× improvement! We've reduced 4 billion to 40 thousand just by recognizing structure.

N-Queens exhibits all the properties that make a problem ideal for backtracking. Let's examine each one:

The Backtracking Mental Model:

Think of backtracking as exploring a decision tree:

1. Root: Empty board, no queens placed
2. Level 1: All possible placements for queen in row 0 (N choices)
3. Level 2: For each Level 1 choice, all valid placements for queen in row 1
4. Level k: All valid placements for queen in row k-1, given previous choices
5. Leaves: Either complete solutions (N queens placed) or dead ends (no valid column for next queen)

Backtracking traverses this tree depth-first, pruning branches the moment a constraint violation is detected. This pruning is what makes it efficient.

Key Observation:

In the tree above (for 4-Queens), notice how entire subtrees are pruned when we detect a conflict. The branch starting with Q at (0,0) → Q at (1,2) leads nowhere because row 2 has no valid column. We don't explore any of those grandchildren—we immediately backtrack.

This pruning is what takes us from 40,320 permutations (8!) down to roughly 2,000 nodes visited for solving 8-Queens. That's a 95% reduction in explored configurations!

Let's solve the smallest non-trivial case by hand to internalize the backtracking process. We'll place queens row by row, tracking columns and diagonals carefully.

The N-Queens problem comes in several flavors, each with different algorithmic implications:

Interview Tip:

Interviewers often start with 'find one solution' to test basic backtracking, then ask 'find all solutions' as a follow-up. The key difference is what happens after finding a valid placement: do you return immediately or continue searching?

Understanding both variants and their tradeoffs demonstrates mastery of the problem.

We'll analyze complexity in detail later, but here's a preview of what to expect:

Time Complexity:

• Theoretical worst case: O(N!) — we might try all permutations
• Practical performance: Much better due to pruning. For 8-Queens, we visit ~2000 nodes instead of 40,320
• Finding one solution: Often O(N) for large N (heuristics can find solutions very quickly)
• Finding all solutions: Must explore entire search tree; grows super-exponentially with N

Space Complexity:

• Recursion depth: O(N) — one level per row
• Board representation: O(N) if storing column positions, O(N²) if storing full board
• Constraint tracking: O(N) for optimized approach using hash sets
• Storing all solutions: O(S × N) where S is the number of solutions

We've established the foundation for understanding N-Queens as the canonical backtracking problem:

What's Next:

With the problem clearly defined, we'll now dive into the mechanics of queen placement. The next page covers how to systematically build valid placements, handle state management, and implement the core backtracking loop.