/*
2005/6 Good Dance
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ Fig.1のように、15枚のピースがある。ピースの形状は3種│
 │類あり、辺の長さはすべて同じである。各ピースには、辺の中心│
 │から別の辺の中心につながるラインとその向きを示す飛行機が描│
 │かれている。裏返しは考えない。各ピースのラインパターンは数│
 │学的に美しいセレクションとなっている。          │
 │ さて、この15枚を重なりなく隙間なく並べて正十二角形を作│
 │る。このとき、各ピースに描かれたラインは、外周で切れてもか│
 │まわないが、内部では必ずつながってなければならない。ループ│
 │になっていてもよい。そして、つながったライン上で飛行機がす│
 │べて同じ方向になっているようにしたい。          │
 │ Fig.1では3本の独立したラインがあり、これを3本解と呼ぶ│
 │。では、1本解から5本解までについて、それぞれ何通りの並べ│
 │方があるかをお答えいただきたい。なお、全体を回転した解や鏡│
 │像解は、別の解とはしない。また、正方形ピースの内角はすべて│
 │90度、そして2種類の形状があるひし形ピースの内角は、60│
 │度と120度、および30度と150度で構成されている。念の│
 │ため。                          │
 │                             │
 │※Fig.1は、プログラムを実行すると、何回目かに得られる。 │
 └─────────────────────────────┘
 ┌─────┐
 │解答:  │
 │1本解: 20│
 │2本解:  0│
 │3本解:452│
 │4本解:164│
 │5本解:194│
 └─────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ デバッグをするのに、コンソールによる文字出力だけでは、限│
 │界を感じたので、Win32APIのグラフィック機能を使いました。 │
 │Visual C++とBorland C++では、自動的にグラフィックのコード │
 │をコンパイルします。他のコンパイラではグラフィックのコード│
 │はコンパイルされません。                 │
 │ プログラムはまず、外周にピースを再帰呼び出しをしながら、│
 │隙間なく置いてゆきます。一番最初に置くピースは、鋭角が60│
 │度のものに固定しました。外周に置くことができたら、12個の│
 │頂点ごとにコード化し、回転と鏡像を排除します。結果として5│
 │0通りの置き方があります。                │
 │ できあがった外周のデータから各ピースのリンクを求めます。│
 │リンクとはピースをノード、辺をエッジとしたグラフのようなも│
 │のです。外周に置いたピースの内側の線についてのデータも作成│
 │します。その後、事前に求めておいたデータにより、内側に残り│
 │のピースを置きます。結果として、ピースの詰め方は43通りあ│
 │ります。グラフィックを使った場合、メッセージボックスが現れ│
 │ます。はいをクリックすると、リンクの確認をします。キャンセ│
 │ルをクリックすると、このメッセージボックスは出現しなくなり│
 │ます。                          │
 │ ピースを詰め終わったら、1本解から5本解のカウンタをリセ│
 │ットし、今度は飛行機を再帰呼び出しをしながら置いてゆきます│
 │。置き終わったら、グラフィックを使った場合、結果を表示する│
 │かどうかのメッセージボックスが現れます。はいをクリックする│
 │と、その詰め方に限り置き方を表示します。キャンセルをクリッ│
 │クすると、このメッセージボックスは出現しなくなります。そし│
 │て、何本解か計算し、該当するカウンタをインクリメントします│
 │。次の詰め方に移る前に、左右対称なら各カウンタを半分にし、│
 │120度回転で等しい場合は各カウンタを3で割り、左右対称か│
 │つ120度回転で等しい場合なら、各カウンタを6で割ります。│
 │そして、全体のカウンタに、各カウンタを足します。     │
 │                             │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 今回は難問でした、外周を詰め終わった後、内部にピースを詰│
 │める処理を自動化したかったのですが、やり方がわからず、手作│
 │業でデータを作成して、それを利用してしまいました。また、対│
 │称性の判断も目視で行いました。これらのように力わざに頼って│
 │しまったのが残念ですが、期限内に解等を手に入れたかったので│
 │、妥協しました。                     │
 └─────────────────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │ 実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Visual Studio C++ 6.0     │  1.985 秒│ 57344 byte │
 │Visual Studio C++ 2003     │  1.765 秒│ 49152 byte │
 │Borland C++ 5.5.1 for Win32 │  2.547 秒│ 61440 byte │
 │gcc-2.953(djgpp)      │  2.143 秒│ 113836 byte │
 │gcc-3.3.3(cygwin)      │  2.172 秒│ 19456 byte │
 │LSI C-86 Ver 3.30 試食版  │  4.230 秒│ 16926 byte │
 │Turbo C Ver 1.5(small model)│  4.670 秒│ 14546 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP     │
 └──────────────┴─────────────┘
*/
#if defined(__BORLANDC__) || defined(_MSC_VER)
#define GRAPHICS
#include <windows.h>
#endif

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

