/**************************************************/
/*   １５パズル/反復深化 with WD,PDB   puz15sv2.c */
/*           Computer & Puzzle 2001/04 by takaken */
/**************************************************/
/* 実行にはpuz15wd.cで得るpuz15wd.db及びpuz15db.c */
/* から得られるpuz15p1.dbとpuz15p2.dbが必要です。 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define  FALSE           0
#define  TRUE            1
#define  BOARD_WIDTH     4
#define  BOARD_SIZE     16

#define  WDTBL_SIZE  24964 /* WalkingDistance TableSize */
#define  PDB_SIZE 12108096 /* = 16 * 15C5 * 10C5  */

typedef  unsigned __int64  u64;

int  BOARD[BOARD_SIZE] = {
 1, 5, 9,13,  // sample
 2, 6,10,14,
 3, 7,11,15,
 4, 8,12, 0
};

/* Pattern Dababase */
char *PDB;
char  PDB1[PDB_SIZE];
char  PDB2[PDB_SIZE];

/* WalkingDistance */
u64   WDPTN[WDTBL_SIZE];        /* パターンテーブル */
short WDLNK_UL[WDTBL_SIZE][BOARD_WIDTH];  /* リンク */
short WDLNK_DR[WDTBL_SIZE][BOARD_WIDTH];  /* リンク */
char  WDTBL[WDTBL_SIZE];        /* WD算出テーブル   */

int   PASCAL[15][6];
int   PASCAL1[15][6];
int   PASCAL2[15][6];
char  RESULT[100];              /* 解答記録テーブル */
int   DEPTH;                    /* 探索の深さ制限値 */
int   MOVAL[BOARD_SIZE][5] = {  /* 移動可能テーブル */
  1,  4, -1,  0,  0,
  2,  5,  0, -1,  0,
  3,  6,  1, -1,  0,
  7,  2, -1,  0,  0,
  0,  5,  8, -1,  0,
  1,  6,  9,  4, -1,
  2,  7, 10,  5, -1,
  3, 11,  6, -1,  0,
  4,  9, 12, -1,  0,
  5, 10, 13,  8, -1,
  6, 11, 14,  9, -1,
  7, 15, 10, -1,  0,
  8, 13, -1,  0,  0,
  9, 14, 12, -1,  0,
 10, 15, 13, -1,  0,
 11, 14, -1,  0,  0
};
int  CONV[BOARD_SIZE] = {       /* 縦横変換テーブル */
    0,
    1, 5, 9,13,
    2, 6,10,14,
    3, 7,11,15,
    4, 8,12
};
time_t StartTime;

