/*
2004/12 ダブル・スクエア
coded by Isaku WADA
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │ 実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Visual Studio C++ 6.0     │0.00578 秒│ 49512 byte │
 │Visual Studio C++ 2003     │0.00593 秒│ 49152 byte │
 │Borland C++ 5.5.1 for Win32 │0.00829 秒│ 55296 byte │
 │gcc-2.953(djgpp)      │0.00495 秒│ 111477 byte │
 │gcc-3.3.3(cygwin)      │0.00500 秒│ 19956 byte │
 │LSI C-86 Ver 3.30 試食版  │0.01650 秒│ 15238 byte │
 │Turbo C Ver 1.5(small model)│0.01810 秒│ 12770 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP     │
 └──────────────┴─────────────┘

 ┌─────────────────────────────┐
 │ Fig.1にある寸法の長方形や正方形を厚さ1の板から切り出し│
 │、2片ずつ接着してA〜Hの8ピース用意する。Fig.1は、サイ│
 │ズが分かるように1×1の方眼の上に描いてある。たとえばピー│
 │スAは、3×3×1と2×2×1の2片からなり、Fig.2(省略│
 │)のような形状をしている。この8ピースを、内寸8×8、深さ│
 │2の箱(Fig.3)(省略)にぴったりと詰めることを考える。全│
 │体の回転・裏返しは別の解とはしないとして、何通りの解がある│
 │だろうか。そのときの詰め方も図示していただきたい。    │
 │                             │
 │Fig.1 8ピースの形状                   │
 │                             │
 │ ┏━┳┯┓  ┏━━━┓ ┏━┓     ┏━━━┓  │
 │ ┃A┃│┃  ┃B  ┃ ┃┌╋━┓ ┏━╋━━┓┃  │
 │ ┃ ┗╋┛ ┏╋┐  ┃ ┗╋┛C┃ ┃ │D ┃┃  │
 │ ┗━━┛  ┃┗╋━━┛  ┗━━┛ ┗━┷━━┻┛  │
 │       ┗━┛                   │
 │┏━┓                          │
 │┃┌╋━━┓  ┏━┓   ┏━┓   ┏━━┓     │
 │┃│┃E ┃ ┏╋─╋━┓ ┠─╋━┓ ┃ ┌╋━━┓  │
 │┃│┃  ┃ ┃┃F┃ ┃ ┃G┃ ┃ ┃ │┃H ┃  │
 │┗┷┻━━┛ ┗┻━┻━┛ ┗━┻━┛ ┗━┷┻━━┛  │
 └─────────────────────────────┘
 ┌─────────────────┐
 │解答:1通り           │
 │HHAAEEEE AAAEEBBB│
 │HHAAEEEE AAAEEBBB│
 │HHCCEEEE AAAEEBBB│
 │HHCCBBFF HHHEEBBB│
 │GGCCBBFF HHHCCFFF│
 │GGDDDDFF HHHCCFFF│
 │GGDDDDFF GGGDDDDD│
 │GGDDDDFF GGGDDDDD│
 └─────────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ 各ピースの上下の片の面積が様々なので、どのピースを表にし│
 │て置くかは、ある程度限られてきます。裏返しは別の解としない│
 │ので、Aのピースは表に限定します。すると、1階2階それぞれ│
 │の面積が64になる、他のピースの表裏の組み合わせは8通りし│
 │かありません。8ピース全ての表裏を調べると、組み合わせが │
 │256通りあるので、8通りに限定することにより、かなり高速│
 │化しました。この8通りの表裏の表を求めるのに8重forループを│
 │使う代わりに、再帰呼び出しするFaceSub()関数を使いました。 │
 │forループを使うとピースの数を変更した場合のソースコードの │
 │変更が面倒だからです。また、Aのピースの向きを固定し、回転│
 │と鏡像を排除しました。                  │
 │ 高速化のために、配列OfsX,OfsY,OfsZを用意しました。これら│
 │は、各8ピースの、表裏×4方向の8通りについて、1階の片の│
 │一番左上の部分の座標からの、残りの部分の相対座標を記録しま│
 │す。OfsZは、1階なら0、2階なら1になります。      │
 │ 盤はMapという3次元配列で表します。壁の太さは5です。空 │
 │白を表すEMPTYという定数は127にしました。理由は−1にす │
 │るとLSI-C 86のようにchar型が、デフォルトで符号無しの場合 │
 │に、正しく動作しないからです。またEMPTYを0にすると、ピー │
 │スAを表す値が1となりプログラムが少々複雑になるからです。│
 │ 探索は、盤の1階の左上から右下に向かって、再帰呼び出しを│
 │しながら、各ピースを置いてゆきます。1回の関数呼び出しの中│
 │で、ピースと方向を選びます。表裏は、前述の8通りの表裏の表│
 │で指定されたものにします。選ばれたピースを選ばれた方向で、│
 │左上に置きます。そして、OfsX,OfsY,OfsZを調べてゆき、既に他│
 │のピースが置かれていたり、壁だったりしたらスキップします。│
 │再帰呼び出しの深さが9になり、全てのピースを隙間なく置くこ│
 │とができたら、表示します。                │
 │                             │
 │・感想                          │
 │                             │
 │ OfsX,OfsY,OfsZの必要性と仕様は早くに決まったのですが、そ│
 │れをどうやって求めるかの方法を思いつくのに時間がかかりまし│
 │た。そもそも、ピースの形状を表す元データの形式を決めるのに│
 │時間がかかってます。また、OfsX,OfsY,OfsZが正しく設定されて│
 │いるかどうか確認するプログラムも小さくはありませんでした。│
 └─────────────────────────────┘*/

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

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define P        8       /* ピースの数 */
#define N        8       /* 大きな箱の内寸 */
#define SHAPE_W  6       /* Shape[][]でのピースの最大幅 */
#define SHAPE_H  4       /* Shape[][]でのピースの最大の高さ */
#define TBL_SIZE 8       /* 表裏の表の大きさ */
#define MAX_BOX 22       /* ピースの持つ箱の最大数 */
#define MAX_LOG  1       /* 解のログの大きさ */
#define EMPTY  127       /* Mapでピースが置かれてないことの印 */
#define WALL (SHAPE_W-1) /* Mapの壁の太さ */

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char Shape[SHAPE_H][SHAPE_W*P+1]= /* ピースの形状 */
{"1132   2222 22      1111 22                     ",
 "1132   2222 2311  223331 23111  22   22   222   ",
 "111   13222  111  223331 23111 13311 3311 223111",
 "      11                 23111 13311 3311 223111"};

