/*
2001/11 チェス盤の分割
coded by Isaku WADA
 ┌────────────────────────────┐
 │4×4の板を,小正方形の辺に沿って大きさも形も同じ2枚の│
 │板に分割するには,回転・鏡像解を除いて6通りある。その全│
 │解をFig.3に示す。では,同じ要領で8×8の板での合同2分│
 │割は何通りあるだろうか(H.E.Dudeney,"Amusements in Mathe│
 │matics"(高木茂男訳)より)。               │
 │                            │
 │Fig.3 4×4の板を2分割する場合の全解        │
 │     ■■□□  ■■■□  ■■■□       │
 │     ■■□□  ■■■□  ■□■□       │
 │     ■■□□  ■□□□  ■□■□       │
 │     ■■□□  ■□□□  ■□□□       │
 │                            │
 │     ■■□□  ■■■□  ■■■□       │
 │     ■□□□  ■□□□  ■■□□       │
 │     ■■■□  ■■■□  ■■□□       │
 │     ■■□□  ■□□□  ■□□□       │
 └────────────────────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │Fig.1                           │
 │■■■■uts□                      │
 │■ABCrqp□                      │
 │■DEFonm□                      │
 │■GHIlkj□                      │
 │■JKLihg□                      │
 │■MNOfed□                      │
 │■PQRcba□                      │
 │■STU□□□□                      │
 │                              │
 │Fig.1中の■は左の板に固定し、□は右の板に固定します。このこ│
 │とにより、回転の排除は考えなくてよくなります。大文字のA〜U│
 │が示す21個は、左の板にもにも右の板にもなりえます。小文字の│
 │a〜uは、対応するのA〜Uが決まれば、自動的に逆の板に決まり│
 │ます。                           │
 │                              │
 │プログラムは21ビットの整数を順に生成します。そして、得られ│
 │た整数のビットパターンから、A〜Uが左右どちらの板に属するか│
 │を決めます。同時に、a〜uも対応するA〜Uにより決めます。こ│
 │れに、■と□を加えて8×8ビットのパターンを求めてゆきます。│
 │                              │
 │こうして得られた2の21乗個の8×8ビットパターンについて、│
 │飛び地がなければカウンタ NumOfSol をカウントします。ただし、│
 │u、t、sが共に右の板に属する場合は、上下を反転した鏡像が他│
 │に存在するので、別のカウンタ NumOfSol2 で数えます。     │
 │                              │
 │最後にNumOfSol+NumOfSol2/2+1を出力し解答とします。1を足して│
 │いるのは、2つの長方形に分かれる場合、鏡像解としてカウントさ│
 │れるのに、実際は1回しか現れないという例外があるからです。 │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・感想                           │
 │                              │
 │開発当初は、再帰呼び出しを使った別のアルゴリズムで、約30分│
 │かけて計算していました。しかし、ビットパターンを利用すること│
 │により、10秒以下に短縮できました。            │
 └──────────────────────────────┘
 Visual C++, Borland C++, gcc, LSI-C, Turbo C で動作確認
16ビットコンパイラでの実行時間は32ビットの約10倍
*/

#include <stdio.h>
#include <time.h>

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌────────────┐
 │マクロ・定数・変数の宣言│
 └────────────┘*/
typedef struct { long lo,hi; } LONG;            /* 64ビット整数 */
#define N 8                         /* チェス盤の大きさ。4,6 or 8 */
#define M ((N/2-1)*(N-1))  /* 可変部のビット数( N==8 なら M==21 ) */
#define TEST(X,P)  (P<32? X.lo & (1L<<(P)) : X.hi & (1L<<((P)-32)) )
#define SET(X,P)   (P<32?(X.lo|=  1L<<(P) ):(X.hi|=  1L<<((P)-32) ))
#define CLEAR(X,P) (P<32?(X.lo&=~(1L<<(P))):(X.hi&=~(1L<<((P)-32))))
long NumOfSol;     /* 通常解の数 */
long NumOfSol2;    /* 鏡像解の数 */
long SerialNo;     /* 現在調査中の21ビット整数 */
LONG StartEnclave; /* 飛び地の判定をする時の初期値 */
LONG AdjMat[N*N];  /* 隣接行列(1要素1ビットなので1次元配列) */
LONG StartMask;    /* mask を生成する時の初期値 */
int  LeftBit[M];   /* mask を生成する時に左半分に立てるビット */
int  RightBit[M];  /* mask を生成する時に右半分でクリアするビット */

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{
    double StartTime=clock(); int i,j,k;

    for (k=i=0;i<N;i++) for (j=0;j<N;j++,k++) { /* 隣接行列を作る */
        if (i>0) SET(AdjMat[k],k-N); if (i<N-1) SET(AdjMat[k],k+N);
        if (j>0) SET(AdjMat[k],k-1); if (j<N-1) SET(AdjMat[k],k+1);
    }

    for (i=0;i<N*N;i+=N) /* 左端の固定ビットを立てる */
    { SET(StartEnclave,i); SET(StartMask,i); }

    for (j=0;j<N/2;j++) /* 上端の固定ビットを立てる */
    { SET(StartEnclave,j); SET(StartMask,j); }

    /* StartMask, LeftBit, RightBit の設定 */
    for (i=0;i<N-1;i++) for (j=0;j<N/2-1;j++) {
        int a=i*(N/2-1)+j,b=(i+1)*N+j+1,c=(N-2-i)*N+N-2-j;
        LeftBit[a]=b; RightBit[a]=c; SET(StartMask,c);
    }

    /* メインループ */
    for (SerialNo=0;SerialNo<(1L<<M);SerialNo++) {
        LONG mask=StartMask,curr=StartEnclave,prev;

        /* SerialNo から8×8ビットのパターン(mask)を求める */
        for (i=0;i<M;i++) if (SerialNo&(1L<<i))
        { SET(mask,LeftBit[i]); CLEAR(mask,RightBit[i]); }

        /* 隣接行列を使って mask に飛び地があるかどうか調べる */
        do {
            prev=curr;
            for (i=0;i<N*N;i++) if (TEST(curr,i)) {
                /* 新たに移動できるビットを立てる */
                curr.lo|=AdjMat[i].lo&mask.lo;
                curr.hi|=AdjMat[i].hi&mask.hi;
            }
            /* curr が変化しなくなるまで繰り返す */
        } while (curr.lo!=prev.lo||curr.hi!=prev.hi);
        /* curr が元通りにならなければ、飛び地がある */
        if (curr.lo!=mask.lo||curr.hi!=mask.hi) continue;

        /* 鏡像解があるかないかで、カウントするカウンタを選ぶ */
        if ((mask.lo&(1<<(N/2)))==0) NumOfSol2++; else NumOfSol++;
    }

    printf(" %ld 通り  ",NumOfSol+NumOfSol2/2+1);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}