/*
2002/12 アルハンブラ・パズル
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ Fig.3のように,矢印が2つずつ描かれた2×1の大きさのタ│
 │イルが8枚ある。矢印の方向は数学的にきれいに選ばれている。│
 │ この8枚を平面状に並べて4×4の正方形を作るだけなら簡単│
 │にできるのだが,縦4列,横4列,対角線2列の合計10に,4│
 │方向のすべての矢印がそろうようにしたい。何通りの配置がある│
 │だろうか。                        │
 │ もちろん,全体を回転した解や鏡像解は別の解とはしない。ま│
 │た,タイルの裏返しは考えない。              │
 │                             │
 │ Fig.3 矢印が2つずつ描かれたタイル8枚        │
 │                             │
 │ ┌─┐┌─┐┌─┐┌─┐                │
 │ │→││→││→││↓│                │
 │ │ ││ ││ ││ │                │
 │ │↓││←││↑││↑│                │
 │ └─┘└─┘└─┘└─┘                │
 │ ┌─┐┌─┐┌─┐┌─┐                │
 │ │↓││←││↑││↑│                │
 │ │ ││ ││ ││ │                │
 │ │→││→││→││↓│                │
 │ └─┘└─┘└─┘└─┘                │
 │                             │
 └─────────────────────────────┘
 ┌────────────────────┐
 │解答:4通り              │
 ├────────────────────┤
 │ ┌─┬───┬─┐┌─┬───┬─┐ │
 │ │→│← ↑│↓││↑│↓ →│←│ │
 │ │ ├───┤ ││ ├───┤ │ │
 │ │↓│↑ ←│→││←│→ ↓│↑│ │
 │ ├─┴─┬─┴─┤├─┴─┬─┴─┤ │
 │ │← →│↓ ↑││↓ ↑│← →│ │
 │ ├───┼───┤├───┼───┤ │
 │ │↑ ↓│→ ←││→ ←│↑ ↓│ │
 │ └───┴───┘└───┴───┘ │
 │ ┌─┬─┬───┐┌─┬───┬─┐ │
 │ │→│↓│← ↑││←│→ ↓│↑│ │
 │ │ │ ├─┬─┤│ ├───┤ │ │
 │ │←│↑│→│↓││↑│↓ →│←│ │
 │ ├─┼─┤ │ │├─┴─┬─┴─┤ │
 │ │↑│←│↓│→││→ ←│↑ ↓│ │
 │ │ │ ├─┴─┤├───┼───┤ │
 │ │↓│→│↑ ←││↓ ↑│← →│ │
 │ └─┴─┴───┘└───┴───┘ │
 └────────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.01250 秒│ 40960 byte │
 │Microsoft Visual C++ .NET  │0.01250 秒│ 49152 byte │
 │Borland C++ 5.5.1 for Win32 │0.01469 秒│ 55808 byte │
 │gcc-2.953(djgpp)      │0.01429 秒│ 112244 byte │
 │gcc-2.953(cygwin)      │0.01422 秒│ 23268 byte │
 │LSI C-86 Ver 3.30 試食版  │0.02640 秒│ 15706 byte │
 │Turbo C Ver 1.5(small model)│0.02200 秒│ 13176 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │   OS:Windows XP   │
 └──────────────┴─────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │基本は、再帰呼び出しをしながら、左上から順に8個のタイルを回│
 │転させながら置いてゆくことです。              │
 │                              │
 │盤を表現するのに2つの4×4の配列(Map,Dir)を使っています。 │
 │Mapは、置かれたタイルの矢印がどちらを向いているかを記録しま │
 │す。Dirは、置かれたタイルのどの部分であるかを記録します。具 │
 │体的に説明すると、横向きなら右か左、縦向きなら上か下かを記録│
 │します。                          │
 │                              │
 │縦4列、横4列の合計8列に矢印がすべて揃うのを確かめるために│
 │8個のカウンタを用意し、置いたり取り除いたりする時に、増減さ│
 │せます。置いた時にカウンタが4になれば、その列に矢印がすべて│
 │揃ったかどうか確認します。                 │
 │                              │
 │問題文に登場するタイルのうち、奇数番目のタイルは180度回転│
 │させると違った矢印になるので、そのままと、180度回転の2通│
 │りについて置いてみます。偶数番目のタイルは180度回転させて│
 │も元の矢印と変わらないので、そのままについてのみ置き、180│
 │度回転はさせません。                    │
 │                              │
 │8枚のタイルを全て置くことができたら、対角線2列にすべての矢│
 │印が揃うかどうか確かめ、さらに、回転と鏡像を排除するために、│
 │MapとDirの両方の盤を、右90度回転を3回、上下反転を1回、さ│
 │らに、右90度回転を3回行いながら、過去の解と比較します。新│
 │しい解ならば記録して次に進みます。             │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │今回は難産でした。鏡像を排除するため上下逆にするときに、左右│
 │も逆にするというバグがあったため、なかなか正しい解答を得るこ│
 │とができませんでした。また、点対称なタイルも180度回転して│
 │置いていたために、同じ解が何度も出現するというバグにも悩まさ│
 │れました。回転と鏡像の排除は、先月号に比べ、より洗練された書│
 │き方ができるようになりました。               │
 └──────────────────────────────┘
*/

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

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define N    4        /* 盤の大きさ */
#define LOG 24        /* ログの大きさ */
#define COL  4        /* 表示の時に横に並べる数 */
#define T (N*N/2)     /* タイルの数 */
#define K (N*2+1)     /* 表示する時の行数 */
enum { WRITE,FLUSH }; /* 書き出し方を Print() へ指示する */
enum { U,R,D,L,B };   /* 上(Up)右(Right)下(Down)左(Left)プランク */
enum { S=2,A=4 };     /* Symmetry, Asymmetry */
enum { oooo,oooL,ooDo,ooDL,oRoo,  /* 罫線の取り得る状態 */
 oRoL,oRDo,oRDL,Uooo,UooL,UoDo,UoDL,URoo,URoL,URDo,URDL };

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char TileU[T]={R,R,R,D,D,L,U,U};  /* タイルの上側のデータ */
char TileD[T]={D,L,U,U,R,R,R,D};  /* タイルの下側のデータ */
char Sym[T]  ={A,S,A,S,A,S,A,S};  /* 点対称S/非点対称Aのデータ */
char TileFlag[T];                 /* タイルを使ったかどうか */
char Map[N][N],Dir[N][N];         /* 盤(矢印の向きとタイルの向き) */
char Tate[4],Yoko[4];             /* 検査するタイミングを図る */
char WorkMap[N][N],WorkDir[N][N]; /* 回転鏡像を記録 */
char LogMap[LOG][N][N],LogDir[LOG][N][N]; /* ログ */
int  LogSize;                             /* ログに溜まった解の数 */

