#include <iostream>
#include <cmath>
/** The N-Queens problem - place n queens on an nxn
chess board such that none of the queens attack one
another.
int sz = 10;
int* x = new int[sz];
*/



bool place(int* x, int k, int i) {
    //returns true if Q can be placed
    //in kth row and ith column,
    //x[k] is a global array with
    //first k-1 values set already
    for(int j=0; j < k; ++j)     {
        if((x[j]==i)||(std::abs(x[j]-i)==std::abs(j-k)))
            return false;
    }
    return true;
}

void print(int* x, int n) {
    for(int i = 0; i < n; ++i) { //for each row
        for(int j = 0; j < x[i]; ++j) // skip queenless columns
            std::cout << ".";
        std::cout << "Q";// << std::endl; //put queen in its column
        for(int j = x[i]+1; j < n; ++j) // skip queenless columns
            std::cout << ".";
        std::cout << std::endl;
    }
}

void NQueens(int* x, int k, int n) {
    for(int i=0; i < n; ++i) {  // for each column of the kth row
        if(place(x, k,i))         {
            x[k]=i;
            if(k==n-1) {
                print(x,n);
                std::cout<<std::endl;
            }
            else NQueens(x, k+1, n);
        }
    }
}

int main() {
    int sz;
    std::cout << "\nHow big is your board? (n>3): ";
    std::cin>>sz;
    int* x = new int[sz]{0};
    NQueens(x,0,sz);
    delete[] x;
}