/**************************************************/
/*   １５パズル/PDB用テーブル作成       puz15db.c */
/*           Computer & Puzzle 2001/04 by takaken */
/**************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define  BOARD_WIDTH       4    /* ボード横長さ */
#define  BOARD_HEIGHT      4    /* ボード縦長さ */
#define  BOARD_SIZE  (BOARD_WIDTH * BOARD_HEIGHT)

#define  PDBSIZE  12108096 /* = 16 * 15C5 * 10C5  */
#define  TBLSIZE    378378 /* = (PDB_SIZE-1)/32+1 */

typedef  unsigned long  u32;

/******************/
/* データベース１ */
/******************/
char *FileName1 = "puz15p1.db";
int  BOARD1[BOARD_SIZE] = {
    3, 1, 1, 1,
    2, 3, 3, 1,
    2, 3, 3, 1,
    2, 2, 2, 0
};

/******************/
/* データベース２ */
/******************/
char *FileName2 = "puz15p2.db";
int  BOARD2[BOARD_SIZE] = {
    1, 1, 1, 3,
    1, 3, 3, 2,
    1, 3, 2, 2,
    3, 2, 2, 0
};

int  BOARD[BOARD_SIZE];
char PDB[PDBSIZE];           /* パターンＤＢ     */
int  MOVAL[BOARD_SIZE][5];   /* 移動可能テーブル */
int  PASCAL[BOARD_SIZE][6];  /* パスカルの三角形 */

u32  BITTBL[32];         /* １ビット値テーブル   */
u32  SAMEDB[TBLSIZE];    /* 同一局面検査テーブル */
u32  CHECK1[TBLSIZE];    /* 新局面フラグテーブル */
u32  CHECK2[TBLSIZE];    /* 新局面フラグテーブル */

time_t StartTime;