typedef unsigned char byte;

/*┌────────┐
 │定数と変数の宣言│
 └────────┘*/
int  Angle[3][2]={{90,90},{60,120},{30,150}}; /* ピースの角度 */
byte Type[15];      /* どの形のピースを置くか */
byte Dir[15];       /* ピースの最初の頂点が鋭角なら0 */
byte Pos[15];       /* ピースを外周の何番目の点に置くか */
byte Arrange[15][4];/* ピースの辺が飛行機の出発点なら1到着点なら2 */
byte OuterCode[12]; /* 外周の並べ方をコード化してまとめたもの */
byte Log[100][12];  /* 新しい OuterCode[] を記録するログ */
int  LogSize;       /* Log[][]にたまった要素の数 */
int  PatternID;     /* 何番目に隙間なく詰められたか */
byte Link[15][4];   /* ピースの各辺がどのピースと繋がっているか */
byte Back[15][4];   /* Link[][]で得られたピースのどの辺に出たか */
byte LineFrom[12];  /* 内周線の外側のピースの番号 */
byte LineIndex[12]; /* 内周線の外側のピースのどの辺が接しているか */
int  LineAngle[12]; /* 内周線の外側の折れ方の角度 */
int  LineLevel;     /* 内周線の外側にあるピースの総数 */
int  LineLength;    /* 内周線が何本の辺で構成されているか */
int  LineStartAngle;/* 最初の内周線の角度 */
int  Divider;       /* 各PatternIDにおける割るべき数 */
int  Count[7];      /* 各PatternIDにおける1本解から5本解の数 */
int  Total[7];      /* 1本解から5本解の総数 */

#ifdef GRAPHICS

#define LINE_SIZE 40                    /* 線の長さ(ピクセル単位) */
#define WINDOW_SIZE (5*LINE_SIZE)       /* ウィンドウの大きさ */
#define START_X ((int)( 1.6*LINE_SIZE)) /* 描画の開始横位置 */
#define START_Y ((int)(0.16*LINE_SIZE)) /* 描画の開始縦位置 */
#define RADIAN(X) ((3.14159265358979324/180.0)*(X)) /* 度から変換 */

HWND ConWnd;        /* コンソールウィンドウのハンドル */
HWND SubWnd;        /* サブウィンドウのハンドル */
int  RectPosX[15];  /* ピースの横位置 */
int  RectPosY[15];  /* ピースの縦位置 */
int  RectAngle[15]; /* ピースの傾き */

/*┌───────────────────────┐
 │度を引数とし sin(r) に LINE_SIZE をかけたもの │
 └───────────────────────┘*/
int Sin(int r)
{
    static int stbl[91]; int i;

    if (stbl[90]==0) {
        for (i=0;i<=90;i++)
            stbl[i]=(int)(sin(RADIAN(i))*LINE_SIZE+0.5);
        stbl[0]=0; stbl[30]=LINE_SIZE/2; stbl[90]=LINE_SIZE;
    }
    while (r>360) r-=360;
    while (r < 0) r+=360;
    if (r>180) return-Sin(r-180);
    if (r>90)  r=180-r;
    return stbl[r];
}

/*┌───────────────────────┐
 │度を引数とし cos(r) に LINE_SIZE をかけたもの │
 └───────────────────────┘*/
int Cos(int r) { return Sin(r+90); }

/*┌─────────────────────────┐
 │ピースを一つ描く。指定したリンクがあれば強調する │
 │また飛行機があれば線を引き、到着点に小さい丸を描く│
 └─────────────────────────┘*/
