//**************************************************************************
// N-Queens Solutions   Basic Code
//**************************************************************************
#include <stdio.h>
#include <time.h>

#define  MAXSIZE   25
#define  MINSIZE    2

int     SIZE;   // N
__int64 TOTAL;  // Number of Solutions

void Backtrack(int y, int mask, int left, int right)
{
    int  bit, bits;

    if (y == SIZE) {
        TOTAL++;
    }
    else {
        bits = mask & ~(left | right);
        while (bits) {
            bit = -bits & bits;
            bits ^= bit;
            Backtrack(y + 1, mask ^ bit, (left | bit) << 1, (right | bit) >> 1);
        }
    }
}
int main(void)
{
    clock_t stime;

    printf(" N:        Total      sec\n");
    for (SIZE = MINSIZE; SIZE <= MAXSIZE; SIZE++) {
        stime = clock();
        TOTAL = 0;
        Backtrack(0, (1 << SIZE) - 1, 0, 0);
        printf("%2d:%13I64d %8.2f\n", SIZE, TOTAL, (double)(clock() - stime) / CLOCKS_PER_SEC);
    }

    return 0;
}