How to Solve: N-Queens Problem – Complete Guide for FAANG Interviews

How to Solve: N-Queens Problem – Complete Guide for FAANG Interviews

? Introduction

"The N-Queens problem isn’t just a chess puzzle—it’s a litmus test for backtracking mastery. FAANG interviewers use it to assess recursion depth, pruning efficiency, and your ability to optimize brute-force solutions. Nail this, and you prove you can handle combinatorial problems under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling N-Queens, ensure you understand: 1. Backtracking (DFS with pruning) – How to explore all possibilities while discarding invalid paths early. 2. Hash Sets / Arrays for Tracking State – Efficiently checking constraints (e.g., column, diagonal conflicts). 3. Recursion & Base Cases – How to structure recursive calls and termination conditions.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeat this checklist for every N-Queens problem:

1. Understand the Problem
2. Confirm: Place N queens on an N x N board so no two queens attack each other.

3. Output: All valid configurations (or count, if follow-up).

4. Choose a Representation

5. Option 1: 2D array (easiest to visualize).
6. Option 2: 1D array queens[row] = col (more efficient).

7. Option 3: Bitmask (fastest for large N).

8. Define Constraints

9. No two queens share the same column.

10. No two queens share the same diagonal (row1 - col1 == row2 - col2 or row1 + col1 == row2 + col2).

11. Backtracking Setup

12. Start with row = 0.
13. For each row, try placing a queen in every column.

14. If a placement is valid, recurse to the next row.

15. Prune Invalid Paths Early

16. Before placing a queen at (row, col), check:

    • Is col already occupied?
    • Are diagonals row-col or row+col occupied?

17. Base Case

18. If row == N, add the current configuration to the result.

19. Optimize (Optional)

20. Use bitmasking for O(1) conflict checks.

21. Skip symmetric configurations (e.g., only generate solutions where the first queen is in the left half).

22. Edge Cases

23. N = 1 → Trivial (1 solution).
24. N = 2 or 3 → No solutions.
25. N >= 4 → Valid solutions exist.

? WORKED EXAMPLES

Example 1 – Basic (N=4)

Problem: Return all distinct solutions for N=4.

Thought Process

1. Use a 1D array queens where queens[row] = col.
2. Track occupied columns and diagonals with sets.
3. Backtrack row-by-row.

Python Code

def solveNQueens(n):

    def backtrack(row, cols, diag1, diag2, path, res):

        if row == n:

            res.append(path)

            return

        for col in range(n):

            curr_diag1 = row - col

            curr_diag2 = row + col

            if col not in cols and curr_diag1 not in diag1 and curr_diag2 not in diag2:

                backtrack(

                    row + 1,

                    cols | {col},

                    diag1 | {curr_diag1},

                    diag2 | {curr_diag2},

                    path + [col],

                    res

                )


    res = []

    backtrack(0, set(), set(), set(), [], res)


    # Convert to board format

    boards = []

    for sol in res:

        board = []

        for col in sol:

            board.append("."  col + "Q" + "."  (n - col - 1))

        boards.append(board)

    return boards

Time & Space Complexity

• Time: O(N!) (pruning reduces this, but worst case is factorial).
• Space: O(N) (recursion depth + sets).

Why This Works

• Backtracking explores all valid queen placements.
• Constraint Propagation (sets for columns/diagonals) prunes invalid paths early.

Example 2 – Medium (Count Solutions)

Problem: Return the number of distinct solutions for N=8.

Twist

• Instead of storing all solutions, just count them.

Optimization

• Use bitmasking for O(1) conflict checks.

Python Code

def totalNQueens(n):

    def backtrack(row, cols, diag1, diag2):

        if row == n:

            return 1

        count = 0

        for col in range(n):

            curr_diag1 = row - col

            curr_diag2 = row + col

            if (cols & (1 << col)) or (diag1 & (1 << curr_diag1)) or (diag2 & (1 << curr_diag2)):

                continue

            count += backtrack(

                row + 1,

                cols | (1 << col),

                diag1 | (1 << curr_diag1),

                diag2 | (1 << curr_diag2)

            )

        return count


    return backtrack(0, 0, 0, 0)

Time & Space Complexity

• Time: O(N!) (but much faster due to bitmasking).
• Space: O(N) (recursion stack).

Why This Works

• Bitmasking replaces sets with integers, speeding up conflict checks.
• Early Pruning avoids exploring invalid paths.

Example 3 – Hard (Follow-Up: Symmetry Reduction)

Problem: Count solutions for N=12 without considering symmetric duplicates (e.g., rotations/reflections).

Twist

• Skip symmetric configurations to reduce computation.

Approach

1. Only generate solutions where the first queen is in the left half (col < (N+1)/2).
2. Multiply by 2 for symmetric solutions (unless N is odd and the first queen is in the center).

Python Code

def totalNQueensSymmetry(n):

    def backtrack(row, cols, diag1, diag2):

        if row == n:

            return 1

        count = 0

        for col in range(n):

            if row == 0 and col > (n - 1) // 2:  # Skip symmetric duplicates

                continue

            curr_diag1 = row - col

            curr_diag2 = row + col

            if (cols & (1 << col)) or (diag1 & (1 << curr_diag1)) or (diag2 & (1 << curr_diag2)):

                continue

            count += backtrack(

                row + 1,

                cols | (1 << col),

                diag1 | (1 << curr_diag1),

                diag2 | (1 << curr_diag2)

            )

        return count


    total = backtrack(0, 0, 0, 0)

    if n % 2 == 0:

        return total  2

    else:

        # For odd N, count center column separately

        center = (n - 1) // 2

        total_center = backtrack(0, 1 << center, 1 << (-center), 1 << center)

        return (total - total_center)  2 + total_center

Time & Space Complexity

• Time: O(N! / 2) (halved due to symmetry).
• Space: O(N).

Why This Works

• Symmetry Reduction avoids redundant work by skipping mirrored solutions.
• Bitmasking keeps the solution efficient.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s your N-Queens cheat sheet: 1. Represent the board as a 1D array or bitmask. 2. Backtrack row-by-row, pruning invalid columns/diagonals early. 3. Use sets or bitmasking for O(1) conflict checks. 4. Optimize with symmetry if counting solutions. 5. Edge cases: N=1 (1 solution), N=2/3 (0 solutions).

Remember: Interviewers care about your pruning logic, not just the final answer. Walk them through your constraints, and you’ll stand out. Now go solve it!

? Final Notes

• Practice: Solve N=4, N=8, and N=12 under time constraints.
• Follow-ups: Be ready for "count solutions" or "symmetry reduction" variants.
• Whiteboard: Sketch the backtracking tree to explain your approach.

This framework is directly usable in interviews—memorize the steps, and you’ll handle any N-Queens problem with confidence. ?