int  Box1[P];              /* ピースの下の箱の数 */
int  Box2[P];              /* ピースの上の箱の数 */
int  TotalBox[P];          /* ピースの持つ箱の数 */
int  FaceOrBack[P];        /* ピースが表か裏かを記録する */
int  FaceTbl[TBL_SIZE][P]; /* BoxSumが64になる表裏のテーブル */
int  FaceSize;             /* FaceTbl[][] の大きさ */
int  OfsX[P][8][MAX_BOX];  /* 各ピース、各回転の、各箱の相対位置 */
int  OfsY[P][8][MAX_BOX];
int  OfsZ[P][8][MAX_BOX];
char Work[2][SHAPE_W][SHAPE_W];  /* Ofs? を作る時の作業変数 */
char Map[2][N+WALL*2][N+WALL*2]; /* 箱詰めを行う時の盤の状態 */
char Flags[P];                   /* ピースを既に使ったかどうか */
int  PrintMode;

/*┌──────────────────────────────┐
 │ピースを表裏に置いてみて一階の箱の数がN*Nになったら記録する │
 └──────────────────────────────┘*/
void FaceSub(int lv,int sum)
{
    int p;

    if (lv==P) {
        if (sum==N*N) {
            if (FaceSize>=TBL_SIZE) {
                 printf("TBL_SIZE が小さすぎます\n");
                 exit(EXIT_FAILURE);
            }
            for (p=0;p<P;p++) FaceTbl[FaceSize][p]=FaceOrBack[p];
            FaceSize++;
        }
        return;
    }
    FaceOrBack[lv]=1; FaceSub(lv+1,sum+Box1[lv]);
    FaceOrBack[lv]=2; FaceSub(lv+1,sum+Box2[lv]);
}

