/*
2003/05 マッチ方陣
coded by Isaku WADA

 ┌─────────────────────────────┐
 │ マッチ棒をFig.2のように並べると,カドまたは交差点が16│
 │個できる。この16を4×4の魔方陣に見立てて,マッチの「頭│
 │」の数を魔方陣のように縦4本,横4本,斜め2本の列で同じに│
 │して並べたい。全体を回転したものや鏡像のものは別の解とはし│
 │ないで,全部で何通りの並べ方があるだろうか。Fig.2では,縦│
 │,横,そして斜め1本ではどこも6個になっているが,破線で示│
 │したところだけ8個になっていて,惜しくも失敗している。  │
 │                             │
 │    Fig.2 マッチ方陣(失敗例)            │
 │             /               │
 │      ・←・←・→・                │
 │      ↑ ↓ ↑/↑                │
 │      ・→・→・→・                │
 │      ↓ ↓/↑ ↑                │
 │      ・←・←・→・                │
 │      ↓/↓ ↑ ↓                │
 │      ・←・→・←・                │
 │     /                       │
 └─────────────────────────────┘
 ┌─────────────────┐
 │解答:118(5×5なら30800)│
 └─────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.04437 秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.03046 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.05172 秒│ 54272 byte │
 │gcc-2.953(djgpp)      │0.05110 秒│ 110227 byte │
 │gcc-2.953(cygwin)      │0.05078 秒│ 21105 byte │
 │LSI C-86 Ver 3.30 試食版  │0.07640 秒│ 14320 byte │
 │Turbo C Ver 1.5(small model)│0.09060 秒│ 11886 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP    │
 └──────────────┴─────────────┘
 ┌────────────────────────────┐
 │・プログラムの説明                   │
 │                            │
 │盤の状態は7×8の配列で表現しました。しかし、実際に使っ│
 │ているのは7×7です。8にした理由は、7だと奇数アドレス│
 │が起点のデータ転送が起こり、速度が遅くなるからです。アラ│
 │イメントを調整したことにより、かなり速度に貢献しました。│
 │                            │
 │プログラムは、マッチを左上から順に置いてゆき、カドまたは│
 │交差点の線が完成したら、頭の数をチェックしてゆきます。水│
 │平・垂直に置いたり、頭の数を数えたりする順序は単純ではあ│
 │りません。そこで、順序をchar*Schedule[] という文字列の配│
 │列で指定しておいて、再帰呼び出しをする関数Makeup()で実行│
 │するようにしました。例えば、文字列が"h01"なら座標(0,1)に│
 │水平にマッチを置きます。また、文字列が"v10"なら座標(1,0)│
 │に垂直にマッチを置きます。そして、文字列が"w00020406"な │
 │ら線(0,0),(0,2),(0,4),(0,6)の頭の数を求めます。さらに、 │
 │"c20222426"なら線(2,0),(2,2),(2,4),(2,6)の頭の数をチェッ│
 │クします。"q"まで進んだら解が見つかっています。このアイ │
 │ディアで、探索のスピードを落とすことなく、シンプルで分か│
 │りやすいプログラムを組むことができました。       │
 │                            │
 │回転や鏡像の排除を行うために過去の解の記録をとりますが、│
 │それは、24ビットに圧縮して32ビット単位で行います。 │
 │圧縮を行うタイミングは、回転または反転を行った後です。ま│
 │た、記録を呼び出したり、登録したりするときに、大きさ  │
 │256のハッシュテーブルを使って高速化しています。   │
 ├────────────────────────────┤
 │・感想                         │
 │                            │
 │5×5の場合も解いてみたところ。2分6秒で30800通り│
 │という結果を得ました。4×4ではハッシュテーブルを使う効│
 │果はあまりありませんが、5×5ではかなり効果があります。│
 └────────────────────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define N          4                /* 盤の大きさ(4か5) */
#define PRINT      1                /* 0なら解を表示しない */
#define MAX       (N*2-1)           /* map_t の一辺の長さ */
#define LOG       (N==4?118:30800)  /* ログの大きさ */
#define COL       (N==4?5:4)        /* 表示するとき横に並べる数 */
#define HASH_BITS (N==4?8:16)       /* ハッシュ表の大きさの元 */
#define HASH_SIZE (1<<HASH_BITS)    /* ハッシュ表の大きさ */
enum { NONE,LEFT,RIGHT,UP,DOWN };   /* マッチの状態 */
typedef char map_t[MAX][N==4?8:12]; /* 盤の状態(最低MAX×MAX) */

