/* 修正版 takaken 2003/4/22 */
/************************************************************************/
/*      Ｎクイーン  Version 4                                           */
/*                                                                      */
/*      斜め２方向使用済検査方式、無駄検索の削除                        */
/*                                                                      */
/*      特徴                                                            */
/*      左端だけ例外処理                                                */
/*      サイズを可変に(30以下)                                          */
/*      盤面は１次元整数型配列、y位置の入れ替えによる                   */
/*      xの小さい方から、可能な場所を順次調べる                         */
/*      対象性は、８通りの可能な変換をし、最小の場合に採用              */
/*                                                                      */
/************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>               /* takaken */

#define MAXBOARDSIZE 20

int boardsize;
int answercount;
int printflag;
int board[MAXBOARDSIZE];        /* チェス盤 */
int sused[MAXBOARDSIZE*2-1];    /* ／方向が使用済み  */
int bused[MAXBOARDSIZE*2-1];    /* ＼方向が使用済み  */

int first1, first2;             /* takaken */

#define QUEEN   'Q'
#define BLANK   '.'

#define TRUE    1
#define FALSE   0

int compareboard( int *b0, int *b1 );
int isunique( void );
void    tryqueen( int x );
void    tryqueen0( void );
void    foundanswer( void );
void    printboard( int *b );
int main( int argc, char **argv );

/*----------------------------------------------------------------------*/
/*  盤上の状態による大小比較                                            */
/*----------------------------------------------------------------------*/
int compareboard(  int *b0, int *b1 )
{
    int x;

    for( x=0; x<boardsize; ++x, ++b0, ++b1 ) {
        if( *b0 != *b1 )
            return ( *b0 < *b1 ) ? -1 : 1;
    }
    return  0;
}

/*----------------------------------------------------------------------*/
/*  回転・反転などによるユニーク性のチェック                            */
/*----------------------------------------------------------------------*/
int isunique( void )
{
    int work[MAXBOARDSIZE]; /* 作業用チェス盤   */
    int x, t, w;

    for( t=1; t<8; ++t ) {                      /* takaken */
        if (t == 2) continue;                   /* takaken */
        if( t & 1 ) {   /* 斜め反転→作業盤 */
            for( x=0; x<boardsize; ++x )
            work[board[x]] = x;
        } else {
            for( x=0; x<boardsize; ++x )
            work[x] = board[x];
        }
        if( t & 2 ) {   /* 上下反転 */
            for( x=0; x<boardsize; ++x )
            work[x] = boardsize-1-work[x];
        }
        if( t & 4 ) {   /* 左右反転 */
            for( x=0; x<boardsize/2; ++x ) {
                w = work[x];
                work[x] = work[boardsize-1-x];
                work[boardsize-1-x] = w;
            }
        }
        if( compareboard( board, work ) > 0 )
            return  FALSE;
    }

    return  TRUE;
}

/*----------------------------------------------------------------------*/
/*  チェス盤の指定場所にクイーンを置けるか調べる                        */
/*----------------------------------------------------------------------*/
void    tryqueen( int x )
{
    int u, y;

    for( u=x; u<boardsize; ++u ) {
        y = board[u];
        if( sused[x-y+boardsize-1] )
            continue;
        if( bused[x+y] )
            continue;
        if (y==0 || y==boardsize-1)                 /* takaken */
            if (x<first1 || x>first2) continue;     /* takaken */

        sused[x-y+boardsize-1] = bused[x+y] = TRUE;
        board[u] = board[x];
        board[x] = y;

        if( x+1 == boardsize ) {
            foundanswer();
        } else {
            tryqueen( x+1 );
        }

        sused[x-y+boardsize-1] = bused[x+y] = FALSE;
        board[x] = board[u];
        board[u] = y;
    }
}

void    tryqueen0( void )
{
    int u, y;

    for( u=0; u<boardsize/2; ++u ) {
        y = board[u];

        sused[-y+boardsize-1] = bused[y] = TRUE;
        board[u] = board[0];
        board[0] = y;

        first1 = y;                             /* takaken */
        first2 = boardsize - 1 - y;             /* takaken */
        tryqueen( 1 );

        sused[-y+boardsize-1] = bused[y] = FALSE;
        board[0] = board[u];
        board[u] = y;
    }
}

/*----------------------------------------------------------------------*/
/*  解が見つかった                                                      */
/*----------------------------------------------------------------------*/
void    foundanswer( void )
{
    if( ! isunique() )
        return;

    ++answercount;

    if( printflag ) {
        printf( "Answer %d\n", answercount );
        printboard( board );
    }
}

/*----------------------------------------------------------------------*/
/*  チェス盤のプリント                                                  */
/*----------------------------------------------------------------------*/
void    printboard( int *b )
{
    int x, y;

    for( y=0; y<boardsize; ++y ) {
        for( x=0; x<boardsize; ++x ) {
            printf( " %c", b[x]==y ? QUEEN : BLANK );
        }
        printf( "\n" );
    }
    printf( "\n" );
}

/*----------------------------------------------------------------------*/
/*  メイン                                                              */
/*----------------------------------------------------------------------*/
int main( int argc, char **argv )
{
    int i;
    time_t st;

    printflag = FALSE;

    /* 連続実行に変更 takaken */
    for (boardsize=1; boardsize<=MAXBOARDSIZE; boardsize++) {

        st = time(NULL);

        answercount = 0;
        for( i=0; i<boardsize; ++i )
            board[i] = i;
        for( i=0; i<boardsize*2-1; ++i )
            sused[i] = bused[i] = FALSE;

        if(boardsize == 1)
            tryqueen(0);
        else
            tryqueen0();

        printf( "N=%2d -> Total count %d %dsec\n",
            boardsize, answercount, time(NULL) - st);
    }

    return  0;
}

/************************************************************************/
/*      End                                                             */
/************************************************************************/