/*┌─────────────────────────┐
 │各ピースの箱の数を調べて、表裏のテーブルを作成する│
 └─────────────────────────┘*/
void CalcBoxAndFace(void)
{
    int p,q,x,y,box1,box2;

    for (p=0;p<P;p++) {
        box1=box2=0; q=p*SHAPE_W;
        for (y=0;y<SHAPE_H;y++) for (x=0;x<SHAPE_W;x++)
          switch (Shape[y][x+q]) {
          case'1':box1++; break;
          case'2':box2++; break;
          case'3':box1++; box2++; break;
          }
         Box1[p]=box1; Box2[p]=box2; TotalBox[p]=box1+box2;
         if (TotalBox[p]>MAX_BOX) {
             printf("MAX_BOX が小さすぎます\n");
             exit(EXIT_FAILURE);
         }
    }
    FaceOrBack[0]=1; FaceSize=0; FaceSub(1,Box1[0]);
}

/*┌────────────────────┐
 │ピースが表だった場合の作業変数を作成する│
 └────────────────────┘*/
void ShapeToWork1(int p)
{
    int x,y,q=p*SHAPE_W;

    memset(Work,0,sizeof Work);
    for (y=0;y<SHAPE_H;y++) for (x=0;x<SHAPE_W;x++)
      switch (Shape[y][x+q]) {
      case'1':Work[0][y][x]=1; break;
      case'2':Work[1][y][x]=1; break;
      case'3':Work[0][y][x]=1; Work[1][y][x]=1; break;
      }
}

/*┌────────────────────┐
 │ピースが裏だった場合の作業変数を作成する│
 └────────────────────┘*/
void ShapeToWork2(int p)
{
    int x,y,q=(p+1)*SHAPE_W-1;

    memset(Work,0,sizeof Work);
    for (y=0;y<SHAPE_H;y++) for (x=0;x<SHAPE_W;x++)
      switch (Shape[y][q-x]) {
      case'1':Work[1][y][x]=1; break;
      case'2':Work[0][y][x]=1; break;
      case'3':Work[0][y][x]=1; Work[1][y][x]=1; break;
      }
}

/*┌───────────────┐
 │作業変数を右に90度回転させる│
 └───────────────┘*/
void RotateWork(void)
{
    static char Buf[2][SHAPE_W][SHAPE_W]; int x,y,z;

    memcpy(Buf,Work,sizeof Buf);
    for (z=0;z<2;z++)
     for (y=0;y<SHAPE_W;y++) for (x=0;x<SHAPE_W;x++)
         Work[z][x][SHAPE_W-1-y]=Buf[z][y][x];
}

/*┌──────────────────────────┐
 │各ピース、各回転の、各箱の相対位置を設定する時に使う│
 └──────────────────────────┘*/
void RegistOfs(int p,int d)
{
    int x,y,k=0,flag=1,baseX=0,baseY=0;

    for (y=0;y<SHAPE_W;y++) for (x=0;x<SHAPE_W;x++)
     if (Work[0][y][x]) {
        if (flag) { flag=0; baseX=x; baseY=y; }
        OfsX[p][d][k]=x-baseX; OfsY[p][d][k]=y-baseY;
        OfsZ[p][d][k]=0; k++;
     }
    for (y=0;y<SHAPE_W;y++) for (x=0;x<SHAPE_W;x++)
     if (Work[1][y][x]) {
        OfsX[p][d][k]=x-baseX; OfsY[p][d][k]=y-baseY;
        OfsZ[p][d][k]=1; k++;
     }
}

