#include <stdio.h>

#define BSIZE 1001  /* バケットサイズ(充分大きな素数) */
#define QSIZE  800  /* キューサイズ(バケットの８割程度) */

int iobox[] = {     /* 問題面(開始局面) */
    5,4,3,
    2,1,0
};


int BACKET[BSIZE][6], LINK[BSIZE];  /* バケット(局面格納とリンク元) */
int QUEUE[QSIZE], Qtop, Qend;       /* 幅優先探索用キュー(待ち行列) */

int box[] = {   /* 探索用フィールド */
    6,6,6,6,
    0,0,0,6,
    0,0,0,6,
    6,6,6
};
int cnv[] = {    /* 座標変換テーブル */
    4, 5, 6,
    8, 9,10
};
int diff[] = {   /* 方向ベクトル */
    -1, 4, 1,-4
};

/* ハッシュ関数 */
int hash_func() {
    int i, hash;
    unsigned long num = 0;

    /* 局面を数値化しハッシュ値を求める */
    for (i=0; i<6; i++)
        num = (num << 4) + box[cnv[i]];
    hash = num % BSIZE;

    for (;;) {
        if (BACKET[hash][0] == -1) break; /* 空バケット */
        for (i=0; i<6; i++)
            if (BACKET[hash][i] != box[cnv[i]]) break;
        if (i == 6) break;                /* 同型がある */
        hash = (hash + 1) % BSIZE;        /* 再ハッシュ */
    }
    return hash;
}

/* 幅優先探索 */
int hsearch(int adrE) {
    int i, c, adr1, adr2, vect, spos, cpos;

    while (Qtop != Qend) {
        adr1 = QUEUE[Qtop++];       /* キュー先頭より局面を取る */
        for (i=0; i<6; i++)
            if ((box[cnv[i]]=BACKET[adr1][i]) == 0)
                spos=cnv[i];           /* 空き位置 */

        for (vect=0; vect<4; vect++) {     /* 4方向について */
            cpos = spos + diff[vect];
            if ((c=box[cpos]) < 6) {          /* パネルがあれば */
                box[spos] = c;           /* cパネルを空き位置へ */
                box[cpos] = 0;
                adr2 = hash_func();     /* 格納アドレスを調べる */
                if (BACKET[adr2][0] == -1) {  /* 未登録なら登録 */
                    for (i=0; i<6; i++)
                        BACKET[adr2][i]=box[cnv[i]];
                    LINK[adr2] = adr1;
                    QUEUE[Qend++] = adr2;   /* キュー終端に登録 */
                    if (Qend == QSIZE) return -2; /* メモリ不足 */
                }
                if (adr2 == adrE) {             /* 解を発見した */
                    LINK[adr2] = adr1;
                    return 0;
                }
                box[spos] = 0;                /* 局面を元に戻す */
                box[cpos] = c;
            }
        }
    }
    return -1;   /* 解が無い */
}

/* ５パズルを解く */
int puzzle() {
    int i, adrS, adrE, next, prev=0;

    /* バケットとキュー初期化 */
    for (i=0; i<BSIZE; i++)
        BACKET[i][0] = -1;
    Qtop = Qend = 0;

    /* 開始局面登録 */
    for (i=0; i<6; i++)
        box[cnv[i]] = iobox[i];
    adrS = hash_func();
    for (i=0; i<6; i++)
        BACKET[adrS][i]=box[cnv[i]];
    QUEUE[Qend++] = adrS;

    /* 終了局面登録 */
    for (i=0; i<5; i++)
        box[cnv[i]] = i+1;
    box[cnv[5]] = 0;
    adrE = hash_func();
    for (i=0; i<6; i++)
        BACKET[adrE][i]=box[cnv[i]];

    /* 幅優先探索実行(失敗なら返値をそのまま返す) */
    if ((i=hsearch(adrE)) !=  0) return i;

    /* リンク方向を正順に書き換える(終端のリンク先を-1) */
    next = -1;
    for (i=adrE; i!=adrS; i=prev) {
        prev=LINK[i]; LINK[i]=next; next=i;
    }
    LINK[adrS]=next;
    return adrS;                  /* 開始アドレスを返す */
}

/* 主処理 */
void main() {
    int adr, adrS, i, cnt=0;

    adrS = puzzle();

    if (adrS == -2) {
        printf("メモリ不足");
    } else if (adrS == -1) {
        printf("解が無い");
    } else {
        /* 解の表示 */
        for (adr=adrS; adr!=-1; adr=LINK[adr]) {
            printf("%d 手目",cnt++);
            for (i=0; i<6; i++) {
                if (i%3 == 0) printf("\n");
                printf("%d ",BACKET[adr][i]);
            }
            printf("\n");
        }
    }
}