N-Queens II.txt

class Solution {
public:
    int totalNQueens(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int count = 0;
        vector<int> pos;
        for (int i = 0; i < n; i++)
            pos.push_back(i);
        plan(count, pos, 0);
        return count;
    }
    void plan(int &count, vector<int>& pos, int p) {
        if (p == pos.size())
            count++;
        else {
            if (check(pos, p))
                plan(count, pos, p+1);
            for (int i = p + 1; i < pos.size(); i++) {
                swap(pos[p], pos[i]);
                if (check(pos, p))
                    plan(count, pos, p+1);
                swap(pos[p], pos[i]);
            }
        }
    }
    bool check(vector<int> &pos, int p) {
        for (int i = 0; i < p; i++) {
            if (abs(i-p) == abs(pos[i] - pos[p]))
                    return false;
        }
        return true;
    }
    void swap(int& a, int& b) {
        int t = a;
        a = b;
        b = t;
    }
};