void DrawOneRect(int link,HDC dc,int i)
{
    int k,dir=Dir[i],type=Type[i],x=RectPosX[i],y=RectPosY[i];
    int a=RectAngle[i],tx[4],ty[4],ta[4],start=0,goal=0,c=0;
    HPEN old=0,pen=CreatePen(PS_SOLID,3,RGB(0,0,255));

    MoveToEx(dc,x,y,0);
    for (k=0;k<4;k++) {
        tx[k]=x; ty[k]=y; ta[k]=a;
        x+=Cos(a); y+=Sin(a);
        a+=Angle[type][dir^(k&1)];
        if (Link[i][k]==link) old=(HPEN)SelectObject(dc,pen);
        LineTo(dc,x,y);
        if (Link[i][k]==link) SelectObject(dc,old);
    }
    DeleteObject(pen);
    for (k=0;k<4;k++) {
        if (Arrange[i][k]==1) { start=k; c|=1; }
        if (Arrange[i][k]==2) { goal=k;  c|=2; }
    }
    if (c==3) {
        pen=CreatePen(PS_SOLID,1,RGB(0,0,255));
        old=(HPEN)SelectObject(dc,pen); a=ta[start];
        MoveToEx(dc,tx[start]+Cos(a)/2,ty[start]+Sin(a)/2,0);
        a=ta[goal]; x=tx[goal]+Cos(a+7)/2; y=ty[goal]+Sin(a+7)/2;
        LineTo(dc,x,y); Ellipse(dc,x-2,y-2,x+2,y+2);
        SelectObject(dc,old); DeleteObject(pen);
    }
}

/*┌─────────────────────────┐
 │ピースを lv の数だけ書く。指定したリンクを強調する│
 └─────────────────────────┘*/
void DrawRects(int lv,int link)
{
    int i; HDC dc=GetDC(SubWnd); RECT r; char buf[100];

    wsprintf(buf,"PID=%d : Divider=%d",PatternID,Divider);
    SetWindowText(SubWnd,buf); GetClientRect(SubWnd,&r);
    FillRect(dc,&r,(HBRUSH)(COLOR_WINDOW+1));
    for (i=0;i<lv;i++) DrawOneRect(link,dc,i);
    ReleaseDC(SubWnd,dc);
}

/*┌──────┐
 │内周線を描く│
 └──────┘*/
void DrawInnerLines(void)
{
    HDC dc=GetDC(SubWnd); int i,a=LineStartAngle;
    int x=START_X+Cos(60),y=START_Y+Sin(60),xx=x,yy=y;
    HPEN pen=CreatePen(PS_SOLID,0,RGB(255,0,0));
    HPEN old=(HPEN)SelectObject(dc,pen);

    MoveToEx(dc,x,y,0);
    for (i=1;i<LineLength;i++)
    { x+=Cos(a); y+=Sin(a); a+=LineAngle[i]-180; LineTo(dc,x,y); }
    LineTo(dc,xx,yy); SelectObject(dc,old);
    ReleaseDC(SubWnd,dc); DeleteObject(pen);
}

/*┌───────────────────────────┐
 │隙間なく詰められた場合、リンクが正しいかどうか表示する│
 └───────────────────────────┘*/
void CheckPattern(void) {
    int i,ans; char buf[100]; static int AlwaysIgnore;

    if (AlwaysIgnore) return;
    DrawRects(15,16); DrawInnerLines();
    wsprintf(buf,"PatternID=%d のチェックをしますか",PatternID);
    ans=MessageBox(ConWnd,buf,"",MB_YESNOCANCEL|MB_SYSTEMMODAL);
    if (ans==IDCANCEL) AlwaysIgnore=1;
    if (ans==IDYES) for (i=0;i<=15;i++)
    { DrawRects(15,i); DrawInnerLines(); Sleep(200); }
}

/*┌─────────────────────┐
 │飛行機が矛盾なく置けた場合に結果を表示する│
 └─────────────────────┘*/
void DrawResult(void)
{
    char buf[100]; int ans;
    static int prev=-1,PrintResult,AlwaysIgnore;

    if (AlwaysIgnore||(PrintResult==0&&PatternID==prev))
    { prev=PatternID; return; }
    DrawRects(15,16); DrawInnerLines();
    if (PatternID==prev) { Sleep(750); return; }
    wsprintf(buf,"PatternID=%d の結果を見ますか",PatternID);
    ans=MessageBox(ConWnd,buf,"",MB_YESNOCANCEL|MB_SYSTEMMODAL);
    prev=PatternID;
    if (ans==IDYES)    PrintResult=1;
    if (ans==IDNO)     PrintResult=0;
    if (ans==IDCANCEL) AlwaysIgnore=1;
}
 

