/**********************************************************************/
/*                                     Ｃmagazine 1995.12 電脳クラブ  */
/*   標    題   Ｆペントミノ                                          */
/*                                                                    */
/*   解    答   1 通り                                                */
/*                                                                    */
/*   使用機種   FMR-50NL (i486sx 25MHz)                               */
/*   Ｏ    Ｓ   MS-DOS Ver6.2                                         */
/*   コンパイラ LSI C-86 Ver3.30C(試食版)                             */
/*   実行時間   12.5 秒                                               */
/*                                                                    */
/**********************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

/* Ｆペントミノの回転裏返しの８パターン */
int  fpent[8][3][3] = {          /*    +-----+-----+       +--+--+--+ */
    1,12, 0, 0,11, 4, 0, 2, 0, /* 例==>|     |     |   ==> | 1|12| 0| */
    0, 8, 0, 9, 7, 4, 2, 0, 0,   /*    |    1|4    |       +--+--+--+ */
    0, 8, 0, 1,14, 0, 0, 3, 4,   /*    |     |  8  |       | 0|11| 4| */
    0, 0, 8, 1,13, 6, 0, 2, 0,   /*    +-----+-----+-----+ +--+--+--+ */
    0, 9, 4, 1,14, 0, 0, 2, 0,   /*          |  2  |     | | 0| 2| 0| */
    0, 8, 0, 1, 7,12, 0, 0, 2,   /*          |    1|4    | +--+--+--+ */
    0, 8, 0, 0,11, 4, 1, 6, 0,   /*          |  8  |     |            */
    8, 0, 0, 3,13, 4, 0, 2, 0 }; /*          +-----+-----+ ４辺に２進 */
                                 /*          |  2  |     数の重みを付 */
                                 /*          |     |     け辺の接する */
                                 /*          |     |     値の合計値で */
                                 /*          +-----+     マスを表わす */
int  board[8][8];           /* ８×８のボード   */
int  anser[3][8][8];        /* 解答パターン     */
int  gaps;                  /* 確定した隙間数   */
int  gapscut;               /* 枝刈用隙間数     */
int  mode;                  /* 処理モード       */
int  count;                 /* 解答の個数       */

/* ボードを裏返す */
void reverse(int workA[8][8], int workB[8][8])
{
    int  x, y, w;

    for (y=0; y<8; y++)
        for (x=0; x<8; x++)
            workB[y][7-x] = ((w=workA[y][x])&10) | ((w&1)<<2) | ((w&4)>>2);
}

/* ボートを９０度回転する */
void rotation(int workA[8][8], int workB[8][8])
{
    int  x, y, w;

    for (y=0; y<8; y++)
        for (x=0; x<8; x++)
            workB[7-x][y] = (((w=workA[y][x])<<1)&15) | ((w&8)>>3);
}

/* 同形比較関数(0:なし 1:あり) */
int  judge(int work[8][8])
{
    int  i;

    for (i=0; i<count; i++)
        if (memcmp(&anser[i][0][0],work,sizeof(board)) == 0) return 1;
    return 0;
}

/* 回転裏返しによる同形があるかをチェック */
void samecheck(void)
{
    int  work1[8][8], work2[8][8], i, j;

    /* ボードを回転・裏返して同形判断する */
    rotation(board,work1); if (judge(work1)) return;
    rotation(work1,work2); if (judge(work2)) return;
    rotation(work2,work1); if (judge(work1)) return;
    reverse (work1,work2); if (judge(work2)) return;
    rotation(work2,work1); if (judge(work1)) return;
    rotation(work1,work2); if (judge(work2)) return;
    rotation(work2,work1); if (judge(work1)) return;

    /* 同形が無かったのでパターンを格納・表示する */
    memcpy(&anser[count++][0][0],board,sizeof(board));
    for (j=0; j<8; j++) {
        for (i=0; i<8; i++) {
            printf("%s",(board[j][i]  )? "■": "□");
            printf("%s",(board[j][i]&1)? "■": "　");
        }
        printf("\n");
        for (i=0; i<8; i++) {
            printf("%s",(board[j][i]&8)? "■　": "　　");
        }
        printf("\n");
    }
}

/* 隙間として残すことが確定したマスのカウント */
void gapscount(int y, int x)
{
    if (board[y][x] == 0) gaps++;
    if (x == 5) {
        if (board[y][6] == 0) gaps++;
        if (board[y][7] == 0) gaps++;
    }
}

