/*****************************************************************************/
/* PENTOMINO(6*10)  with Breadth First Search     2001/02/05 by takaken      */
/*****************************************************************************/
/* BOARD MAP
( 0)( 1)( 2)( 3)( 4)( 5)( 6)
  7   8   9  10  11  12 (13)
 14  15  16  17  18  19 (20)
            |
 63  64  65  66  67  68 (69)
 70  71  72  73  74  75 (76)
(77)(78)(79)(80)(81)(82)
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define  FALSE      0
#define  TRUE       1

#define  SPACE      0
#define  WALL       1
#define  SILHOUETTE 2
#define  BOX        3

#define  BOARD_SIZE      83
#define  XSIZE            7
#define  BUCKET_SIZE  60013

typedef  unsigned long  ulong;
typedef  struct bucket {
    int    result_count;
    long   silhouette;
    short  used_piece;
    struct bucket *link;
} bucket_t;
bucket_t BUCKET[BUCKET_SIZE];
bucket_t *HEADER[BOARD_SIZE];

int  ResultCount;
int  BucketCount, MaxBucket;
int  PaintCode, PaintCount;
int  PAINT[BOARD_SIZE];
int  BOARD[BOARD_SIZE];
int  DIFF[4] = {-XSIZE, 1, XSIZE, -1};
int  INDEX[12];
int  PIECE[12][8][4] = {
     1, 2, 3, 4, /* □□□□□ */
     7,14,21,28, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0,
     0, 0, 0, 0,
     0, 0, 0, 0,

     1, 2, 3, 7, /* □□□□　 */
     1, 2, 3,10, /* □　　　　 */
     1, 7,14,21, /* 　　　　　 */
     1, 8,15,22, /* 　　　　　 */
     4, 5, 6, 7, /* 　　　　　 */
     7, 8, 9,10,
     7,14,20,21,
     7,14,21,22,

     1, 2, 3, 8, /* □□□□　 */
     1, 2, 3, 9, /* 　□　　　 */
     5, 6, 7, 8, /* 　　　　　 */
     6, 7, 8, 9, /* 　　　　　 */
     6, 7,14,21, /* 　　　　　 */
     7, 8,14,21,
     7,13,14,21,
     7,14,15,21,

     1, 2, 6, 7, /* 　□□□　 */
     1, 2, 9,10, /* □□　　　 */
     1, 5, 6, 7, /* 　　　　　 */
     1, 8, 9,10, /* 　　　　　 */
     6, 7,13,20, /* 　　　　　 */
     7, 8,15,22,
     7,13,14,20,
     7,14,15,22,

     1, 2, 7, 8, /* □□□　　 */
     1, 2, 8, 9, /* □□　　　 */
     1, 6, 7, 8, /* 　　　　　 */
     1, 7, 8, 9, /* 　　　　　 */
     1, 7, 8,14, /* 　　　　　 */
     1, 7, 8,15,
     6, 7,13,14,
     7, 8,14,15,

     1, 2, 7, 9, /* □□□　　 */
     1, 7,14,15, /* □　□　　 */
     1, 8,14,15, /* 　　　　　 */
     2, 7, 8, 9, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0,
     0, 0, 0, 0,
     0, 0, 0, 0,

     1, 2, 7,14, /* □□□　　 */
     1, 2, 9,16, /* □　　　　 */
     7,12,13,14, /* □　　　　 */
     7,14,15,16, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0,
     0, 0, 0, 0,
     0, 0, 0, 0,

     1, 2, 8,15, /* □□□　　 */
     5, 6, 7,14, /* 　□　　　 */
     7, 8, 9,14, /* 　□　　　 */
     7,13,14,15, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0,
     0, 0, 0, 0,
     0, 0, 0, 0,

     1, 6, 7,13, /* 　□□　　 */
     1, 8, 9,16, /* □□　　　 */
     6, 7,12,13, /* □　　　　 */
     7, 8,15,16, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0,
     0, 0, 0, 0,
     0, 0, 0, 0,

     1, 6, 7,14, /* 　□□　　 */
     1, 8, 9,15, /* □□　　　 */
     5, 6, 7,13, /* 　□　　　 */
     6, 7, 8,13, /* 　　　　　 */
     6, 7, 8,15, /* 　　　　　 */
     6, 7,14,15,
     7, 8, 9,15,
     7, 8,13,14,

     1, 7,13,14, /* 　□□　　 */
     1, 8,15,16, /* 　□　　　 */
     5, 6, 7,12, /* □□　　　 */
     7, 8, 9,16, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0,
     0, 0, 0, 0,
     0, 0, 0, 0,