/*┌────────────────┐
 │外周にあるピースの位置を計算する│
 └────────────────┘*/
void CalcOuterLocation(void)
{
    int i,j,prev=0,x=START_X,y=START_Y,a=0,r=0;

    for (i=0;i<LineLevel;i++) {
        for (j=0;j<Pos[i]-prev;j++)
        { x+=Cos(a); y+=Sin(a); a+=30; }
        if (i>=LineLevel-1||Pos[i+1]==Pos[i])
             { r-=Angle[Type[i]][0]; RectAngle[i]=a+r; }
        else { r=150-Angle[Type[i]][0]; RectAngle[i]=a; }
        RectPosX[i]=x; RectPosY[i]=y; prev=Pos[i]; 
    }
}

/*┌───────────────────────────┐
 │内周線の情報を使ってピースの位置を計算する。iは辺番号 │
 └───────────────────────────┘*/
void CalcInnerLocation(int lv,int i)
{
    int k=LineFrom[i],a=RectAngle[k],l=LineIndex[i];
    int g=Angle[Type[k]][Dir[k]];

    RectPosX[lv]=RectPosX[k]+Cos(a+g)+(l==1?Cos(a):0);
    RectPosY[lv]=RectPosY[k]+Sin(a+g)+(l==1?Sin(a):0);
    RectAngle[lv]=a+(l==1?g-180:0);
}

/*┌───────────────────────┐
 │内周線に接しない例外的なピースの位置を計算する│
 └───────────────────────┘*/
void SpecialLocation(int lv)
{
    RectPosX[lv]=RectPosX[0];
    RectPosY[lv]=RectPosY[0]+Sin(60)*2;
    RectAngle[lv]=0;
}

/*┌─────────┐
 │ウィンドウの初期化│
 └─────────┘*/
void InitWindow(void)
{
    static WNDCLASSEX wcex; HINSTANCE hinst=GetModuleHandle(0);

    wcex.cbSize=sizeof wcex; wcex.lpfnWndProc=DefWindowProc;
    wcex.hInstance=hinst; wcex.hCursor=LoadCursor(0,IDC_ARROW);
    wcex.hbrBackground=(HBRUSH)(COLOR_WINDOW+1);
    wcex.lpszClassName="GOOD"; RegisterClassEx(&wcex);
    SetWindowPos(ConWnd,0,WINDOW_SIZE+2,0,0,0,
        SWP_NOZORDER|SWP_NOSIZE);
    SubWnd=CreateWindowEx(0,"GOOD","",WS_OVERLAPPEDWINDOW,
        0,0,WINDOW_SIZE,WINDOW_SIZE,ConWnd,0,hinst,0);
    ShowWindow(SubWnd,SW_SHOW); UpdateWindow(SubWnd);
    SetForegroundWindow(ConWnd);
}

#endif /* end of #ifdef GRAPHICS */

/*┌────────────────┐
 │何本解か調べてカウンターを進める│
 └────────────────┘*/
void CountUpLines(void)
{
    int cnt=0,i,j,k,d; char visited[15];

    memset(visited,0,sizeof visited);
    for (i=0;i<15;i++) if (visited[i]==0) {
        cnt++;
        for (d=1;d<=2;d++) {
            j=i;
            do {
                visited[j]=1;
                for (k=0;Arrange[j][k]!=d;k++) ;
                j=Link[j][k];
            } while (j!=15&&visited[j]==0);
        }
    }
    Count[cnt>=7?6:cnt]++;
}

/*┌─────────────────────┐
 │再起呼び出しをしながら、飛行機を置いてゆく│
 └─────────────────────┘*/
void SearchPlane(int lv)
{
    int i,j,k,a,c,l,t=Type[lv],d=Dir[lv],n=(t?6:3),inc=(t?2:1);
    static char used[3][6],tbl[6][4]=
    {{1,0,2,0},{1,2,0,0},{1,0,0,2},{2,1,0,0},{0,2,0,1},{2,0,0,1}};

    if (lv==15) {
        CountUpLines();
#ifdef GRAPHICS
        if (SubWnd) DrawResult();
#endif
        return;
    }
    for (i=0;i<n;i++) if (used[t][i]==0) {
        used[t][i]=1;
        for (j=0;j<4;j+=inc) {
            for (k=0;k<4;k++) {
                a=Arrange[lv][k]=tbl[i][(j+k+d)&3]; l=Link[lv][k];
                if (l<lv) {
                    c=Arrange[l][Back[lv][k]];
                    if (a==0)      { if (c!=0) break; }
                    else if (a==1) { if (c!=2) break; }
                    else           { if (c!=1) break; }
                }
            }
            if (k==4) SearchPlane(lv+1);
        }
        used[t][i]=0;
    }
}

