//**************************************************************************
// N-Queens Solutions   Recursive + OpenMP
//**************************************************************************
#include <stdio.h>
#include <time.h>
#include <omp.h>

#define  MAXSIZE   25
#define  MINSIZE    2
#define  i64  __int64

int  SIZE;  // N
int  LAST;  // SIZE - 1
int  TOPB;  // 1 << LAST
int  SIDE;  // TOPB | 1
i64  UNIQUE, TOTAL; // Number of Solutions

//**********************************************
// Check Unique Solutions
//**********************************************
void Check(int board[], int posA, int bitB, int posC, i64* count8, i64* count4, i64* count2)
{
    int  pos1, pos2, bit1, bit2;

    // 90-degree rotation
    if (board[posA] == 1) {
        for (pos1 = 1, bit2 = 2; pos1 < SIZE; pos1++, bit2 <<= 1) {
            for (pos2 = LAST, bit1 = 1; board[pos1] != bit1 && board[pos2] != bit2; pos2--, bit1 <<= 1);
            if (board[pos1] != bit1) return;
            if (board[pos2] != bit2) break;
        }
        if (pos1 == SIZE) {
            (*count2)++;
            return;
        }
    }

    // 180-degree rotation
    if (board[LAST] == bitB) {
        for (pos1 = 1, pos2 = LAST - 1; pos1 < SIZE; pos1++, pos2--) {
            for (bit2 = TOPB, bit1 = 1; board[pos1] != bit1 && board[pos2] != bit2; bit2 >>= 1, bit1 <<= 1);
            if (board[pos1] != bit1) return;
            if (board[pos2] != bit2) break;
        }
        if (pos1 == SIZE) {
            (*count4)++;
            return;
        }
    }

    // 270-degree rotation
    if (board[posC] == TOPB) {
        for (pos1 = 1, bit2 = TOPB >> 1; pos1 < SIZE; pos1++, bit2 >>= 1) {
            for (pos2 = 0, bit1 = 1; board[pos1] != bit1 && board[pos2] != bit2; pos2++, bit1 <<= 1);
            if (board[pos1] != bit1) return;
            if (board[pos2] != bit2) break;
        }
    }

    (*count8)++;
}
//**********************************************
// First queen is inside
//**********************************************
void InsideSub(int board[], i64* count8, i64* count4, i64* count2, int posA, int bitB, int posC, int gate, int y, int mask, int left, int right)
{
    int  bit, bits;

    if (y == SIZE) {
        Check(board, posA, bitB, posC, count8, count4, count2);
    }
    else {
        if (y == posC) mask |= SIDE; // Release of prohibited position
        bits = mask & ~(left | right);
        if (y == posA) {
            if (mask & TOPB) return;
            if (mask & 1) {
                if (!(bits & 1)) return;
                bits = 1;
            }
            else {
                // check of lastline bits and gate
                if (!(gate & mask & ~(left << (LAST - y) | right >> (LAST - y)))) return;
            }
        }
        else if (y == LAST) {
            bits &= gate;
        }
        while (bits) {
            bits ^= bit = -bits & bits;
            board[y] = bit;
            InsideSub(board, count8, count4, count2, posA, bitB, posC, gate, y + 1, mask ^ bit, (left | bit) << 1, (right | bit) >> 1);
        }
    }
}
void Inside(int x0, int x1, i64* unique, i64* total)
{
    int  board[MAXSIZE];
    int  mask, left, right;
    int  posA, bitB, posC, gate;
    i64  count8, count4, count2;

    // first check
    if (x1 >= (x0 - 1) && x1 <= (x0 + 1)) return;
    if (x0 > 1 && (x1 == 0 || x1 == LAST)) return;

    // Initialize
    mask = (1 << SIZE) - 1;
    count8 = count4 = count2 = 0;

    // ControlValue
    posA = LAST - x0;
    bitB = TOPB >> x0;
    posC = x0;
    gate = (mask >> x0) & (mask << x0);

    // y0: 000001110 (select)
    // y1: 111111111 (select)
    board[0] = 1 << x0;
    board[1] = 1 << x1;
    mask = mask ^ (board[0] | board[1]);
    left = board[0] << 2 | board[1] << 1;
    right = board[0] >> 2 | board[1] >> 1;
    if (posC >= 2) mask ^= SIDE;   // Forbidden position
    InsideSub(board, &count8, &count4, &count2, posA, bitB, posC, gate, 2, mask, left, right);

    // Finish
    *unique += count8 + count4 + count2;
    *total += count8 * 8 + count4 * 4 + count2 * 2;
}
//**********************************************
// First queen is in the corner
//**********************************************
void CornerSub(int board[], i64* count8, int posA, int y, int mask, int left, int right)
{
    int  bit, bits;

    if (y == SIZE) {
        (*count8)++;
    }
    else {
        bits = mask & ~(left | right);
        if (y == posA) mask |= 2; // Release of prohibited position
        while (bits) {
            bits ^= bit = -bits & bits;
            board[y] = bit;
            CornerSub(board, count8, posA, y + 1, mask ^ bit, (left | bit) << 1, (right | bit) >> 1);
        }
    }
}
void Corner(int x1, i64* unique, i64* total)
{
    int  board[MAXSIZE];
    int  mask, left, right;
    int  posA;
    i64  count8;

    // nitialize
    mask = (1 << SIZE) - 1;
    count8 = 0;

    // ControlValue
    posA = x1;

    // y=0: 000000001 (static)
    // y=1: 011111100 (select)
    board[0] = 1;
    board[1] = 1 << x1;
    mask = mask ^ (board[0] | board[1]);
    left = board[0] << 2 | board[1] << 1;
    right = board[0] >> 2 | board[1] >> 1;
    mask ^= 2;  // Forbidden position
    CornerSub(board, &count8, posA, 2, mask, left, right);

    // Finish
    *unique += count8;
    *total += count8 * 8;
}
//**********************************************
// Search of N-Queens
//**********************************************
void NQueens(void)
{
    int  i, x0, x1;
    i64  unique[MAXSIZE], total[MAXSIZE];

    // Constants on SIZE
    LAST = SIZE - 1;
    TOPB = 1 << LAST;
    SIDE = TOPB | 1;

    // Initialize (omp memory)
    for (i = 0; i < SIZE; i++)
        unique[i] = total[i] = 0;

    // First queen is in the corner
    // y=0: 000000001 (static)
    // y=1: 011111100 (select)
    #pragma omp parallel for
    for (x1 = 2; x1 < LAST; x1++) {
        Corner(x1, &unique[x1], &total[x1]);
    }

    // First queen is inside
    // y=0: 000001110 (select)
    // y=1: 111111111 (select)
    for (x0 = 1; x0 < SIZE / 2; x0++) {
        #pragma omp parallel for
        for (x1 = 0; x1 < SIZE; x1++) {
            Inside(x0, x1, &unique[x1], &total[x1]);
        }
    }

    // Totalling (omp memory -> shared memory)
    for (i = 0; i < SIZE; i++) {
        UNIQUE += unique[i];
        TOTAL += total[i];
    }
}
//**********************************************
// Format of Used Time
//**********************************************
void TimeFormat(clock_t utime, char* form)
{
    int  dd, hh, mm;
    double ftime, ss;

    ftime = (double)utime / CLOCKS_PER_SEC;

    mm = (int)ftime / 60;
    ss = ftime - (double)(mm * 60);
    dd = mm / (24 * 60);
    mm = mm % (24 * 60);
    hh = mm / 60;
    mm = mm % 60;

    if (dd) sprintf_s(form, 20, "%4d %02d:%02d:%05.2f", dd, hh, mm, ss);
    else if (hh) sprintf_s(form, 20, "     %2d:%02d:%05.2f", hh, mm, ss);
    else if (mm) sprintf_s(form, 20, "        %2d:%05.2f", mm, ss);
    else sprintf_s(form, 20, "           %5.2f", ss);
}
//**********************************************
// N-Queens Solutions MAIN
//**********************************************
int main(void)
{
    clock_t starttime;
    char form[20];

    printf("<------  N-Queens Solutions  -----> <---- time ---->\n");
    printf(" N:           Total          Unique days hh:mm:ss.--\n");
   for (SIZE = MINSIZE; SIZE <= MAXSIZE; SIZE++) {
        starttime = clock();
        UNIQUE = TOTAL = 0;
        NQueens();
        TimeFormat(clock() - starttime, form);
        printf("%2d:%16I64d%16I64d %s\n", SIZE, TOTAL, UNIQUE, form);
  }

    return 0;
}