#if N == 4
typedef unsigned long LONG;
#else
#ifdef __GNUC__
typedef unsigned long long LONG;
#else
typedef unsigned __int64 LONG;
#endif
#endif

/*┌─────┐
 │変数の宣言│
 └─────┘*/
LONG Log[LOG];             /* 過去の解 */
int  LogSize;              /* 溜まった解の数 */
int  HashTable[HASH_SIZE]; /* ハッシュテーブル */
int  NextHash[LOG];        /* 同じハッシュ値をもつ次の要素 */

/*┌─────────────────────────────┐
 │Schedule[] : 置き方とチェックのスケジュール表、      │
 │    座標早見表 \X01234567         │
 │          Y┌───────          │
 │          0│・←・←・→・          │
 │          1│↑ ↓ ↑ ↑          │
 │          2│・→・→・→・          │
 │          3│↓ ↓ ↑ ↑          │
 │          4│・←・←・→・          │
 │          5│↓ ↓ ↑ ↓          │
 │          6│・←・→・←・          │
 │h/v で始まると続く座標にマッチを水平/垂直に置く      │
 │w で始まると続く線の頭の数を求めてFirstSumに記録する   │
 │c で始まると続く線の頭の数を求めてチェックする。q なら終了│
 └─────────────────────────────┘*/
#if N == 4
char*Schedule[]={
"h01", "h03", "h05", "v10", "v12", "v14", "v16", "w00020406",
"h21", "h23", "h25", "v30", "v32", "v34", "v36", "c20222426",
"h41", "h43", "h45", "v50", "v52", "v54", "v56", "c40424446",
"h61", "c00204060",  "c06244260",  "h63",        "c02224262",
"h65", "c04244464",  "c06264666",  "c60626466",  "c00224466","q"};
#endif

#if N == 5
char*Schedule[]={
"h01","h03","h05","h07","v10","v12","v14","v16","v18","w0002040608",
"h21","h23","h25","h27","v30","v32","v34","v36","v38","c2022242628",
"h41","h43","h45","h47","v50","v52","v54","v56","v58","c4042444648",
"h61","h63","h65","h67","v70","v72","v74","v76","v78","c6062646668",
"h81","c0020406080","c0826446280","h83","c0222426282","h85",
"c0424446484","h87","c0626466686","c8082848688","c0828486888",
"c0022446688","q"};
#endif

/*┌─────────┐
 │盤の状態を圧縮する│
 └─────────┘*/
LONG Compress(map_t Map)
{
    int i,j,k; LONG ret=0;

    for (k=i=0;i<MAX;i++) for (j=0;j<MAX;j++) if ((i+j)&1) {
        if ((i&1)==0) ret+=((LONG)(Map[i][j]==RIGHT))<<k++;
        else          ret+=((LONG)(Map[i][j]==DOWN))<<k++;
    }
    return ret;
}

#if PRINT != 0
/*┌──────────────┐
 │圧縮された盤の状態を元に戻す│
 └──────────────┘*/
void Uncompress(LONG x,map_t Map)
{
    int i,j,k;

    for (k=i=0;i<MAX;i++) for (j=0;j<MAX;j++) if ((i+j)&1) {
        if ((i&1)==0)
              Map[i][j]=(char)((x&((LONG)1<<k++))?RIGHT:LEFT);
        else  Map[i][j]=(char)((x&((LONG)1<<k++))?DOWN:UP);
    }
}

/*┌──────────────────┐
 │解の表示。引数が0ならフラッシュする│
 └──────────────────┘*/
void Print(LONG data)
{
    int i,j; static char buf[MAX][81];
    static int col; static map_t map;

    if (data) {
        col++; Uncompress(data,map);
        for (i=0;i<MAX;i++) {
            if (col!=1) strcat(buf[i]," ");
            for (j=0;j<MAX;j++)
             if ((i&1)==0&&(j&1)==0) strcat(buf[i],"・");
             else sprintf(buf[i]+strlen(buf[i]),"%.2s",
                          " ←→↑↓"+map[i][j]*2);
        }
    }
    if ((data==0&&col)||col==COL) {
        for (i=0;i<MAX;i++) { printf("%s\n",buf[i]); buf[i][0]=0; }
        printf("\n"); col=0;
    }
}
#endif