/* Ｆペントミノを置けるか調べる(0:置けない 1:置ける) */
int  isput(int y, int x, int p)
{
    int  i, j;

    for (j=0; j<3; j++)
        for (i=0; i<3; i++)
            if (fpent[p][j][i] && board[y+j][x+i]) return 0;
    return 1;
}

/* Ｆペントミノをボートに置いていく(バックトラック) */
void backtrack(int piece, int y, int x)
{
    int  i, j, p, wkgaps=gaps;

    /* 次の行に移る場合 */
    if (x == 6) {
        x=0, y++;
        if (mode == 1) {
            if (y == 6) {
                /* １１片置かれていれば同形チェック */
                if (piece == 11) samecheck();
                return;
            }
        } else {
            if (y == 2) {
                /* ２行分の隙間の数の最小値を更新する */
                if (gaps < gapscut) gapscut = gaps;
                return;
            }
        }
    }

    /* そこにＦペントミノを置く場合 */
    if (board[y+1][x+1] == 0) {
        for (p=0; p<8; p++) {
            if ( isput(y,x,p) ) {

                /* Ｆペンミノをボードに置く */
                for (j=0; j<3; j++)
                    for (i=0; i<3; i++)
                        board[y+j][x+i] += fpent[p][j][i];

                /* 確定した隙間をカウントし許される範囲内なら再帰 */
                gapscount(y,x);
                if (gaps <= gapscut) backtrack(piece+1,y,x+1);
                gaps = wkgaps;

                /* Ｆペントミノをボードから取る */
                for (j=0; j<3; j++)
                    for (i=0; i<3; i++)
                        if (fpent[p][j][i]) board[y+j][x+i] = 0;
            }
        }
    }

    /* そこにはＦペントミノを置かない場合の再帰 */
    gapscount(y,x);
    if (gaps <= gapscut) backtrack(piece,y,x+1);
    gaps = wkgaps;
}

/* メイン処理 */
void mainp(void)
{
    int  i, j, p;

    /* 前調査：ボードの辺寄りの２行に残ってしまう隙間の最小数を求める */
    mode = 0;
    gapscut = 16;
    backtrack(0,0,0);
    printf("前調査結果：9 - %d = %d\n",gapscut,9-gapscut);
    gapscut = 9 - gapscut;    /* 本探索中に許される隙間の最大数に変換 */

    /* 本探索：裏返しを除いた４パターンを最初に置いて探索する         */
    mode = 1;
    for (p=0; p<4; p++) {
        for (j=0; j<3; j++)
            for (i=0; i<3; i++)
                board[j][i] = fpent[p][j][i];
        gaps = (board[0][0])? 0: 1;
        backtrack(1,0,1);
    }

    /* 解答数表示 */
    printf("解答 %d 通り",count);
}

/*************************** ( プログラムの説明､感想 ) *****************

・プログラムの説明

    まず、Ｆペントミノがボード上にどの様に置かれているかを表す方法とし
  て、Ｆペントミノの各正方形の４辺に２進数(右上左下の順で１２４８)の重
  みを付け、つながっている辺の重みの合計でその正方形を表します。その値
  を８×８のボードに転記することで、Ｆペントミノがどの様に配置されてい
  るかが明確に識別可能になり、鏡像解のチェックも出来る様になります。
    さて、Ｆペントミノを３×３の駒と考え駒の左上端を着手点としてボード
  の左上から横優先の順にバックトラックで置いていくことを考えると着手点
  としては６×６の範囲になり、右２列と最後の２行は必然的に決定されます。
    つぎに枝刈り法ですが、９つの隙間が最後に残ることに着目して、探索中
  において確定した隙間の数を常に数え、その数が許される隙間の数を越えて
  しまったら枝刈りしますが、隙間の数え方として基本的には着手点が隙間か
  どうかで数えますが、右２列については着手点が改行する時に数えます。
  最後の２行については駒が１１個置けたかどうかの判断を優先した方がよい
  ので隙間の数を数える必要は無くなってしまいます。
    しかしながら、最後の２行については、どうしても残ってしまう隙間があ
  るはずです。そこで、ボードの辺寄りの２行にどうしても残ってしまう隙間
  の最小数を８×４のボード上で事前探索を行い求めておき、９からその値を
  引いた数、その数こそが本探索中において許される隙間の最大数となります。
  その数を本探索の中で用いることでより効果的な枝刈りが可能になります。


・感  想

    子供の頃に「プラパズル」とか言う詰めものパズルを夢中になって遊んだ
  ことを懐かしく思い出しました。説明書にはコンピューターで調べて××通
  りの解があるとか書いてあったように思いますが、昔どんなコンピューター
  を使ったんでしょうかね。

***********************************************************************/