/*┌─────────────────────────┐
 │飛行機を置く。置き終わったら、カウンターを計算する│
 └─────────────────────────┘*/
void SolvePlane(void)
{
    int i,sum=0;

    memset(Arrange,0,sizeof Arrange); memset(Count,0,sizeof Count);
#ifdef GRAPHICS
    if (SubWnd) CheckPattern();
#endif
    SearchPlane(0); printf("PatternID=%2d ",PatternID);
    for (i=1;i<=5;i++) printf(" (%d:%2d) ",i,Count[i]);
    for (i=0;i<7;i++) { Total[i]+=Count[i]/Divider; sum+=Count[i]; }
    printf(" sum=%2d  Divider=%d\n",sum,Divider);
}

/*┌─────────────────┐
 │内周線の内側のピース置き方のデータ│
 └─────────────────┘*/
/*
 先頭はType[]、次は Dir[]。'S'は内周線とリンクさせる。
 'A'は次のピースとリンクさせる。'B'は次の次のピースとリンクさせる。
 ','は次のピースに処理を移す。'L'は例外。'!'は終了処理。
 ':'は10を一文字で表したもの。';'は11を一文字で表したもの。
*/
char t1[]="11S00S11A23S37,21S02S13A23,10S04S15S26!",
 t2[]="11S00S11A23,21S02S13A23,10S04S15A23,20S06S17A23!",
 t3[]="11S00S11S39A23,21S02S13A23,11S04S15A23,20S06S17S28!",
 t6[]="11S00S11S37A23,21S02S13A23,11S04S15S26!",
 t8[]="11S00S11B22A32,20S06S17A31,21S05A33,10S02S13S24!"
      "21S00S37A22B13,11S05S16A32,20S01A13,10S02S13S24!",
 t1417[]="11S00S11A23S37,00S02S13A23,20S04S15S26!",
 t1518[]="11S00S11A23S35,00S02S13S24!",
 t1619[]="11S00S11A23B33,00S02S13S24,21S05S16S27!",
 t20[]="11S00S11A31B20,21S07S36A23,21A13B22L,11S02S13A23,20S04S15!"
       "21S00S37A13B21,20S01B13A22,10S06B32,11S02S13A23,20S04S15!",
 t21[]="11S37S00S11A22,21A33S05S16,11S02S13S24!",
 t2627[]="21S37S00S11A21,00S06A23B32,10S02S13A23,20S04S15!"
         "21S37S00S11A23,21S02A13B22,00S03S14A23,10S05S16!",
 t28[]="21S39S00S11A23,21S02A13B23,00S03S14S25,00S06S17S28!",
 t2931[]="21S37S00S11,00S02S13A23B32,20S04S15A23,10S06A12!"
         "21S37S00S11A23,21S02A13B22,10S03S14A23,00S05S16!",
 t34354041[]="00S37S00S11A23,10S02S13A23,10S04S15S26!",
 t3642[]="00S00S11A23,10S02S13A23,20S04S15A23!"
         "11S35S00A13,20S01S12A23,00S03S14A22!",
 t3743[]="00S39S00S11A23,10S02S13S24,00S35S06S17S28!",
 t383944[]="00S00S11A23,10S02S13S24,10S06S17A23S35!",
 t46[]="00S37S00S11A23,20S02S13A23,00S04S15S26!",
 t47[]="00S3;S00S11S22,00S33S04S15S26,00S37S08S19S2:!",
 t4849[]="10S00S11A23,10S02S13A23,10S04S15A23!"
         "10S01S12A23,10S03S14A23,10S05S10A23!";

char*InnerData[]={
 "",t1,t2,t3,"","",t6,"",t8,"","","","","",t1417,t1518,t1619,t1417,
 t1518,t1619,t20,t21,"","","","",t2627,t2627,t28,t2931,"",t2931,"",
 "",t34354041,t34354041,t3642,t3743,t383944,t383944,t34354041,
 t34354041,t3642,t3743,t383944,"",t46,t47,t4849,t4849};