/****************************************************/
/* 探索結果のテーブルをディスクに保存する           */
/****************************************************/
void WritePDB(char *filename)
{
    int  i;
    FILE *fp;

    fp = fopen(filename, "wb");
    for (i=0; i<PDBSIZE; i++)
        putc(PDB[i], fp);
    fclose(fp);
}
/****************************************************/
/* 各種テーブル作成                                 */
/****************************************************/
void Initialize(void)
{
    int  i, j, c, vect, x1, y1, x2, y2;
    int  diffy[] = {-1, 0, 1, 0};
    int  diffx[] = { 0, 1, 0,-1};

    /* MOVAL[位置][添字] */
    for (i=0; i<BOARD_SIZE; i++) {
        y1 = i / BOARD_WIDTH;
        x1 = i % BOARD_WIDTH;
        for (c=vect=0; vect<4; vect++) {
            y2 = y1 + diffy[vect];
            x2 = x1 + diffx[vect];
            j  = y2 * BOARD_WIDTH + x2;
            if (y2>=0 && y2<BOARD_HEIGHT &&
                x2>=0 && x2<BOARD_WIDTH) MOVAL[i][c++] = j;
        }
        MOVAL[i][c] = -1;
    }

    /* PASCAL[n][r] = nCr */
    for (PASCAL[0][0]=1,i=1; i<=14; i++)
        for (PASCAL[i][0]=1,j=1; j<=5; j++)
            PASCAL[i][j] = PASCAL[i-1][j-1] + PASCAL[i-1][j];

    /* BITTBL[添字] */
    for (BITTBL[0]=1,i=1; i<32; i++)
        BITTBL[i] = BITTBL[i-1] << 1;
}
/****************************************************/
/* 最少完全ハッシュ関数(局面のhash値を求める)       */
/****************************************************/
long ChangeNumber(void)
{
    int  num, i, n1, n2, r1, r2;
    long hash, h0, h1, h2;

    h0 = h1 = h2 = 0;
    n1=14; r1=5;
    n2= 9; r2=5;
    for (i=0; i<BOARD_SIZE; i++) {
        num = BOARD[i];
        if (num == 0) {
            h0 = i;
        } else {
            if (num == 1) {
                h1 += PASCAL[n1][r1--];
            } else {
                if (num == 2)
                    h2 += PASCAL[n2][r2--];
                n2--;
            }
            n1--;
        }
    }
    hash = (h2 * 3003 + h1) * 16 + h0;

    return hash;
}
/****************************************************/
/* 最少完全ハッシュ逆関数(hash値から局面を復元する) */
/****************************************************/
void ChangeBoard(long hash)
{
    int  i, c, n1, n2, r1, r2;
    long h0, h1, h2;

    h0 = hash %   16; hash /=   16;
    h1 = hash % 3003; hash /= 3003;
    h2 = hash;

    for (i=0; i<BOARD_SIZE; i++) BOARD[i] = 3;
    BOARD[h0] = 0;

    n1=14; r1=5;
    n2= 9; r2=5;
    for (i=0; i<16; i++) {
        if (BOARD[i] == 0) continue;
        c = PASCAL[n1][r1];
        if (h1 >= c) {
            h1 -= c;
            r1--;
            BOARD[i] = 1;
        } else {
            c = PASCAL[n2][r2];
            if (h2 >= c) {
                h2 -= c;
                r2--;
                BOARD[i] = 2;
            }
            n2--;
        }
        n1--;
    }
}
/****************************************************/
/* 幅優先探索 (GETTBL[]  ->  PUTTBL[])              */
/****************************************************/
int Search(u32 GETTBL[], u32 PUTTBL[], int moves)
{
    int count = 0, space, piece, number, i;
    int pos1, bit1, hash1, pos2, bit2, hash2;
    u32 bitmap1, bitmap2;

    /* GETTBL[]を順次呼び込む */
    for (pos1=0; pos1<TBLSIZE; pos1++) {
        bitmap1 = GETTBL[pos1];
        hash1 = pos1 << 5;
        for (bit1=0; bitmap1; bit1++,bitmap1>>=1) {
            if (!(bitmap1 & 1)) continue;
            ChangeBoard(hash1 + bit1);
            for (space=0; BOARD[space]; space++);
            /* 新局面生成しPUTTBL[]へ書き出す */
            for (i=0; (piece=MOVAL[space][i])!=-1; i++) {
                number = BOARD[piece];
                BOARD[space] = number;
                BOARD[piece] = 0;
                hash2 = ChangeNumber();
                pos2 = hash2 >> 5;
                bit2 = hash2 & 0x1F;
                bitmap2 = BITTBL[bit2];
                if (!(SAMEDB[pos2] & bitmap2)) {
                    SAMEDB[pos2] |= bitmap2;
                    PUTTBL[pos2] |= bitmap2;
                    PDB[hash2] = (char)moves;
                    count++;
                }
                BOARD[space] = 0;
                BOARD[piece] = number;
            }
        }
    }
    return count;
}
void main_sub(void)
{
    int  i, count, hash,  moves;

    /* フラグテーブル初期化 */
    for (i=0; i<TBLSIZE; i++)
        SAMEDB[i] = CHECK1[i] = CHECK2[i] = 0;

    /* 完了型を登録する */
    moves = 0;
    hash = ChangeNumber();
    SAMEDB[hash >> 5] = BITTBL[hash & 0x1F];
    CHECK1[hash >> 5] = BITTBL[hash & 0x1F];
    PDB[hash] = 0;
    printf("%2dmoves:%8d%4dsec\n",moves++, 1, time(NULL)-StartTime);

    for (;;) {
        /* CHECK1 -> CHECK2 */
        count = Search(CHECK1, CHECK2, moves);
        if (!count) break;
        printf("%2dmoves:%8d%4dsec\n",moves++, count, time(NULL)-StartTime);
        for (i=0; i<TBLSIZE; i++) CHECK1[i] = 0;

        /* CHECK2 -> CHECK1 */
        count = Search(CHECK2, CHECK1, moves);
        if (!count) break;
        printf("%2dmoves:%8d%4dsec\n",moves++, count, time(NULL)-StartTime);
        for (i=0; i<TBLSIZE; i++) CHECK2[i] = 0;
    }
}
int main(void)
{
    int  i;

    /* 各参照テーブル準備 */
    Initialize();
    StartTime = time(NULL);

    /* データベース１ */
    printf("making.....DB1\n");
    for (i=0; i<BOARD_SIZE; i++)
        BOARD[i] = BOARD1[i];
    main_sub();
    printf("saving.....DB1\n");
    WritePDB(FileName1);

    /* データベース２ */
    printf("making.....DB2\n");
    for (i=0; i<BOARD_SIZE; i++)
        BOARD[i] = BOARD2[i];
    main_sub();
    printf("saving.....DB2\n");
    WritePDB(FileName2);

    printf("finish!\n");
    return 0;
}