Description

Submission

class Solution {
public:
    int totalNQueens(int n) {
        int res = 0;
        vector<bool> col_taken(n, false);
        vector<string> board(n);
        vector<int> queen_col(n, -1);
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                board[i].push_back('.');
            }
        }

        backtrack(res, board, col_taken, queen_col, 0);

        return res;
    }

private:

    void backtrack(int& res, vector<string>& board,
            vector<bool>& col_taken, vector<int>& queen_col, int row) {
        if(row == board.size()) {
            res++;
        }

        for(int col = 0; col < board.size(); ++col) {
            if(col_taken[col]) continue;
            if(!check(board, queen_col, row, col)) continue;
            board[row][col] = 'Q';
            col_taken[col] = true;
            queen_col[row] = col;
            backtrack(res, board, col_taken, queen_col, row + 1);
            queen_col[row] = -1;
            board[row][col] = '.';
            col_taken[col] = false;
        }

    }

    bool check(vector<string> &board, vector<int>& queen_col, int row, int col) {

        for(int i = 0; i < queen_col.size() && queen_col[i] != -1; ++i) {
            if(abs(row - i) == abs(queen_col[i] - col)) {
                return false;
            }
        }

        return true;
    }
};