/*┌────────────────────┐
 │カウンターを割る値Dividerを決めるデータ │
 └────────────────────┘
 通常は1。左右対称なら2。120度回転なら3。
 左右対称でかつ120度回転なら6。*/
char DivData[]="1112111111112121111111111111112111112263311";

/*┌──────────────────────┐
 │上のデータに従って、内側にピースを置いてゆく│
 └──────────────────────┘*/
void FillInnerRects(void)
{
    char*p; int lv=LineLevel,command,i,j,n,m; static int id;

    for (p=InnerData[id++];*p;) {
        Type[lv]=(byte)(*p++-'0'); Dir[lv]=(byte)(*p++-'0');
        for (;;) {
            switch (command=*p++) {
            case'S':i=*p++-'0'; j=*p++-'0';
                    n=LineFrom[j]; m=LineIndex[j];
                    Link[n][m]=(byte)lv; Back[n][m]=(byte)i;
                    Link[lv][i]=(byte)n; Back[lv][i]=(byte)m;
#ifdef GRAPHICS
                    if (SubWnd&&i==0) CalcInnerLocation(lv,j);
#endif
                    break;
            case'A':
            case'B':i=*p++-'0'; j=*p++-'0';
                    n=(lv=='B'-command+13?LineLevel:lv+command-'@');
                    Link[n][j]=(byte)lv; Back[n][j]=(byte)i;
                    Link[lv][i]=(byte)n; Back[lv][i]=(byte)j;
                    break;
#ifdef GRAPHICS
            case'L':if (SubWnd) SpecialLocation(lv); break;
#endif
            }
            if (command==',') { lv++; break; }
            if (command=='!') {
                Divider=DivData[PatternID]-'0'; SolvePlane();
                lv=LineLevel; PatternID++; break;
            }
        }
    }
}

/*┌───────────────────┐
 │与えられた外周の置き方からリンクを張る│
 └───────────────────┘*/
void CalcLinkAndIndex(void)
{
    int i,cur=1,z=LineLevel-1,k=12-Pos[z],d,s;

#ifdef GRAPHICS
    if (SubWnd) CalcOuterLocation();
#endif
    memset(LineAngle,0,sizeof LineAngle); LineAngle[0]=120;
    LineAngle[1]=60; LineLength=0; memset(Link,16,sizeof Link);
    Link[0][0]=15; LineFrom[0]=0; LineIndex[0]=2;
    Link[0][3]=(char)z; Back[0][3]=(byte)k;
    Link[z][k]=0; Back[z][k]=3;
    for (i=1;i<LineLevel;i++) {
        d=Pos[i]-Pos[i-1]; Link[i-1][d]=(byte)i; Back[i-1][d]=3;
        Link[i][3]=(byte)(i-1); Back[i][3]=(byte)d;
        if (i<LineLevel-1&&Pos[i+1]-Pos[i]==2) {
            LineAngle[cur]+=Angle[Type[i]][Dir[i]^1];
            Link[i][0]=Link[i][1]=15;
        } else {
            s=((i==z?12:Pos[i+1])==Pos[i]);
            LineFrom[cur]=(byte)i; LineIndex[cur]=2;
            if ((LineAngle[cur++]+=Angle[Type[i]][Dir[i]^1])==360) {
                d=Pos[i-1]-Pos[i-2]+1; Link[i-2][d]=(byte)i;
                Back[i-2][d]=2; Link[i][2]=(byte)(i-2);
                Back[i][2]=(byte)d; LineAngle[cur-1]=0; cur-=2;
                if (i==2) LineStartAngle=Angle[Type[i]][Dir[i]];
            }
            if (s) {
                LineFrom[cur]=(byte)i; LineIndex[cur]=1;
                LineAngle[cur++]+=Angle[Type[i]][Dir[i]];
            } else Link[i][0]=15;
            if (i==z) { LineLength=cur; cur=0; }
            LineAngle[cur]+=Angle[Type[i]][Dir[i]^s];
        }
    }
}

/*┌─────────────────────┐
 │外周の置き方をコード化して、ログと比較する│
 └─────────────────────┘*/