/******** SPECIAL PIECE ********/

     6, 7, 8,14, /* 　□　　　 */
     0, 0, 0, 0, /* □□□　　 */
     0, 0, 0, 0, /* 　□　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0, /* 　　　　　 */
     0, 0, 0, 0,
     0, 0, 0, 0,
     0, 0, 0, 0
};

/*****************************************************************************/
/* Debug ( Display )                                                         */
/*****************************************************************************/
void Display()
{
    int  i;

    system("cls");
    printf("BucketCount = %d\n", BucketCount);
    printf("ResultCount = %d  ", ResultCount);
    for (i=0; i<BOARD_SIZE; i++) {
        if (i % XSIZE == 0) printf("\n");
        switch (BOARD[i]) {
            case SPACE:       printf("　"); break;
            case WALL:        printf("■"); break;
            case SILHOUETTE:  printf("※"); break;
            case BOX:         printf("□"); break;
        }
    }
    printf("■\n");
}
/*****************************************************************************/
/* Paint                                                                     */
/*****************************************************************************/
void PaintSub(int pos0)
{
    int  pos1, vect;

    PAINT[pos0] = PaintCode;
    PaintCount++;
    for (vect=0; vect<4; vect++) {
        pos1 = pos0 + DIFF[vect];
        if (!BOARD[pos1] && PAINT[pos1]!=PaintCode)
            PaintSub(pos1);
    }
}
int PaintCheck(int start_space)
{
    int  pos;

    if (++PaintCode == 0) {
        PaintCode = 1;
        for (pos=0; pos<BOARD_SIZE; pos++) PAINT[pos] = 0;
    }
    for (pos=start_space; pos<BOARD_SIZE; pos++) {
        if (BOARD[pos] || PAINT[pos]==PaintCode) continue;
        PaintCount = 0;
        PaintSub(pos);
        if (PaintCount % 5) return FALSE;
    }
    return TRUE;
}
/*****************************************************************************/
/* BackTarck                                                              */
/*****************************************************************************/
int FrontCheck(int start_space, short used_piece, int depth)
{
    int   pos, i, j, k, index, retc, *piece, pos_table[5];
    short bit;

    if (used_piece==0x7FF) return TRUE;
    if (depth == 5) {
        return PaintCheck(start_space);
    } else {
        pos_table[4] = start_space;
        for (bit=1, i=0; i<11; i++, bit<<=1) {
            if (used_piece & bit) continue;
            index = INDEX[i];
            for (j=0; j<index; j++) {
                piece = &PIECE[i][j][0];
                for (k=0; k<4; k++)
                    if (BOARD[pos_table[k] = start_space + piece[k]]) break;
                if (k == 4) {
                    for (k=0; k<5; k++) BOARD[pos_table[k]] = BOX;
                    for (pos=start_space; BOARD[pos]; pos++);
                    retc = FrontCheck(pos, (short)(used_piece | bit), depth + 1);
                    for (k=0; k<5; k++) BOARD[pos_table[k]] = SPACE;
                    if (retc) return TRUE;
                }
            }
        }
    }
    return FALSE;
}
/*****************************************************************************/
/* Bucket In                                                                 */
/*****************************************************************************/
void BucketIn(int start_space, bucket_t *this_bucket, short bit)
{
    int   pos;
    short used_piece;
    long  silhouette;
    ulong hash;
    bucket_t *next_bucket;

    /* used_piece */
    used_piece = (short)(this_bucket->used_piece | bit);
    if (used_piece == 0x7FF) {
        ResultCount += this_bucket->result_count; return;
    }

    /* start_space */
    while (BOARD[start_space]) start_space++;

    /* Cut of Branch */
    if (!PaintCheck(start_space)) return;
    if (!FrontCheck(start_space, used_piece, 0)) return;

    /* silhouette */
    pos = start_space + 27;
    if (pos > 75) pos = 75;
    for (silhouette=0; pos>start_space; pos--) {
        silhouette <<= 1;
        if (BOARD[pos] >= SILHOUETTE) silhouette |= 1;
    }

    /* HASH FUNC */
    hash = (used_piece * 37 + silhouette) % BUCKET_SIZE;

    /* POINTER */
    for (;;) {
        next_bucket = &BUCKET[hash];
        if (next_bucket->result_count == 0) break;
        if (next_bucket->used_piece==used_piece && next_bucket->silhouette==silhouette) {
            next_bucket->result_count += this_bucket->result_count; return;
        }
        hash = (hash + 491) % BUCKET_SIZE;
    }

    /* BUCKET IN */
    if (BucketCount >= (BUCKET_SIZE * 4 / 5)) {
        printf("BUCKET FULL\n"); exit(1);
    }
    if (++BucketCount > MaxBucket) MaxBucket = BucketCount;
    next_bucket->result_count = this_bucket->result_count;
    next_bucket->used_piece   = used_piece;
    next_bucket->silhouette   = silhouette;
    next_bucket->link = HEADER[start_space];
    HEADER[start_space] = next_bucket;
}
/*****************************************************************************/
/* Breadth First Search                                                      */
/*****************************************************************************/
void Search(char start_space)
{
    int   pos, i, j, k, index, *piece, pos_table[4];
    short bit;
    long  silhouette;
    bucket_t *this_bucket;

    for (;;) {
        /* BUCKET OUT */
        if ((this_bucket = HEADER[start_space]) == NULL) break;
        HEADER[start_space] = this_bucket->link;
        /* PUT SILHOUETTE */
        silhouette = this_bucket->silhouette;
        for (pos=start_space+1; silhouette; pos++, silhouette>>=1)
            if (silhouette & 1) BOARD[pos] = SILHOUETTE;
        /* ADD PIECE */
        for (bit=1, i=0; i<11; i++, bit<<=1) {
            if (this_bucket->used_piece & bit) continue;
            index = INDEX[i];
            for (j=0; j<index; j++) {
                piece = &PIECE[i][j][0];
                for (k=0; k<4; k++)
                    if (BOARD[pos_table[k] = start_space + piece[k]]) break;
                if (k == 4) {
                    for (k=0; k<4; k++) BOARD[pos_table[k]] = BOX;
                    BucketIn(start_space, this_bucket, bit);
                    for (k=0; k<4; k++) BOARD[pos_table[k]] = SPACE;
                }
            }
        }
        /* GET SILHOUETTE */
        silhouette = this_bucket->silhouette;
        for (pos=start_space+1; silhouette; pos++, silhouette>>=1)
            if (silhouette & 1) BOARD[pos] = SPACE;
        /* RELEASE FROM BUCKET */
        this_bucket->result_count = 0; /* EMPTY */
        BucketCount--;
    }
}
/*****************************************************************************/
/* Pentomino                                                                 */
/*****************************************************************************/
void Pentomino()
{
    int  i;
    char start_space;
    bucket_t *start_bucket;

    /* INITIALIZE */
    for (i=0; i<BUCKET_SIZE; i++) BUCKET[i].result_count = 0;
    for (i=0; i<BOARD_SIZE; i++) HEADER[i] = NULL;

    /* BOARD */
    for (i=0; i<BOARD_SIZE; i++)
        if (BOARD[i] == SILHOUETTE) BOARD[i] = SPACE;

    /* START PATTERN */
    start_space = 7;
    while (BOARD[start_space]) start_space++;
    start_bucket = &BUCKET[0];
    start_bucket->result_count = 1;
    start_bucket->used_piece   = 0;
    start_bucket->silhouette   = 0;
    start_bucket->link         = NULL;
    HEADER[start_space] = start_bucket;
    BucketCount = 1;

    /* SEARCH */
    for (start_space=7; start_space<BOARD_SIZE; start_space++) {
        if (!BOARD[start_space]) {
            BOARD[start_space] = BOX;
            Search(start_space);
            BOARD[start_space] = SILHOUETTE;
        }
    }
}
int main(void)
{
    clock_t start_time = clock();
    int  i, j, k;

    /* INDEX */
    for (i=0; i<12; i++) {
        for (j=0; j<8; j++)
            if (!PIECE[i][j][0]) break;
        INDEX[i] = j;
    }

    /* BOARD */
    for (i=0; i<BOARD_SIZE; i++) BOARD[i] = WALL;
    for (i=7; i<=70; i+=7)
        for (j=0; j<6; j++)
            BOARD[i + j] = SPACE;

    /* CROSS */
    for (i=8; i<=29; i+=7)
    for (j=0; j<2; j++) {
        BOARD[i + j] = WALL;
        for (k=0; k<4; k++) BOARD[i + j + PIECE[11][0][k]] = WALL;
        Pentomino();
        BOARD[i + j] = SPACE;
        for (k=0; k<4; k++) BOARD[i + j + PIECE[11][0][k]] = SPACE;
    }

    /* RESULT */
    printf("ResultCount = %d\n", ResultCount);
    printf("MaxBucket   = %d/%d\n", MaxBucket, BUCKET_SIZE * 4 / 5);
    printf("Time = %f sec\n", ((float)(clock() - start_time)) / CLK_TCK);
    return 0;
}