/**************************************************/
/* 　スライドパズル最長手数面の探索/幅優先探索(2) */
/* 　　　　 　　Computer&Puzzle 2004/2 by takaken */
/**************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* BOARD_SIZEが4以上12以下になること(MEM=128MB) */
#define  BOARD_WIDTH       4    /* ボード横長さ */
#define  BOARD_HEIGHT      3    /* ボード縦長さ */
#define  BOARD_SIZE  (BOARD_WIDTH * BOARD_HEIGHT)

typedef  unsigned long  u32;

int BOARD[BOARD_SIZE];
int MOVAL[BOARD_SIZE][5];   /* 移動可能テーブル */
int PASCAL[BOARD_SIZE][3];  /* パスカルの三角形 */
int FACTOR[BOARD_SIZE-2];   /* 階乗値テーブル   */
int MAX_FACTOR;             /* (BOARD_SIZE-2)!  */

int TBLSIZE;
u32 *TABLE1;                /* フラグテーブル１ */
u32 *TABLE2;                /* フラグテーブル２ */

/****************************************************/
/* 各種テーブル作成                                 */
/****************************************************/
void Initialize(void)
{
    int  i, j, c, vect, x1, y1, x2, y2, hashsize;
    int  diffy[] = {-1, 0, 1, 0};
    int  diffx[] = { 0, 1, 0,-1};

    /* 巨大なフラグテーブルを確保する */
    for (hashsize=1,i=BOARD_SIZE; i>=3; i--)
        hashsize *= i;
    TBLSIZE = ((hashsize - 1) / 32 + 1);
    if (NULL == (TABLE1 = calloc(TBLSIZE, sizeof(u32)))) {
        printf("フラグテーブル作成に失敗(1)\n"); exit(1);
    }
    if (NULL == (TABLE2 = calloc(TBLSIZE, sizeof(u32)))) {
        printf("フラグテーブル作成に失敗(2)\n"); exit(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<BOARD_SIZE; i++)
        for (PASCAL[i][0]=1,j=1; j<3; j++)
            PASCAL[i][j] = PASCAL[i-1][j-1] + PASCAL[i-1][j];

    /* FACTOR[位置] */
    for (FACTOR[BOARD_SIZE-4]=1,i=BOARD_SIZE-5,c=2; i>=0; i--,c++)
        FACTOR[i] = FACTOR[i+1] * c;
    MAX_FACTOR = FACTOR[0] * c;
}
/****************************************************/
/* 最少完全ハッシュ関数(局面のhash値を求める)       */
/****************************************************/
int ChangeNumber(void)
{
    int  hash = 0, i, j, n, r, work[BOARD_SIZE-2];

    /* 組合せ */
    for (j=i=0,n=BOARD_SIZE-1,r=2; i<BOARD_SIZE; n--,i++) {
        if (BOARD[i] == BOARD_SIZE-2)
            hash += PASCAL[n][r--];
        else
            work[j++] = BOARD[i];
    }

    hash *= MAX_FACTOR;
    /* 順列 */
    for (i=0; i<BOARD_SIZE-3; i++) {
        hash += work[i] * FACTOR[i];
        for (j=i+1; j<BOARD_SIZE-3; j++)
            if (work[i] < work[j]) work[j]--;
    }
    return hash;
}
/****************************************************/
/* 最少完全ハッシュ逆関数(hash値から局面を復元する) */
/****************************************************/
void ChangeBoard(int hash)
{
    int  hash1, hash2, i, j, n, r, c, work[BOARD_SIZE-2];

    hash1 = hash / MAX_FACTOR;
    hash2 = hash % MAX_FACTOR;
    /* 順列 */
    for (i=0; i<BOARD_SIZE-3; i++) {
        work[i] = hash2 / FACTOR[i];
        hash2 -= FACTOR[i] * work[i];
    }
    work[BOARD_SIZE-3] = 0;
    for (i=BOARD_SIZE-4; i>=0; i--)
        for (j=i+1; j<BOARD_SIZE-2; j++)
            if (work[i] <= work[j]) work[j]++;
    /* 組合せ */
    for (i=j=0,n=BOARD_SIZE-1,r=2; i<BOARD_SIZE; n--,i++) {
        c = PASCAL[n][r];
        if (hash1 >= c) {
            hash1 -= c;
            r--;
            BOARD[i] = BOARD_SIZE-2;
        } else
            BOARD[i] = work[j++];
    }
}
/****************************************************/
/* 最後に残った局面(最長手数面)を表示する           */
/****************************************************/
void Result(void)
{
    int  idx, pos, result = 0;
    int  i, j, space, invert, tb[2];
    u32  bit;

    /* フラグテーブルをスキャンする */
    for (idx=0; idx<TBLSIZE; idx++) {
        for (pos=0,bit=1; bit; pos++,bit<<=1) {
            /* n手目グループ[1,0]ならその局面を復元する */
            if ((TABLE1[idx] & bit) && !(TABLE2[idx] & bit)) {
                ChangeBoard(idx * 32 + pos); /* 復元する */
                for (space=j=i=0; i<BOARD_SIZE; i++) {
                    if (BOARD[i] == BOARD_SIZE-2) tb[j++] = i;
                    if (BOARD[i] ==    0        ) space   = i;
                }
                /* 転倒数を調べ偶奇性の正しい局面にする */
                BOARD[tb[0]] = BOARD_SIZE-1;
                invert = (BOARD_WIDTH % 2)? 0: BOARD_HEIGHT-1 - space/BOARD_WIDTH;
                for (i=0; i<BOARD_SIZE; i++) {
                    if (!BOARD[i]) continue;
                    for (j=i+1; j<BOARD_SIZE; j++)
                        if (BOARD[j] && BOARD[i]>BOARD[j]) invert++;
                }
                if (invert % 2) {
                    BOARD[tb[0]] = BOARD_SIZE-2;
                    BOARD[tb[1]] = BOARD_SIZE-1;
                }
                /* 表示 */
                printf("[%d]",++result);
                for (i=0; i<BOARD_SIZE; i++) {
                    if (i % BOARD_WIDTH == 0) printf("\n");
                    printf(" %2d",BOARD[i]);
                }
                printf("\n");
            }
        }
    }
}
/****************************************************/
/* フラグテーブル更新                               */
/****************************************************/
void Update(void)
{
    int  idx, pos;
    u32  bit;

    /* フラグテーブルをスキャンする */
    for (idx=0; idx<TBLSIZE; idx++) {
        for (pos=0,bit=1; bit; pos++,bit<<=1) {
            if (TABLE1[idx] & bit) {
                /* [1,0] -> [1,1] */
                if (!(TABLE2[idx] & bit)) TABLE2[idx] |= bit;
            } else {
                /* [0,1] -> [1,0] */
                if (TABLE2[idx] & bit) {
                    TABLE1[idx] |= bit;
                    TABLE2[idx] ^= bit;
                }
            }
        }
    }
}
/****************************************************/
/* 幅優先探索 (TABLE1[]  ->  TABLE2[])              */
/****************************************************/
int Search(void)
{
    int  space, piece, i, count = 0;
    int  idx1, idx2, pos, hash;
    u32  bit1, bit2;

    /* フラグテーブルをスキャンする */
    for (idx1=0; idx1<TBLSIZE; idx1++) {
        for (pos=0,bit1=1; bit1; pos++,bit1<<=1) {
            /* n手目グループ[1,0]ならその局面を復元する */
            if ((TABLE1[idx1] & bit1) && !(TABLE2[idx1] & bit1)) {
                ChangeBoard(idx1 * 32 + pos); /* 復元する */
                /* 空きエリアの位置を調べる */
                for (space=0; ; space++)
                    if (BOARD[space] == 0) break;
                /* １手加えてn+1手目グループを探す */
                for (i=0; MOVAL[space][i]!=-1; i++) {
                    piece = MOVAL[space][i];
                    BOARD[space] = BOARD[piece];
                    BOARD[piece] = 0;
                    /* 局面値を求める */
                    hash = ChangeNumber();
                    idx2 = hash / 32;
                    bit2 = 1 << (hash % 32);
                    /* 初めての局面[0,0]ならn+1手目グループ[0,1]とする */
                    if (!(TABLE1[idx2] & bit2) && !(TABLE2[idx2] & bit2)) {
                        TABLE2[idx2] |= bit2;
                        count++; /* 個数を数える */
                    }
                    BOARD[piece] = BOARD[space];
                    BOARD[space] = 0;
                }
            }
        }
    }
    return count;
}
int main(void)
{
    int  i, hash, count, moves = 0;
    time_t st = time(NULL);

    /* 各種テーブル作成 */
    Initialize();

    /* 完了型を作る(BOARD_SIZE-2が2枚) */
    for (i=0; i<BOARD_SIZE-2; i++)
        BOARD[i] = i + 1;
    BOARD[BOARD_SIZE-2] = BOARD_SIZE-2;
    BOARD[BOARD_SIZE-1] = 0;

    /* 完了型を登録する */
    hash = ChangeNumber();
    TABLE1[hash / 32] = 1 << (hash % 32);
    printf("%2dmoves:%8d%4dsec\n",moves++, 1, time(NULL)-st);

    /* 幅優先探索 */
    for (;;) {
        count = Search();
        if (count == 0) break;
        printf("%2dmoves:%8d%4dsec\n",moves++, count, time(NULL)-st);
        Update();
    }
    Result();

    return 0;
}