#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

bool conflict(int row, int col, int row2, int col2);
bool isSafe(int* board, int row, int col);
void printBoard(int* board, int n);
int iterativeQueens(int n, bool print);
int recursiveQueens(int n, bool print);
void recursiveQueens(int* board, int n, int col, int& solutions, bool print);
int* createBoard(int n);


int main()
{
    auto start = duration_cast< milliseconds >(system_clock::now().time_since_epoch());

    auto sol = recursiveQueens(12, false); // 12x12
    auto finish = duration_cast< milliseconds >(system_clock::now().time_since_epoch()) - start;
    cout << sol << " Solutions found." << endl;
    cout << "Time = " << finish.count() << " ms." << endl;
    system("pause");
    return 0;
}

int recursiveQueens(int n, bool print)
{
    auto solutions = 0;
    auto board = createBoard(n);
    recursiveQueens(board, n, 0, solutions, print);
    return solutions;
}
void recursiveQueens(int* board, int n, int col, int& solutions, bool print)
{
    if(col == n)
    {
        if(print)
            printBoard(board, n);
        solutions++;
        return;
    }
    for(auto r = 0; r < n; r++)
    {
        if(isSafe(board, r, col))
        {
            board[col] = r;
            recursiveQueens(board, n, col + 1, solutions, print);
        }
    }
}
bool isSafe(int* board, int row, int col)
{
    for(auto i = 0; i < col;i++)
    {
        auto c = i;
        auto r = board[i];
        if (conflict(r, c, row, col))
            return false;
    }
    return true;
}
int* createBoard(int n)
{
    auto board = static_cast<int*>(malloc(n * sizeof(int)));
    for(auto i = 0; i < n;i++)
    {
        board[i] = -1;
    }
    return board;
}
int iterativeQueens(int n, bool print) {
    auto board = createBoard(n);
    auto solutions = 0;

    auto row = 0;
    while (row >= 0) {
        do {
            board[row]++;
        } while (board[row] < n && !isSafe(board, board[row], row));
        if (board[row] < n) {
            if (row < n - 1) {
                board[++row] = -1;
            } else {
                if (print)
                    printBoard(board, n);
                solutions++;
            }
        }
        else {
            row--;
        }
    }
    free(board);
    return solutions;
}
void printBoard(int* board, int n)
{
    cout << "---------size = " << n << "---------" << endl;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if (board[i] == j)
                cout << "Q";
            else
                cout << "*";
        }
        cout << endl;
    }
    cout << "--------------------------" << endl;
}
bool conflict(int row, int col, int row2, int col2) {
    return row == row2 || col == col2 || abs(col - col2) == abs(row - row2);
}