Description

Submission

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

        backtrack(res, board, col_taken, 0);

        return res;

    }

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

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

    }

    bool check(vector<string> &board, int i, int j) {
        vector<vector<int>> steps = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};

        for(auto step: steps) {
            for(int r = i, c = j;
                r >= 0 && c >= 0 && r < board.size() && c < board.size();
                r += step[0], c += step[1]) {
                if(board[r][c] == 'Q') return false;
            }
        }

        return true;
    }
};

Submission II

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        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(vector<vector<string>>& res, vector<string>& board,
            vector<bool>& col_taken, vector<int>& queen_col, int row) {
        if(row == board.size()) {
            res.push_back(board);
        }

        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;
    }
};

Submission III 210416

class Solution {
    vector<vector<string>> rets;
    vector<string> hand;
    vector<int> colTaken;
    int n;

    bool isDiagnolValid(int row, int col) {
        for(int r = row-1, c = col-1; r >= 0 && c >= 0; --c, --r) {
            if(hand[r][c] == 'Q') return false;
        }

        for(int r = row-1, c = col+1; r >= 0 && c < n; --r, ++c) {
            if(hand[r][c] == 'Q') return false;
        }

        return true;
    }
    void backtrack(int row, int col) {
        if(row == n) {
            rets.push_back(hand);
            return;
        }
        
        for(int i = 0; i < n; ++i) {
            if(!colTaken[i] && isDiagnolValid(row, i)) {
                hand[row][i] = 'Q';
                colTaken[i] = 1;
                backtrack(row+1, col);
                hand[row][i] = '.';
                colTaken[i] = 0;
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        
        colTaken.resize(n);

        hand.resize(n, string(n, '.'));

        backtrack(0, 0);
        return rets;
    }
};