/*┌─────────────────────────────┐
 │解の表示( COL だけ溜まるか mode を FLUSH にすると書き出す │
 └─────────────────────────────┘*/
void Print(int mode,char map[N][N],char dir[N][N])
{
    static char t[K][K],buf[K][K*COL*2+1];
    int i,j; static int col,id;

    if (mode==FLUSH) { /* FLUSH なのでバッファを強制的に書き出す */
        if (col) {
            for (i=0;i<col/K/2;i++) printf("%*d   ",K*2-3,++id);
            printf("\n");
            for (i=0;i<K;i++) printf("%s\n",buf[i]);
        }
        col=0; return;
    }

    /* 罫線メッシュを作成する */
    memset(t,oooo,sizeof t);
    for (i=0;i<K;i+=2) for (j=0;j<K;j++)
    { t[i][j]|=oRoL; t[j][i]|=UoDo; }
    for (i=0;i<K;i++) {
        t[i][0]&=URDo; t[i][K-1]&=UoDL;
        t[0][i]&=oRDL; t[K-1][i]&=URoL;
    }

    /* 罫線の調整 */
    for (i=0;i<N;i++) for (j=0;j<N;j++) {
        if (dir[i][j]==U) {
            t[i*2+2][j*2]  &=UoDL;
            t[i*2+2][j*2+1] =oooo;
            t[i*2+2][j*2+2]&=URDo;
        }
        if (dir[i][j]==L) {
            t[i*2][j*2+2]  &=URoL;
            t[i*2+1][j*2+2] =oooo;
            t[i*2+2][j*2+2]&=oRDL;
        }
    }

    for (i=0;i<K;i++) { /* バッファへ書き込む */
        for (j=0;j<K;j++)
         if (i&1&&j&1)
              sprintf(buf[i]+j*2+col,"%.2s",
                      "↑→↓← "+map[i>>1][j>>1]*2);
         else sprintf(buf[i]+j*2+col,"%.2s",
                      " ─│┐──┌┬│┘│┤└┴├┼"+t[i][j]*2);
    }
    col+=K*2;
    if (col==K*2*COL) { /* バッファが一杯になったので書き出す */
        for (i=0;i<COL;i++) printf("%*d   ",K*2-3,++id);
        printf("\n");
        for (i=0;i<K;i++) printf("%s\n",buf[i]);
        col=0;
    }
}

/*┌────────────────────────┐
 │過去のログと比較する。既に出現していれば1を返す│
 └────────────────────────┘*/
int Compare(void)
{
    int i;

    for (i=0;i<LogSize;i++)
     if (memcmp(WorkMap,LogMap[i],N*N)==0&&
         memcmp(WorkDir,LogDir[i],N*N)==0) return 1;
    return 0;
}

/*┌──────────────────────────┐
 │盤 Buf を90度右回りに回転させて、Compare() を返す │
 └──────────────────────────┘*/
int Rotate(void)
{
    char tmp[N][N]; int i,j; static char t[4]={R,D,L,U};

    memcpy(tmp,WorkMap,N*N);
    for (i=0;i<N;i++) for (j=0;j<N;j++)
        WorkMap[j][N-1-i]=t[(int)tmp[i][j]];
    memcpy(tmp,WorkDir,N*N);
    for (i=0;i<N;i++) for (j=0;j<N;j++)
        WorkDir[j][N-1-i]=t[(int)tmp[i][j]];
    return Compare();
}

