#include <iostream>
#include <string>
#include <vector>
#include <numeric>

using namespace std;

bool is_valid(const vector<int>& cols) {
    for (int i=0; i<cols.size(); ++i) {
        for (int j=i+1; j<cols.size(); ++j) {
            if (abs(cols[i]-cols[j]) == j-i)  //clash on diagonal
                return false;
        }
    }
    return true;
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> ret;
    vector<int> cols(n,0);
    iota(cols.begin(), cols.end(), 0);
    do {
        if (is_valid(cols)) {
            //add grid state in string format to ret
            vector<string> grid;
            string line(n, '.');
            for (int i=0; i<cols.size(); ++i) {  //the grid will be rotated but that doesn't matter
                line[cols[i]] = 'Q';
                grid.push_back(line);
                line[cols[i]] = '.';
            }
            ret.push_back(grid);
        }
    } while (next_permutation(cols.begin(), cols.end()));
    return ret;
}

void print_grids(const vector<vector<string>>& grids) {
    for (const vector<string>& grid : grids) {
        for (const string& line : grid)
            cout << line << "\n";
        cout << "\n";
    }
}

int main() {
    auto grids = solveNQueens(8);
    print_grids(grids);

    return 0;
}