# 52 - N-Queens II

解法一 - 暴力法

最簡單的方法就是枚舉所有可能方案，只要一發現是對的盤面就把答案加 1，可惜這個解法會 TLE。

class Solution {
public:
    int totalNQueens(int n) {
        int res=0;
        vector<int> cols;

        helper(n, cols, res);

        return res;
    }

private:
    void helper(int& n, vector<int>& cols, int& res) {
        if(cols.size() == n)
            res++;

        for(int col=0; col<n; col++) {
            if(!isValidBoard(col, cols))
                continue;

            cols.push_back(col);
            helper(n, cols, res);
            cols.pop_back();
        }
    }

    bool isValidBoard(int col, const vector<int>& cols) {
        int row = cols.size();

        for(int i=0; i<row; i++) {
            // Check vertical
            if(col = cols[i])
                return false;

            // Check top-left to bottom-right
            if(col-row == cols[i]-i)
                return false;

            // Check top-right to bottom-left
            if(col+row == cols[i]+i)
                return false;
        }

        return true;
    }
};

// idea: put into cols, if cols size is n, then add res by 1;

解法二 - 快速檢查

這題既然只問有幾種方法，我們就不需要紀錄每一列皇后的所在位置，而只需要用某種方法檢查每次放皇后會不會引起：

1. 同一列的衝突

2. 左上-右下對角線衝突

3. 右上-左下對角線衝突

這可以用三個 bool vector （也可以用 Hash Set，但應該會比較慢）來儲存就好。

class Solution {
public:
    int res;
    int totalNQueens(int n) {
        res = 0;

        vector<bool> cols(n);
        vector<bool> d1(2*n);
        vector<bool> d2(2*n);

        helper(cols, d1, d2, n, 0);

        return res;
    }

private:
    void helper(vector<bool>& cols, vector<bool>& d1, vector<bool>& d2, int& n, int row) {
        if(row == n)
            res++;
        else {
            for(int col=0; col<n; col++) {
                // because row-col might be negative, + n
                int id1 = col-row+n; 
                int id2 = col+row;

                if(cols[col] || d1[id1] || d2[id2])
                    continue;

                cols[col] = true;
                d1[id1] = true;
                d2[id2] = true;
                helper(cols, d1, d2, n, row+1);
                cols[col] = false;
                d1[id1] = false;
                d2[id2] = false;
            }
        }
    }    
};