int FindSame(byte*Pos,byte*Type)
{
    int i,k=0,p=0,b=1,x=0,q,next;

    for (i=0;i<LineLevel;i++) {
        x+=Type[i]<<k; next=(i==LineLevel-1?13:Pos[i+1]);
        if (p==12) b<<=2;
        if (next!=p) {
            if (p==12) OuterCode[0]=(byte)(x+b);
            else OuterCode[p]=(byte)x;
            if (p<11&&next-p>=2) OuterCode[p+1]=3;
            p=next; x=0; k=0;
        } else k+=2;
    }
    for (k=0;k<LogSize;k++) {
        for (p=0;p<12;p++) {
            q=p;
            for (i=0;i<12;i++) {
                if (Log[k][i]!=OuterCode[q]) break;
                if (q==11) q=0; else q++;
            }
            if (i==12) break;
        }
        if (p<12) break;
    }
    return k<LogSize;
}

/*┌─────────────────────┐
 │FindSame()を利用して、回転と鏡像を排除する│
 └─────────────────────┘*/
int CheckRotationAndSymmetry(void)
{
    int i,j,k=0,p; byte Pos2[15],Type2[15];

    if (FindSame(Pos,Type)) return 0;
    for (j=i=0;i<LineLevel;i++) {
        if (++k==LineLevel) k=0;
        if ((p=Pos[k])<2) Pos2[j]=(byte)( 1-p);
        else              Pos2[j]=(byte)(13-p);
        Type2[j]=Type[i];
        if (j==0) j=LineLevel-1; else j--;
    }
    for (i=LineLevel-1;Pos2[i]==0;i--) Pos2[i]=12;
    if (FindSame(Pos2,Type2)) return 0;
    for (i=0;i<12;i++) Log[LogSize][i]=OuterCode[i];
    LogSize++; return 1;
}

/*┌─────────────────┐
 │外周にピースを置き終わった時の処理│
 └─────────────────┘*/
void AfterOuterRects(int lv)
{
    LineLevel=lv;
    if (CheckRotationAndSymmetry())
    { CalcLinkAndIndex(); FillInnerRects(); }
}

/*┌────────────────────────┐
 │再起呼び出しをしながら、外周にピースを置いてゆく│
 └────────────────────────┘*/
void SearchOuterRects(int lv,int pos)
{
    int i,j,k,l,n; static int over[12],ang[12],used[3]={3,6,6};

    Pos[lv]=(byte)pos;
    if (lv==0) {
        /* 最初のは60度120度のピースに固定 */
        used[1]--; Type[0]=1; Dir[0]=0; ang[0]=60; ang[1]=120;
        SearchOuterRects(1,1); used[1]--; return;
    }
    if (pos>=12) n=pos-12; else n=pos;
    for (i=0;i<3;i++) if (used[i]) {
        used[i]--; Type[lv]=(byte)i;
        for (j=0;j<(i==1?2:1);j++) {
            if (over[lv-1]+Angle[i][j^1]>360) continue;
            Dir[lv]=(byte)j; ang[n]+=Angle[i][j];
            if (ang[n]<150) SearchOuterRects(lv+1,pos);
            else if (ang[n]==150) {
                if (pos==12) AfterOuterRects(lv+1);
                else {
                    if (n==11) k=0; else k=n+1;
                    ang[k]+=Angle[i][j^1];
                    if (ang[k]<150) SearchOuterRects(lv+1,pos+1);
                    else if (ang[k]==150) {
                        if (pos==11) AfterOuterRects(lv+1);
                        else {
                            over[lv]=150+Angle[Type[lv-1]]
                                       [Dir[lv-1]^(Pos[lv-1]==pos)];
                            if (k==11) l=0; else l=k+1;
                            ang[l]+=Angle[i][j];
                            SearchOuterRects(lv+1,pos+2);
                            ang[l]-=Angle[i][j]; over[lv]=0;
                        }
                    }
                    ang[k]-=Angle[i][j^1];
                }
            }
            ang[n]-=Angle[i][j];
        }
        used[i]++;
    }
}

/*┌────────────────────┐
 │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(void)
{
    double StartTime; int i,sum=0;
#ifdef GRAPHICS

    ConWnd=GetForegroundWindow();
    if (MessageBox(ConWnd,"GUIを使いますか","",MB_YESNO)==IDYES)
        InitWindow();
#endif
    StartTime=clock(); SearchOuterRects(0,0);
    for (i=1;i<=5;i++)
    { printf(" %d本解:%d  ",i,Total[i]); sum+=Total[i]; }
    printf("合計:%d\n",sum);
#ifdef GRAPHICS
    if (SubWnd) SendMessage(SubWnd,WM_CLOSE,0,0);
#endif
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}