Link to Question

HARD

N-Queens II

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.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example

Input:

n = 4

Output:

2

Explanation:
There are two distinct solutions to the 4-queens puzzle.

---

Constraints

• 1 ≤ n ≤ 9

---

Solution: Backtracking

• Time Complexity: O(n!)
• Space Complexity: O(n)

C++

class Solution {
public:
    int totalNQueens(int n) {
        int count = 0;
        vector<bool> col(n, false), diag1(2*n-1, false), diag2(2*n-1, false);
        function<void(int)> dfs = [&](int row) {
            if (row == n) {
                ++count;
                return;
            }
            for (int c = 0; c < n; ++c) {
                if (col[c] || diag1[row+c] || diag2[row-c+n-1]) continue;
                col[c] = diag1[row+c] = diag2[row-c+n-1] = true;
                dfs(row+1);
                col[c] = diag1[row+c] = diag2[row-c+n-1] = false;
            }
        };
        dfs(0);
        return count;
    }
};