N-Queens II

Follow up for N-Queens problem.

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

tag: backtracking

此题与上一题非常相似，只是把“输出所有可能情况”改成了“输出所有可能情况的个数”。详细解析请看上一题的结题报告： N-Queens

class Solution {
public:
    int totalNQueens(int n) {
        if(n == 0){
            return 0;
        }
        int queen[n] = {0};
        int sum = 0;
        for(int i = 0; i < n; i++){
            queen[0] = i;
             sum += _totalNQueens(1, n, queen);
        }
        return sum;
    }
    int _totalNQueens(int row, int size, int *queen){
        if(row == size){
            return 1;//finish, find a solution 
        }
        int sum = 0;
        for(int i = 0; i < size; i++){
            if(isValid(row, i, size, queen)){
                queen[row] = i;
                sum += _totalNQueens(row + 1, size, queen);
            }
        }
        return sum;
    }
    bool isValid(int row, int column, int size, int *queen){
        for(int i = 0; i < row; i++){
            if(queen[i] == column){
                return false;//check column
            }
            if(abs(queen[i] - column) == row - i){
                return false;//check diagonal
            }
        }
        return true;
    }
};