MANG Problem #12: N-Queens (Hard)

1. Problem Statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Return all distinct solutions to the n-queens puzzle.

2. Approach: Row-by-Row Backtracking

graph TD
    subgraph "Diagonal Constraints"
        Pos[Positive Diagonal: r + c = Constant]
        Neg[Negative Diagonal: r - c = Constant]
    end
    
    Backtrack[Row r] --> Loop[Try Col c]
    Loop --> Check{Safe?}
    Check -- Yes --> Recurse[Row r + 1]
    Check -- No --> NextCol[Try Next c]

We can place exactly one queen per row. The problem then becomes: "For each row, which column is safe?"

1. State: row index.
2. Choices: col indices from 0 to $N-1$.
3. Constraints: A queen at (r, c) is safe if no other queen is in:
   • The same column c.
   • The positive diagonal (r + c).
   • The negative diagonal (r - c).
4. Backtrack: Place queen, recurse to row + 1, then remove queen.

3. Java Implementation

class Solution {
    private Set<Integer> cols = new HashSet<>();
    private Set<Integer> posDiag = new HashSet<>(); // r + c
    private Set<Integer> negDiag = new HashSet<>(); // r - c
    private List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(0, n, board);
        return res;
    }

    private void backtrack(int r, int n, char[][] board) {
        if (r == n) {
            res.add(construct(board));
            return;
        }

        for (int c = 0; c < n; c++) {
            if (cols.contains(c) || posDiag.contains(r + c) || negDiag.contains(r - c)) {
                continue;
            }

            // Choose
            cols.add(c); posDiag.add(r + c); negDiag.add(r - c);
            board[r][c] = 'Q';

            // Explore
            backtrack(r + 1, n, board);

            // Un-choose (Backtrack)
            cols.remove(c); posDiag.remove(r + c); negDiag.remove(r - c);
            board[r][c] = '.';
        }
    }
}

4. 5-Minute "Video-Style" Walkthrough

1. The "Aha!" Moment: How do we check diagonals in $O(1)$?
   • Every cell on a diagonal sloping from top-right to bottom-left has the same sum of row and column (r + c).
   • Every cell on a diagonal sloping from top-left to bottom-right has the same difference of row and column (r - c).
2. The State Management: We use three HashSets (or boolean arrays) to track blocked paths. This is significantly faster than scanning the board for every placement.
3. The Symmetry: Note that N-Queens solutions are often symmetric. While we solve for all, you could theoretically optimize by solving for half the board and mirroring.

5. Interview Discussion

• Interviewer: "What is the time complexity?"
• You: "It is $O(N!)$ because we have $N$ choices for the first row, $N-2$ for the second, and so on. It is much better than a brute force $O(N^N)$."
• Interviewer: "How can we optimize the space?"
• You: "Instead of HashSet<Integer>, we can use Boolean arrays of size $N$ and $2N$ for columns and diagonals. For absolute peak performance, we could use Bitmasks."

Read Next

• MANG Problem #13: Edit Distance
• MANG Problem #14: K-th Smallest in Lexicographical Order 埋