class NQueens {
public:
    NQueens()   {       }
    ~NQueens()  {       }

    void backtrack(vector<vector<string>>& arrangements, vector<string> arrangement, int rowId, int squares,
                   vector<int> columns, vector<int> leftDiagonal, vector<int> rightDiagonal)
    {
        for (int colId = 0; colId < squares; ++colId) {
            if ( (arrangement[rowId][colId] == '.') && (columns[colId] == 1) &&
                 (leftDiagonal[rowId + colId] == 1) && (rightDiagonal[rowId - colId + (squares-1)] == 1) ) {
                arrangement[rowId][colId] = 'Q';
                leftDiagonal[rowId + colId] = 0;
                rightDiagonal[rowId - colId + (squares-1)] = 0;
                columns[colId] = 0;

                if (rowId<squares-1)
                    this->backtrack(arrangements, arrangement, rowId+1, squares, columns, leftDiagonal, rightDiagonal);
                else arrangements.push_back(arrangement);

                arrangement[rowId][colId] = '.';
                leftDiagonal[rowId + colId] = 1;
                rightDiagonal[rowId - colId + (squares-1)] = 1;
                columns[colId] = 1;
            }
        }
    }

    vector<vector<string>> solveNQueens(int n)
    {
        vector<vector<string>> arrangements;

        std::string rowArrangement(n, '.');
        vector<string> arrangement(n, rowArrangement);
        vector<int> leftDiagonal(2*n-1, 1);
        vector<int> rightDiagonal(2*n-1, 1);
        vector<int> columns(n, 1);

        this->backtrack(arrangements, arrangement, 0, n, columns, leftDiagonal, rightDiagonal);

        return arrangements;
    }
};