class Solution {
    bool good(int a, int b, int dist) {
        return a != b && abs(a - b) != dist;
    }
    vector<char> columnTaken, diagTaken, diagTaken2;
    void rec(int row, int n, vector<vector<string>>& solutions, vector<string>& grid) {
        if(row == n) {
            solutions.push_back(grid);
            return;
        }
        for(int col = 0; col < n; ++col) {
            char& a = columnTaken[col];
            char& b = diagTaken[col+row];
            char& c = diagTaken2[col-row+n-1];
            if(!a && !b && !c) {
                a = b = c = true;
                grid[row][col] = 'Q';
                rec(row + 1, n, solutions, grid);
                grid[row][col] = '.';
                a = b = c = false;
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        if(n == 5) {
            vector<vector<string>> solutions;
            for(int a = 1; a <= n; ++a) {
                for(int b = 1; b <= n; ++b) {
                    if(good(a, b, 1)) {
                        for(int c = 1; c <= n; ++c) {
                            if(good(a, c, 2) && good(b, c, 1)) {
                                for(int d = 1; d <= n; ++d) {
                                    if(good(a, d, 3) && good(b, d, 2) && good(c, d, 1)) {
                                        for(int e = 1; e <= n; ++e) {
                                            if(good(a, e, 4) && good(b, e, 3) && good(c, e, 2) && good(d, e, 1)) {
                                                string A = ".....";
                                                string B = A;
                                                string C = B;
                                                string D = C;
                                                string E = D;
                                                A[a-1] = 'Q';
                                                B[b-1] = 'Q';
                                                C[c-1] = 'Q';
                                                D[d-1] = 'Q';
                                                E[e-1] = 'Q';
                                                solutions.push_back({A, B, C, D, E});
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return solutions;
        }
        columnTaken = diagTaken = diagTaken2 = vector<char>(2 * n, 0);
        vector<vector<string>> solutions;
        vector<string> grid(n, string(n, '.'));
        rec(0, n, solutions, grid);
        return solutions;
    }
};