51. N-Queens

backtracking O(n!) time O(n) space
There is N possibilities to put the first queen, not more than N * (N - 2) to put the second one, not more than N * (N - 2) * (N - 4) for the third one etc. In total that results in O(n!) time complexity.
按row去dfs，只需统计col以及两个方向的斜边即可

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        chessboard.resize(n, string(n, '.'));
        only_col.resize(n);
        row_minus_col.resize((n << 1) - 1);
        row_plus_col.resize((n << 1) - 1);
        dfs(0);
        return res;
    }

private:
    void dfs(int r) {
        if (r == n) {
            res.push_back(chessboard);
            return;
        }
        for (int c = 0; c < n; ++c) {
            if (!only_col[c]
                && !row_minus_col[n - 1 + r - c]
                && !row_plus_col[r + c]) {
                only_col[c] = row_minus_col[n - 1 + r - c] = row_plus_col[r + c] = true;
                chessboard[r][c] = 'Q';
                dfs(r + 1);
                chessboard[r][c] = '.';
                only_col[c] = row_minus_col[n - 1 + r - c] = row_plus_col[r + c] = false;
            }
        }
    }

    int n;
    vector<bool> only_col, row_minus_col, row_plus_col;
    vector<string> chessboard;
    vector<vector<string> > res;
};