/*┌─────────────────────┐
 │盤 Buf を上下反転させて、Compare() を返す │
 └─────────────────────┘*/
int TurnOver(void)
{
    char tmp[N][N]; int i,j; static char t[4]={D,R,U,L};

    memcpy(tmp,WorkMap,N*N);
    for (i=0;i<N;i++) for (j=0;j<N;j++)
        WorkMap[N-1-i][j]=t[(int)tmp[i][j]];
    memcpy(tmp,WorkDir,N*N);
    for (i=0;i<N;i++) for (j=0;j<N;j++)
        WorkDir[N-1-i][j]=t[(int)tmp[i][j]];
    return Compare();
}

/*┌────────────────────────────┐
 │得られた Map を過去ログと比較して新しいものなら登録する │
 └────────────────────────────┘*/
void CheckLog(void)
{
    memcpy(WorkMap,Map,N*N); memcpy(WorkDir,Dir,N*N);
    if (LogSize) {
        if (Compare() ||Rotate()||Rotate()||Rotate()) return;
        if (TurnOver()||Rotate()||Rotate()||Rotate()) return;
    }
    if (LogSize==LOG) { printf("LOG is small\n"); exit(1); }
    memcpy(LogMap[LogSize],  Map,N*N);
    memcpy(LogDir[LogSize++],Dir,N*N);
}

void Solve(int level); /* プロトタイプ宣言 */

/*┌────────────────┐
 │揃っているかどうかを調べるマクロ│
 └────────────────┘*/
#define TEST(Y,X) { for (*p=k=0;k<4;k++) f[(int)Map[Y][X]]=1; \
                    if (*p!=0x01010101L) ok=0; }

/*┌──────────┐
 │タイルを縦方向に置く│
 └──────────┘*/
void UpDown(int i,int j,int level)
{
    int a,b,k; static char f[4],ok; long*const p=(long*)f;

    if (i>N-2||Dir[i+1][j]!=B) return;
    for (a=0;a<T;a++) if (TileFlag[a]==0) for (b=0;b<Sym[a];b+=2) {
        Map[i][j]  =(char)(((b?TileD[a]:TileU[a])+b)&3);
        Map[i+1][j]=(char)(((b?TileU[a]:TileD[a])+b)&3);
        ok=1;
        if ((Tate[j]+=2)==4)    TEST(k,j);
        if (++Yoko[i]==4&&ok)   TEST(i,k);
        if (++Yoko[i+1]==4&&ok) TEST(i+1,k);
        if (ok) {
            TileFlag[a]=1; Dir[i][j]=U; Dir[i+1][j]=D;
            Solve(level+1);
            TileFlag[a]=0; Dir[i][j]=B; Dir[i+1][j]=B;
        }
        Tate[j]-=2; Yoko[i]--; Yoko[i+1]--;
    }
}

/*┌──────────┐
 │タイルを横方向に置く│
 └──────────┘*/
void LeftRight(int i,int j,int level)
{
    int a,b,k; static char f[4],ok; long*const p=(long*)f;

    if (j>N-2||Dir[i][j+1]!=B) return;
    for (a=0;a<T;a++) if (TileFlag[a]==0) for (b=0;b<Sym[a];b+=2) {
        Map[i][j]  =(char)(((b?TileD[a]:TileU[a])+b+1)&3);
        Map[i][j+1]=(char)(((b?TileU[a]:TileD[a])+b+1)&3);
        ok=1;
        if ((Yoko[i]+=2)==4)    TEST(i,k);
        if (++Tate[j]==4&&ok)   TEST(k,j);
        if (++Tate[j+1]==4&&ok) TEST(k,j+1);
        if (ok) {
            TileFlag[a]=1; Dir[i][j]=L; Dir[i][j+1]=R;
            Solve(level+1);
            TileFlag[a]=0; Dir[i][j]=B; Dir[i][j+1]=B;
        }
        Yoko[i]-=2; Tate[j]--; Tate[j+1]--;
    }
}

/*┌──────┐
 │パズルを解く│
 └──────┘*/
void Solve(int level)
{
    int i,j=0;

    if (level==0) { memset(Dir,B,sizeof Dir); LogSize=0; }
    if (level==T) {
        /* 斜めに揃っているかどうか確認する */
        int k; static char f1[4],f2[4];
        long*const p1=(long*)&f1,*const p2=(long*)&f2;
        for (*p1=*p2=k=0;k<4;k++)
        { f1[(int)Map[k][k]]=1; f2[(int)Map[k][N-1-k]]=1; }
        if (*p1!=0x01010101L||*p2!=0x01010101L) return;

        CheckLog(); return;
    }
    for (i=0;i<N;i++) {
        for (j=0;j<N;j++) if (Dir[i][j]==B) break;
        if (j<N) break;
    }
    UpDown(i,j,level); LeftRight(i,j,level);
}

/*┌────────────────────┐
 │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

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); int i,num;

    if (argc==2) num=atoi(argv[1]); else num=1;
    for (i=0;i<num;i++) Solve(0);
    for (i=0;i<LogSize;i++) Print(WRITE,LogMap[i],LogDir[i]);
    Print(FLUSH,0,0);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}