/*
2003/12 ダブりペントミノ
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ Fig.4のような7種類のピースがある。この7枚をFig.5の正│
 │方形に詰めたい。                     │
 │(1)正方形にある9か所の穴には置けない          │
 │(2)ピースは回転したり裏返したりしてかまわない      │
 │(3)あるピースだけ2枚を使い,合計8枚ですき間なく詰める │
 │ さて,2枚使うのはどのピースだろうか。そのときの詰め方の│
 │1つを添えてお答えいただきたい。             │
 │                             │
 │Fig.4 7種類のピース    Fig.5 ピースを詰める正方形│
 │□                     □□□□□□□│
 │□ □  □                □■□■□■□│
 │□ □  □□ □ □□  □       □□□□□□□│
 │□ □  □ □□□ □  □   □ □ □■□■□■□│
 │□ □□ □  □  □□ □□□ □□□ □□□□□□□│
 │1 2  3  4  5   6   7  □■□■□■□│
 │                      □□□□□□□│
 └─────────────────────────────┘
 ┌──────────┐
 │解答:2番目のピース│
 │          │
 │2222553   │
 │2■1■5■3   │
 │7715533   │
 │7■1■4■3   │
 │7714446   │
 │2■1■4■6   │
 │2222666   │
 └──────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ まず、7種類のピース全てについて、回転・裏返しのデータを│
 │作ります。作り方は、3回回転し、裏返し、3回回転を行って8│
 │つのパターンを生成します。そして、それぞれのパターンについ│
 │て、一番上の正方形のうち、左のものの座標を(0,0)として、残│
 │りの4つの正方形の相対位置を求めます。次に、その相対位置の│
 │パターンの中から、互いに異なるパターンを選んで登録します。│
 │ピース1は2種類、ピース2・3は8種類、ピース4は1種類、│
 │ピース5・6・7は4種類のパターンがありました。     │
 │ プログラムは、ピース1からピース7の中から、順に一つを選│
 │んで、それを2枚使えるようにして探索します。それぞれの探索│
 │の前準備として、2枚置くピースのカウンターは2、それ以外の│
 │ピースのカウンターは1にします。また、7×7の盤を用意し、│
 │穴には8を記録し、残りは空白を表す0にしておきます。   │
 │ メインの探索は再帰呼び出しをする関数で行います。関数では│
 │まず、盤の中で一番上の空白のうち左のものを選びます。次に、│
 │カウンターが1以上のピース全てについて繰り返すループと、回│
 │転裏返し全てについて繰り返すループの2重forループに入り│
 │ます。選んだ空白に、前に求めておいた相対位置のデータを使っ│
 │て、ピースが置けるかどうか調べます。具体的には相対位置で求│
 │めた位置が盤の外だったり、または、空白でないものがあればス│
 │キップします。逆に全て空白なら、その位置の盤にピースの番号│
 │を記録し、対応するピースのカウンターを減らして、再帰呼び出│
 │しします。8枚全てを詰めることができたら、盤を表示して終了│
 │します。                         │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 回転と裏返しのデータを作成する部分で苦労しました。盤に穴│
 │が空いているため、探索が狭くなり、予想以上に高速になり、驚│
 │きました。                        │
 └─────────────────────────────┘
 ┌──────────────┬──────┬───────┐
 │コンパイラ         │実行時間  │ファイルサイズ│
 ├──────────────┼──────┼───────┤
 │Microsoft Visual C++ 6.0  │0.0005781 秒│ 36864 byte │
 │Microsoft Visual C++ 2003  │0.0006078 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.0008922 秒│ 54784 byte │
 │gcc-2.953(djgpp)      │0.0007363 秒│ 110135 byte │
 │gcc-2.953(cygwin)      │0.0007250 秒│ 20846 byte │
 │LSI C-86 Ver 3.30 試食版  │0.0017350 秒│ 14672 byte │
 │Turbo C Ver 1.5(small model)│0.0017800 秒│ 12120 byte │
 ├──────────────┼──────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP     │
 └──────────────┴──────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
char*Shape[]= /* ピースの形 */
{"│□    │      │      │      │      │      │      │",
 "│□    │□    │□    │      │      │      │      │",
 "│□    │□    │□□  │  □  │□□  │□    │      │",
 "│□    │□    │□    │□□□│  □  │□    │□  □│",
 "│□    │□□  │□    │  □  │  □□│□□□│□□□│"};

