52. N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

record数组记录 record[i]表示第i行皇后所在的列数。

class Solution {
public:
    int totalNQueens(int n) {
        if(n < 1)   return 0;

        vector<int> record(n);

        return process(0, record, n);
    }
private:
    int process(int i, vector<int> &pos, int n){
        if( i == n){
            return 1;
        }
        int res = 0;

        //遍历，找到第i行皇后可以放置的位置
        for(int j = 0; j < n; j++){
            //第i行放在j列是否有效
            if(isValid(pos, i, j)){
                pos[i] = j;
                res += process(i + 1, pos, n);
            }
        }
        return res;
    }

    bool isValid(vector<int> &position, int i, int j){
        for(int k = 0; k < i; k++){
            if(j == position[k] || abs(position[k] - j) == abs(i - k)){
                return false;
            }
        }
        return true;
    }
};