import java.applet.Applet;
import java.awt.*;

public class five extends Applet implements Runnable {

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

int iobox[] = new int[6];           /* 問題面(表示局面)   */

int BACKET[][] = new int[BSIZE][6]; /* バケット(局面格納) */
int LINK[] = new int[BSIZE];        /* バケット(リンク元) */
int QUEUE[] = new int[QSIZE];       /* キュー(待ち行列)   */
int 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;
    long num = 0;

    /* 局面を数値化しハッシュ値を求める */
    for (i=0; i<6; i++)
        num = (num << 4) + box[cnv[i]];
    hash = (int)(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=0, 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;
    }
    return next;               /* 1手目のアドレスを返す */
}

/*----------------------------------------------------*/
int   mode = 0;
int   DispAddress = -1;
int   DispTesu = 0;

/* かき混ぜる */
void kakimaze() {
    int i, a, b, n;

    for (i=0; i<5; i++)
        iobox[i] = i+1;
    iobox[5] = 0;

    for (i=0; i<18; i++) {
        do {
            a = (int)(Math.random()*6);
        } while (iobox[a] == 0);
        do {
            b = (int)(Math.random()*6);
        } while (a==b || iobox[b] == 0);
        n=iobox[a]; iobox[a]=iobox[b]; iobox[b]=n;
    }

    DispAddress = -1;
    DispTesu = 0;
    repaint();
}

/* 次の局面表示の準備 */
void moving() {
    int i;

    for (i=0; i<6; i++)
        iobox[i] = BACKET[DispAddress][i];
    DispTesu++;
    DispAddress=LINK[DispAddress];
    repaint();
}

/*----------------------------------------------------*/

Image    buffer;
Graphics grf;
Thread   animation = null;
long     sleepTime = 400;

public void init() {
    setBackground(Color.gray);
    setLayout(new BorderLayout());
    Panel psouth = new Panel();
    psouth.add(new Button("click"));
    add("South", psouth);

    buffer = createImage(181,151);
    grf = buffer.getGraphics();

    kakimaze();
}

public void start() {
    if (animation == null) {
        animation = new Thread(this);
        animation.start();
    }
}

public void run() {
    while (true) {
        if (DispAddress >= 0) {
            moving();
        }
        try {
            animation.sleep(sleepTime);
        } catch (InterruptedException e) {}
    }
}

public void stop() {
    if (animation != null) {
        animation.stop();
        animation = null;
    }
}

public void update(Graphics g) {
    paint(grf);
    g.drawImage(buffer,0,0,this);
}

public void paint(Graphics g) {
    int x, y, n;

    g.setColor(Color.white);
    g.fillRect(0,0,180,120);
    g.setColor(Color.gray);
    g.fillRect(0,121,181,150);

    g.setFont(new Font("Helvetica",Font.BOLD,48));
    for (y=0; y<2; y++)
    for (x=0; x<3; x++) {
        g.setColor(Color.black);
        g.drawRect(x*60,y*60,60,60);
        n = iobox[y*3+x];
        if (n != 0) {
            g.drawString(Integer.toString(n),x*60+15,y*56+50);
        } else {
            g.setColor(Color.gray);
            g.fillRect(x*60+1,y*60+1,59,59);
        }
    }
    g.setColor(Color.black);
    g.setFont(new Font("Helvetica",Font.BOLD,12));
    g.drawString("TESU = "+Integer.toString(DispTesu),50,142);
}

public boolean action(Event e, Object arg) {
    if (DispAddress >= 0) return false;
    if ("click".equals(arg)) {
        if (mode == 0) {
            mode = 1;
            DispAddress = puzzle();
        } else {
            mode = 0;
            kakimaze();
        }
    }
    return true;
}
}