#include <iostream>

void tryQueen(int col, int n, int* trace, bool* rowFlag, bool* pDiaFlag, bool* sDiaFlag) {
    if (col == n) {
        std::cout << "Position of " << n << " queens (row, col): \n";
        for (int c = 0; c < n; ++c) {
            int r = trace[c];
            std::cout << "(" << r << ", " << c << ")\n";
        }

        std::cout << "\nDrawing the board...\n";
        int* traceRow = new int[n]();
        for (int c = 0; c < n; ++c) {
            traceRow[trace[c]] = c;
        }
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                std::cout << (traceRow[r] == c ? '*' : '.') << ' '; 
            }
            std::cout << '\n';
        }
        std::cout << '\n';
        
        delete[] traceRow;

        return;
    }
    for (int row = 0; row < n; ++row) {
        if (!rowFlag[row] && !pDiaFlag[n-1+(col-row)] && !sDiaFlag[n*2-2-(row+col)]) {
            trace[col] = row;
            rowFlag[row] = true;
            pDiaFlag[n-1+(col-row)] = true;
            sDiaFlag[n*2-2-(row+col)] = true;
            tryQueen(col+1, n, trace, rowFlag, pDiaFlag, sDiaFlag);
            rowFlag[row] = false;
            pDiaFlag[n-1+(col-row)] = false;
            sDiaFlag[n*2-2-(row+col)] = false;
        }
    }
}

int main() {
    int n;
    std::cout << "Enter n: ";
    std::cin >> n;

    int* trace = new int[n]();
    bool* rowFlag = new bool[n]();
    bool* pDiaFlag = new bool[n*2-1]();
    bool* sDiaFlag = new bool[n*2-1]();

    tryQueen(0, n, trace, rowFlag, pDiaFlag, sDiaFlag);

    delete[] trace;
    delete[] rowFlag;
    delete[] pDiaFlag;
    delete[] sDiaFlag;

    return 0;
}