#define HASH_FUNC(X) ((int)((X)*(X)>>(sizeof(LONG)*8-HASH_BITS)))

/*┌────────────────────┐
 │盤Cmpと同じ物がログに見つかれば1を返す │
 └────────────────────┘*/
int SameMap(map_t cmp)
{
    LONG data=Compress(cmp); int i;

    for (i=HashTable[HASH_FUNC(data)];i!=-1;i=NextHash[i])
        if (Log[i]==data) return 1;
    return 0;
}

/*┌───────────────────────────┐
 │盤Cmpを右回転させて、ログに同じ物が見つかれば1を返す │
 └───────────────────────────┘*/
int Rotate(map_t cmp)
{
    int i,j; map_t buf; static char tbl[]={NONE,UP,DOWN,RIGHT,LEFT};

    memcpy(buf,cmp,sizeof buf);
    for (i=0;i<MAX;i++) for (j=0;j<MAX;j++)
        cmp[j][MAX-1-i]=tbl[(int)buf[i][j]];
    return SameMap(cmp);
}

/*┌────────────────────────────┐
 │盤Cmpを左右反転させて、ログに同じ物が見つかれば1を返す │
 └────────────────────────────┘*/
int Mirror(map_t cmp)
{
    int i,j; map_t buf; static char tbl[]={NONE,RIGHT,LEFT,UP,DOWN};

    memcpy(buf,cmp,sizeof buf);
    for (i=0;i<MAX;i++) for (j=0;j<MAX;j++)
        cmp[i][MAX-1-j]=tbl[(int)buf[i][j]];
    return SameMap(cmp);
}

/*┌───────────────────────────┐
 │MapをCmpに転送し、回転と鏡像を調べて新しければ記録する│
 └───────────────────────────┘*/
void CheckMap(map_t map)
{
    LONG data; int h; map_t cmp;

    memcpy(cmp,map,sizeof cmp);
    if (Rotate(cmp)||Rotate(cmp)||Rotate(cmp)||Mirror(cmp)||
        Rotate(cmp)||Rotate(cmp)||Rotate(cmp)) return;
    if (LogSize>=LOG) { printf("ログが小さい\n"); exit(1); }
    data=Compress(map); h=HASH_FUNC(data);
    NextHash[LogSize]=HashTable[h]; HashTable[h]=LogSize;
    Log[LogSize]=data; LogSize++;
}

/*┌───────────────────┐
 │スケジュールに従いながらパズルを解く。│
 └───────────────────┘*/
void Makeup(int level)
{
    static map_t map; static int FirstSum;
    char*p=Schedule[level]; int ch=*p++,i,j,k,sum;

    if (ch=='h') { /* マッチを水平に置く */
        i=*p++-'0'; j=*p-'0';
        map[i][j]=LEFT;  Makeup(level+1);
        map[i][j]=RIGHT; Makeup(level+1); return;
    }

    if (ch=='v') { /* マッチを垂直に置く */
        i=*p++-'0'; j=*p-'0';
        map[i][j]=UP;   Makeup(level+1);
        map[i][j]=DOWN; Makeup(level+1); return;
    }

    if (ch=='q') { CheckMap(map); return; }

    /* ここまで来るとchは必ず'w'か'c'なので、頭の数を求める */
    for (sum=k=0;k<N;k++) {
        i=*p++-'0'; j=*p++-'0';
        if (i>0&&map[i-1][j]==DOWN)     sum++;
        if (j>0&&map[i][j-1]==RIGHT)    sum++;
        if (i<MAX-2&&map[i+1][j]==UP)   sum++;
        if (j<MAX-2&&map[i][j+1]==LEFT) sum++;
    }

    if (ch=='w') FirstSum=sum;
    if (sum==FirstSum) Makeup(level+1);
}

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

    for (i=0;i<HASH_SIZE;i++) HashTable[i]=-1;
    LogSize=0; Makeup(0);
}

/*┌────────────────────┐
 │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();
#if PRINT != 0
    for (i=0;i<LogSize;i++) Print(Log[i]);
    Print(0);
#endif
    printf("解の個数=%d   ",LogSize);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}