/*********************************************/
/* 各種参照テーブル準備                      */
/*********************************************/
void Initialize(void)
{
    int   i, j, nextd;
    u64   table;
    char  *filename0 = "puz15wd.db";
    char  *filename1 = "puz15p1.db";
    char  *filename2 = "puz15p2.db";
    FILE  *fp;

    /* WDPTN[], WDTBL[], WDLNK[][][] */
    fp = fopen(filename0, "rb");
    if (fp == NULL) { printf("%s nothing\n", filename0); exit(1); }
    for (i=0; i<WDTBL_SIZE; i++) {
        /* WDPTN */
        table = 0;
        for (j=0; j<8; j++)
            table = (table << 8) | getc(fp);
        WDPTN[i] = table;
        /* WDTBL */
        WDTBL[i] = (char)getc(fp);
        /* WDLNK */
        for (j=0; j<4; j++) {
            nextd = getc(fp);
            WDLNK_UL[i][j] = (short)((nextd << 8) | getc(fp));
        }
        for (j=0; j<4; j++) {
            nextd = getc(fp);
            WDLNK_DR[i][j] = (short)((nextd << 8) | getc(fp));
        }
    }
    fclose(fp);

    /* PDB1[] */
    fp = fopen(filename1, "rb");
    if (fp == NULL) { printf("%s nothing\n", filename1); exit(1); }
    for (i=0; i<PDB_SIZE; i++)
        PDB1[i] = (char)getc(fp);
    fclose(fp);

    /* PDB2[] */
    fp = fopen(filename2, "rb");
    if (fp == NULL) { printf("%s nothing\n", filename2); exit(1); }
    for (i=0; i<PDB_SIZE; i++)
        PDB2[i] = (char)getc(fp);
    fclose(fp);

    /* PASCAL[][] */
    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];
            PASCAL1[i][j] = PASCAL[i][j] * 16;
            PASCAL2[i][j] = PASCAL[i][j] * 16 * 3003;
        }
    }
}
/*********************************************/
/* データベース参照                          */
/*********************************************/
int *NUM;
int NUM1[] = {
    0,
    3,1,1,1,
    2,3,3,1,
    2,3,3,1,
    2,2,2
};
int NUM2[] = {
    0,
    1,1,1,3,
    1,3,3,2,
    1,3,2,2,
    3,2,2
};
char DataBase(void)
{
    int  i, n1, n2, r1, r2, num, hash = 0;

    n1=14; r1=5;
    n2= 9; r2=5;
    for (i=0; i<BOARD_SIZE; i++) {
        num = NUM[BOARD[i]];
        if (num == 0) {
            hash += i;
        } else {
            if (num == 1) {
                hash += PASCAL1[n1][r1--]; /* nCr * 16 */
            } else {
                if (num == 2)
                    hash += PASCAL2[n2][r2--]; /* nCr * 16 * 15C5 */
                n2--;
            }
            n1--;
        }
    }
    return PDB[hash];
}
/*********************************************/
/* 反復深化によるバックトラッキング          */
/*********************************************/
int IDA(int space, int prev, int idx1o, int idx2o, int skipo, int depth)
{
    int  i, n, piece, wd, pdb, diff, idx1, idx2, skip;

    /* 次の手を総て試してみる */
    depth++;
    for (i=0; ; i++) {
        piece = MOVAL[space][i]; /* 移動させる駒の座標 */
        if (piece == -1  ) break;              /* 番兵 */
        if (piece == prev) continue; /* 直前手戻り防止 */
        n = BOARD[piece];        /* 移動させる駒の数字 */

        /* WD枝刈り */
        diff = piece - space;
        if (diff > 0) {
            if (diff ==  4) {
                idx1 = WDLNK_UL[idx1o][(     n  - 1) >> 2]; /* 駒を上 */
                idx2 = idx2o;
            } else {
                idx1 = idx1o;
                idx2 = WDLNK_UL[idx2o][(CONV[n] - 1) >> 2]; /* 駒を左 */
            }
        } else {
            if (diff == -4) {
                idx1 = WDLNK_DR[idx1o][(     n  - 1) >> 2]; /* 駒を下 */
                idx2 = idx2o;
            } else {
                idx1 = idx1o;
                idx2 = WDLNK_DR[idx2o][(CONV[n] - 1) >> 2]; /* 駒を右 */
            }
        }
        wd = WDTBL[idx1] + WDTBL[idx2];
        if (depth + wd > DEPTH) continue;

        BOARD[piece] = 0;
        BOARD[space] = n;

        /* DB枝刈り */
        if (depth == skipo) {
            pdb = DataBase();
            if (pdb < wd) {
                skip = -1; /* これ以降PDBの使用を放棄 */
            } else {
                if (depth + pdb > DEPTH) {
                    BOARD[piece] = n;
                    BOARD[space] = 0;
                    continue;
                }
                /* 次のDB枝刈り地点 */
                /* skip + (pdb + (skip - depth)) > DEPTH */
                skip = ((DEPTH + depth - pdb) >> 1) + 1;
            }
        } else {
            skip = skipo;
        }

        /* 再帰呼び出し */
        if (depth==DEPTH || IDA(piece, space, idx1, idx2, skip, depth)) {
            RESULT[depth - 1] = (char)n;  /* 解答手順を記録する */
            return TRUE;
        }

        BOARD[piece] = n;
        BOARD[space] = 0;
    }
    return FALSE;
}
/*********************************************/
/* １５パズルを解く                          */
/*********************************************/
int Search(void)
{
    int  space, inv, num1, num2, idx1, idx2, wd, pdb, d1, d2;
    int  limit, max_pdb, skip, lowb, i, j, work[BOARD_WIDTH];
    u64  table;

    /* 解の存在チェック */
    for (space=0; BOARD[space]; space++);
    inv = (BOARD_WIDTH - 1) - space / BOARD_WIDTH;
    for (i=0; i<BOARD_SIZE; i++) {
        if (BOARD[i] == 0) continue;
        for (j=i+1; j<BOARD_SIZE; j++)
            if (BOARD[j] && BOARD[j]<BOARD[i]) inv++;
    }
    if (inv & 1) return FALSE;

    /* 初期 IDX1 for WD */
    table = 0;
    for (i=0; i<BOARD_WIDTH; i++) {
        for (j=0; j<BOARD_WIDTH; j++) work[j] = 0;
        for (j=0; j<BOARD_WIDTH; j++) {
            num1 = BOARD[i * BOARD_WIDTH + j];
            if (num1 == 0) continue;
            work[(num1 - 1) >> 2]++;
        }
        for (j=0; j<BOARD_WIDTH; j++)
            table = (table << 3) | work[j];
    }
    for (idx1=0; WDPTN[idx1]!=table; idx1++);

    /* 初期 IDX2 for WD */
    table = 0;
    for (i=0; i<BOARD_WIDTH; i++) {
        for (j=0; j<BOARD_WIDTH; j++) work[j] = 0;
        for (j=0; j<BOARD_WIDTH; j++) {
            num2 = CONV[BOARD[j * BOARD_WIDTH + i]];
            if (num2 == 0) continue;
            work[(num2 - 1) >> 2]++;
        }
        for (j=0; j<BOARD_WIDTH; j++)
            table = (table << 3) | work[j];
    }
    for (idx2=0; WDPTN[idx2]!=table; idx2++);

    /* 初期wd */
    wd = WDTBL[idx1] + WDTBL[idx2];

    /* 初期pdb */
    NUM = NUM1; PDB = PDB1; d1 = DataBase();
    NUM = NUM2; PDB = PDB2; d2 = DataBase();
    if (d1 > d2) {
        pdb = d1; NUM = NUM1; PDB = PDB1;
        max_pdb = 56;
    } else {
        pdb = d2;
        max_pdb = 58;
    }

    /* 初期LowerBound */
    lowb = (pdb > wd)? pdb: wd;
    printf("(WD=%d,DB1=%d,DB2=%d) LowerBound=%d\n", wd, d1, d2, lowb);

    /* IDA実行 */
    for (DEPTH=lowb; ; DEPTH+=2) {
        printf("-%d",DEPTH);
        if (pdb < wd) {
            skip = -1; /* PDBを使用しない */
        } else {
            skip  = ((DEPTH - pdb) >> 1) + 1; /* skip  + (pdb + skip) > DEPTH */
            limit =   DEPTH - max_pdb    + 1; /* limit +   max_pdb    > DEPTH */
            if (limit > skip) skip = limit;
        }
        if (IDA(space, -1, idx1, idx2, skip, 0)) break;
        printf(" %dsec\n",time(NULL)-StartTime);
    }

    return TRUE;
}
int main(void)
{
    int  i;

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

    /* BOARD表示(問題面表示) */
    for (i=0; i<BOARD_SIZE; i++) {
        if (i && !(i % BOARD_WIDTH)) printf("\n");
        printf("%3d",BOARD[i]);
    }
    printf("\n");

    /* 探索して結果を表示 */
    if (Search()) {
        printf("\n[%d moves] time=%dsec", DEPTH, time(NULL) - StartTime);
        for (i=0; i<DEPTH; i++) {
            if (i % 10 == 0) printf("\n");
            printf(" %2d ", RESULT[i]);
        }
        printf("\n");
    } else {
        printf("Impossible!!\n");
    }

    return 0;
}