N-Queens II

<-H 52> N-Queens II

class Solution {

private:
    vector<int> columns;
    vector<int> main_diag;
    vector<int> anti_diag;
    int ans_count;

    void dfs(vector<int> &count, int row) {
        const int num = count.size();
        if(row == num) {
            this->ans_count++;
            return;
        }

        for(int j = 0; j < num; j++) {
            bool ok = columns[j] == 0 && main_diag[row + j] == 0 &&
                anti_diag[row - j + num] == 0;

            if(!ok)
                continue;
            count[row] = j;
            columns[j] = main_diag[row + j] = anti_diag[row - j + num] = 1;
            dfs(count, row + 1);

            count[row] = 0;
            columns[j] = main_diag[row + j] = anti_diag[row - j + num] = 0;
        }
    }
public:
    int totalNQueens(int n) {
        this->columns = vector<int> (n, 0);
        this->main_diag = vector<int> (2 * n, 0);
        this->anti_diag  = vector<int> (2 * n, 0);
        this->ans_count = 0;

        vector<int> count(n, 0);
        dfs(count, 0);
        return this->ans_count;
    }
};