52.md

52. N-Queens II

Leetcode link

解题思路

本题本质上跟 51 题的 N-Queens 是一个题，区别在于这题只需要计算个数就好

详细思路见 N-Queens，这里就选了一种方法实现了一下

C++

class Solution {
public:
    int res = 0;
    int totalNQueens(int n) {
        vector<int> queens(n, -1);
        
        backtrack(n, 0, queens, 0, 0, 0);
        return res;
    }
    
    void backtrack(int n, int row, vector<int> &queens, int col, int slash, int backslash) {
        if(row == n) {
            res++;
        } else {
            int available = ((1<<n) - 1) & (~(col | slash | backslash));
            while(available != 0) {
                int position = available & (-available);
                available &= available - 1;
                queens[row] = __builtin_ctz(position);
                
                backtrack(n, row+1, queens, col | position, (slash | position) << 1, (backslash | position) >> 1);
                
                queens[row] = -1;
            }
        }
    }
};