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

using namespace std;

bool is_valid(const vector<int>& cols, int row) {
    for (int i=0; i<row; ++i) {
        if (cols[i] == cols[row] || abs(cols[i]-cols[row]) == row-i)
            return false;  //clash horizontal or diagonal
    }
    return true;
}

vector<vector<string>> solveNQueens(int n) {
    //using backtracking iteratively
    vector<vector<string>> ret;
    vector<int> cols(n, 0);
    int row = 0;

    while (true) {
        if (row == n) {  //valid complete board
            //compose string vector for board and add to ret
            vector<string> board;
            string line(n, '.');
            for (int pos : cols) {
                line[pos] = 'Q';
                board.push_back(line);
                line[pos] = '.';
            }
            ret.push_back(board);
            //continue search by going to last row and incrementing last queen
            cols[--row]++;
        }
        else if (cols[row] == n) {  //end of row
            cols[row--] = 0;  //reset queen position and move back one row
            if (row == -1) break;  //finished. let's break out
            cols[row]++;  //move queen forward one position.
        }
        else if (!is_valid(cols, row)) 
            cols[row]++;  //not valid, so move queen forward one position
        else
            row++;   //valid, so go to next row.        
    }
    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(5);
    cout << "calculated " << grids.size() << " boards:\n\n";
    print_grids(grids);

    return 0;
}