/*┌──────────────────────┐
 │各ピース、各回転の、各箱の相対位置を設定する│
 └──────────────────────┘*/
void CalcOfs(void)
{
    int p;

    for (p=0;p<P;p++) {
        ShapeToWork1(p); RegistOfs(p,0);
        RotateWork();    RegistOfs(p,1);
        RotateWork();    RegistOfs(p,2);
        RotateWork();    RegistOfs(p,3);
        ShapeToWork2(p); RegistOfs(p,4);
        RotateWork();    RegistOfs(p,5);
        RotateWork();    RegistOfs(p,6);
        RotateWork();    RegistOfs(p,7);
    }
}

/*┌───────┐
 │履歴を表示する│
 └───────┘*/
void Print(void)
{
    int x,y; static char str[]="ABCDEFGH";

    if (PrintMode==0) return;
    for (y=0;y<N;y++) {
        for (x=0;x<N;x++)
            printf("%.2s",str+Map[1][y+WALL][x+WALL]*2);
        printf(" ");
        for (x=0;x<N;x++)
            printf("%.2s",str+Map[0][y+WALL][x+WALL]*2);
        printf("\n");
    }
    printf("\n");
}

/*┌────────────────────────────┐
 │解の探索をする。引数 lv は再帰の深さ、face は表裏の配列 │
 └────────────────────────────┘*/
void Recurr(int lv,int face[])
{
    int x=0,y,p,d,b,end,*ox,*oy,*oz;

    if (lv==P) { Print(); return; } /* 解を得た */

    for (p=0;p<P;p++) if (Flags[p]==0) {

        Flags[p]=1;

        /* 表裏のテーブルから d の範囲を絞る */
        if (p==0)            { d=0; end=1; }
        else if (face[p]==1) { d=0; end=4; }
        else                 { d=4; end=8; }
        for (;d<end;d++) {

            ox=OfsX[p][d]; oy=OfsY[p][d]; oz=OfsZ[p][d];

            /* 一階の一番左上の空白を探索して(x,y)に設定する */
            for (y=WALL;y<N+WALL;y++) {
                for (x=WALL;x<N+WALL;x++)
                     if (Map[0][y][x]==EMPTY) break;
                if (x<N+WALL) break;
            }

            /* 新しいピースが置けるかどうか確認する */
            for (b=TotalBox[p]-1;b>0;b--)
             if (Map[oz[b]][y+oy[b]][x+ox[b]]!=EMPTY) break;

            /* 置くことができた場合の処理 */
            if (b==0) {

                /* 印をつける */
                for (b=TotalBox[p]-1;b>=0;b--)
                    Map[oz[b]][y+oy[b]][x+ox[b]]=(char)p;

                Recurr(lv+1,face); /* 再帰呼び出し */

                /* 印を外して、元に戻す */
                for (b=TotalBox[p]-1;b>=0;b--)
                    Map[oz[b]][y+oy[b]][x+ox[b]]=EMPTY;
            }
        }
        Flags[p]=0;
    }
}

/*┌──────────────────────────┐
 │パズルを解く。引数 print が0以外なら履歴を表示する │
 └──────────────────────────┘*/
void Solve(int print)
{
    int x,y,z;

    PrintMode=print; CalcBoxAndFace(); CalcOfs();
    for (z=0;z<2;z++) for (y=0;y<N;y++) for (x=0;x<N;x++)
        Map[z][y+WALL][x+WALL]=EMPTY;
    for (y=0;y<FaceSize;y++) Recurr(0,FaceTbl[y]);
}

/*┌────────────────────┐
 │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(i==0);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}