/* Ｎクイーン問題(対称性の考慮なし) takaken 2003/4/23 */
#include <stdio.h>
#include <time.h>

#define MAXSIZE 18
#define MINSIZE  2

int  COUNT;
int  SIZE;
int  MASK;
int  BOARD[MAXSIZE];

void Display(void)
{
    int  y, bitmap, bit;

    printf("\nN=%d no.%d\n", SIZE, COUNT);
    for (y=0; y<SIZE; y++) {
        bitmap = BOARD[y];
        for (bit=1<<(SIZE-1); bit; bit>>=1)
            printf("%s ", (bitmap & bit)? "Q": "-");
        printf("\n");
    }
}
void Backtrack(int y, int down, int right, int left)
{
    int bitmap;
    static int bit;

    if (y == SIZE) {
        COUNT++;                                /* 配置を完了した */
        // Display();
    } else {
        bitmap = MASK & ~(down | right | left); /* 配置可能ビット */
        while (bitmap) {
            bit = -bitmap & bitmap;             /* 下位ビット抽出 */
            bitmap ^= bit;
            BOARD[y] = bit;                     /* 配置位置の記録 */
            Backtrack(y+1, down | bit, (right | bit) >> 1, (left | bit) << 1);
        }
    }
}
void Queen(void)
{
    int bitmap, bit, down, right, left;

    MASK = (1 << SIZE) - 1;

    /* 右半分限定 0行目:000001111 */
    bitmap = (1 << (SIZE / 2)) - 1; /* 0行目の配置可能ビット */
    while (bitmap) {
        bit = -bitmap & bitmap;
        bitmap ^= bit;
        BOARD[0] = bit;
        Backtrack(1, bit, bit >> 1, bit << 1);
    }

    /* 奇数の中央 0行目:000010000 */
    /* 右半分限定 1行目:000000111 */
    if (SIZE & 1) {
        bit = 1 << (SIZE / 2);      /* 0行目のビット */
        BOARD[0] = bit;
        down  = bit;
        right = bit >> 1;
        left  = bit << 1;
        bitmap = (bit - 1) >> 1;    /* 1行目の配置可能ビット */
        while (bitmap) {
            bit = -bitmap & bitmap;
            bitmap ^= bit;
            BOARD[1] = bit;
            Backtrack(2, down | bit, (right | bit) >> 1, (left | bit) << 1);
        }
    }

    COUNT *= 2; /* 左右反転パターンを考慮 */
}
int main(void)
{
    time_t st;

    for (SIZE=MINSIZE; SIZE<=MAXSIZE; SIZE++) {
        st = time(NULL);
        COUNT = 0;
        Queen();
        printf("N=%d -> %d %dsec\n", SIZE, COUNT, time(NULL)-st);
    }
    return 0;
}