char InitialMap[7][7]= /* 盤の初期状態 */
{{0,0,0,0,0,0,0},
 {0,8,0,8,0,8,0},
 {0,0,0,0,0,0,0},
 {0,8,0,8,0,8,0},
 {0,0,0,0,0,0,0},
 {0,8,0,8,0,8,0},
 {0,0,0,0,0,0,0}};

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char Map[7][7];    /* 作業用盤 */
int RotRev[8];     /* 回転と鏡像の数 */
int OfsX[8][8][4]; /* ピースの相対位置 */
int OfsY[8][8][4]; /* ピースの相対位置 */
int Counter[8];    /* あと、何回おけるか */

/*┌───────┐
 │結果を書き出す│
 └───────┘*/
void Print(void)
{
    int x,y; static int f;

    if (f) return; else f=1;
    for (y=0;y<7;y++) {
        for (x=0;x<7;x++)
            printf("%.2s","01234567■"+Map[y][x]*2);
        printf("\n");
    }
    printf("\n");
}

/*┌────────────────────┐
 │ピースpの回転と裏返しのデータを作成する│
 │RotRev,OfsX,OfsYに記録される      │
 └────────────────────┘*/
void MakeOfsTable(int p)
{
    int x,y,s=0,t=0,i,k,n=0,f,px[4],py[4]; static char log[8][5][5];

    for (y=0;y<5;y++) for (x=0;x<3;x++) /* 形を読み取る */
        log[0][y][x]=(char)(Shape[y][p*8-6+x*2]!=' ');

    for (i=0;i<3;i++) for (y=0;y<5;y++) /* 3回、回転 */
     for (x=0;x<5;x++) log[i+1][x][4-y]=log[i][y][x];

    for (y=0;y<5;y++) for (x=0;x<5;x++) /* 裏返し */
        log[4][4-y][x]=log[3][y][x];

    for (i=0;i<3;i++) for (y=0;y<5;y++) /* 3回、回転 */
     for (x=0;x<5;x++) log[i+5][x][4-y]=log[i+4][y][x];

    for (k=0;k<8;k++) {

        /* 相対位置の計算 */
        for (f=y=0;y<5;y++) for (x=0;x<5;x++) if (log[k][y][x]) {
            if (f==0) { s=x; t=y; f++; }
            else { px[f-1]=x-s; py[f-1]=y-t; f++; }
        }
        
        for (i=0;i<n;i++) { /* 過去の相対位置との比較 */
            for (f=0;f<4;f++)
             if (px[f]!=OfsX[p][i][f]||py[f]!=OfsY[p][i][f]) break;
            if (f==4) break;
        }
        if (i<n) continue; /* 同じものが既にあればスキップ */

        for (f=0;f<4;f++) /* 登録 */
        { OfsX[p][n][f]=px[f]; OfsY[p][n][f]=py[f]; }
        n++;
    }
    RotRev[p]=n;
}

/*┌─────────────────┐
 │再帰呼び出しをしながらパズルを解く│
 │解くことができたら1を返す    │
 └─────────────────┘*/
int Sub(int level)
{
    int p,d,x,y,i,s=0,t,px[4],py[4];

    if (level==8) { Print(); return 1; }

    /* 一番上の中で左にある空白の座標(s,t)を求める */
    for (t=0;t<7;t++) {
        for (s=0;s<7;s++) if (Map[t][s]==0) break;
        if (s<7) break;
    }
    for (p=1;p<8;p++) if (Counter[p]) /* ピースについて繰り返す */
     for (d=0;d<RotRev[p];d++) { /* 回転・裏返しについて繰り返す */

         for (i=0;i<4;i++) {
             /* ピースの位置を求める */
             x=px[i]=s+OfsX[p][d][i];
             y=py[i]=t+OfsY[p][d][i];
             /* 置けなければループを中断 */
             if (x<0||x>=7||y>=7||Map[y][x]) break;
         }
         if (i<4) continue; /* 置けなかったのでスキップ */

         /* ピースを盤に置いて再帰呼び出しする */
         for (i=0;i<4;i++) Map[py[i]][px[i]]=(char)p;
         Map[t][s]=(char)p; Counter[p]--;
         if (Sub(level+1)) return 1;

         /* 盤を元に戻す */
         Counter[p]++; Map[t][s]=0;
         for (i=0;i<4;i++) Map[py[i]][px[i]]=0;
     }
     return 0;
}

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

    memcpy(Map,InitialMap,sizeof Map);
    for (p=1;p<8;p++) MakeOfsTable(p);
    for (p=1;p<8;p++) {
        for (i=1;i<8;i++) Counter[i]=1;
        Counter[p]=2; /* 1つだけ2個置けるようにする */
        if (Sub(0)) return;
    }
}

/*┌────────────────────┐
 │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(); long i,num;

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