ƒgƒbƒvƒy[ƒW‚É–ß‚é    ŽŸ‚ÌJavaƒAƒ‹ƒSƒŠƒYƒ€ƒpƒYƒ‹‚Ö    ‘O‚ÌJavaƒAƒ‹ƒSƒŠƒYƒ€ƒpƒYƒ‹‚Ö

3-6 15ƒpƒYƒ‹

JavaƒAƒ‹ƒSƒŠƒYƒ€ƒpƒYƒ‹

15ƒpƒYƒ‹‚ð‰ð‚«‚Ü‚·B


ƒ\[ƒX

public final class puzzle15{
    int maxLevel = 30; //‚‚³§ŒÀ

    class StackDataDef {
        int Level = 0;
        String Log = "";
        String priMove;
        int[][] ValList = {{ 1, 2, 3, 4,},  //1
                           { 0, 5, 6, 7,},  //2
                           { 9,10,11, 8,},  //3
                           {13,14,15,12,}}; //4;
    }

    //ƒXƒ^ƒbƒN
    class StackClass {
        int stackP;
        StackDataDef stackData[];

        StackClass(){
            stackP = 0;
            stackData = new StackDataDef[99999];
        }

        private void push(StackDataDef pushData,String addLog){
            stackData[stackP] = new StackDataDef();
            stackData[stackP].Level = pushData.Level+1;
            stackData[stackP].Log = pushData.Log+addLog;
            stackData[stackP].priMove = addLog;

            for(int Y=0;Y<=3;Y++)
                for(int X=0;X<=3;X++)
                    stackData[stackP].ValList[X][Y] = pushData.ValList[X][Y];
            stackP++;
        }

        private StackDataDef pop(){
            return stackData[--stackP];
        }
        boolean isEmpty(){ return stackP == 0; }
    }

    public static void main(String[] args) {
        puzzle15 mi = new puzzle15();
        mi.main();
    }

    void main() {
        StackClass st = new StackClass();

        StackDataDef willPush = new StackDataDef();

        int X=0; int Y=0;
        while(willPush.ValList[X][Y] !=0){
            if (++Y == 4){
                X++;Y=0;
            }
        }

        int saveVal;
        //¶‚̐”Žš‚ðˆÚ“®
        if (X!=0){
            saveVal = willPush.ValList[X-1][Y];
            willPush.ValList[X-1][Y] = 0;
            willPush.ValList[X][Y] = saveVal;

            st.push(willPush,"¨");
            willPush.ValList[X-1][Y] = saveVal;
            willPush.ValList[X][Y] = 0;
        }

        //‰E‚̐”Žš‚ðˆÚ“®
        if (X!=3){
            saveVal = willPush.ValList[X+1][Y];
            willPush.ValList[X+1][Y] = 0;
            willPush.ValList[X][Y] = saveVal;

            st.push(willPush,"©");
            willPush.ValList[X+1][Y] = saveVal;
            willPush.ValList[X][Y] = 0;
        }

        //ã‚̐”Žš‚ðˆÚ“®
        if (Y!=0){
            saveVal = willPush.ValList[X][Y-1];
            willPush.ValList[X][Y-1] = 0;
            willPush.ValList[X][Y] = saveVal;

            st.push(willPush,"«");
            willPush.ValList[X][Y-1] = saveVal;
            willPush.ValList[X][Y] = 0;
        }

        //‰º‚̐”Žš‚ðˆÚ“®
        if (Y!=3){
            saveVal = willPush.ValList[X][Y+1];
            willPush.ValList[X][Y+1] = 0;
            willPush.ValList[X][Y] = saveVal;

            st.push(willPush,"ª");
            willPush.ValList[X][Y+1] = saveVal;
            willPush.ValList[X][Y] = 0;
        }

        int ansCnt=0;
        while (st.isEmpty() == false){
            StackDataDef priInfo = st.pop();

            boolean isOK = true;
            int mustNumber=0;
            //‡ŠiŒo˜H‚È‚ç•\Ž¦
            for (X=0;X<=3;X++)
                for (Y=0;Y<=3;Y++){
                    ++mustNumber;
                    if (mustNumber!=16 && priInfo.ValList[X][Y] != mustNumber) isOK = false;
                }

            if (isOK){
                System.out.println("‰ð" + Integer.toString(++ansCnt));
                priInfo.Log = priInfo.Log.replaceAll("©","ã");
                priInfo.Log = priInfo.Log.replaceAll("¨","‰º");
                priInfo.Log = priInfo.Log.replaceAll("ª","¶");
                priInfo.Log = priInfo.Log.replaceAll("«","‰E");
                System.out.println(priInfo.Log);

                if (maxLevel > priInfo.Level) maxLevel = priInfo.Level; //‚‚³§ŒÀ’l‚ðXV
            }

            if (priInfo.Level >=maxLevel) continue; //‚‚³§ŒÀ

            X=Y=0;
            while(priInfo.ValList[X][Y] !=0){
                if (++Y == 4){
                    X++;Y=0;
                }
            }

            //¶‚̐”Žš‚ðˆÚ“®
            if (X!=0 && !priInfo.priMove.equals("©")){
                saveVal = priInfo.ValList[X-1][Y];
                priInfo.ValList[X-1][Y] = 0;
                priInfo.ValList[X][Y] = saveVal;

                st.push(priInfo,"¨");
                priInfo.ValList[X-1][Y] = saveVal;
                priInfo.ValList[X][Y] = 0;
            }

            //‰E‚̐”Žš‚ðˆÚ“®
            if (X!=3 && !priInfo.priMove.equals("¨")){
                saveVal = priInfo.ValList[X+1][Y];
                priInfo.ValList[X+1][Y] = 0;
                priInfo.ValList[X][Y] = saveVal;

                st.push(priInfo,"©");
                priInfo.ValList[X+1][Y] = saveVal;
                priInfo.ValList[X][Y] = 0;
            }

            //ã‚̐”Žš‚ðˆÚ“®
            if (Y!=0 && !priInfo.priMove.equals("ª")){
                saveVal = priInfo.ValList[X][Y-1];
                priInfo.ValList[X][Y-1] = 0;
                priInfo.ValList[X][Y] = saveVal;

                st.push(priInfo,"«");
                priInfo.ValList[X][Y-1] = saveVal;
                priInfo.ValList[X][Y] = 0;
            }

            //‰º‚̐”Žš‚ðˆÚ“®
            if (Y!=3 && !priInfo.priMove.equals("«")){
                saveVal = priInfo.ValList[X][Y+1];
                priInfo.ValList[X][Y+1] = 0;
                priInfo.ValList[X][Y] = saveVal;

                st.push(priInfo,"ª");
                priInfo.ValList[X][Y+1] = saveVal;
                priInfo.ValList[X][Y] = 0;
            }
        }
    }
}


ŽÀsŒ‹‰Ê

‰ð1
¶¶¶ã‰E‰E‰Eã¶¶¶‰º‰Eã¶‰º‰Eã¶‰º‰Eã‰E‰E‰º¶¶¶ã
‰ð2
¶¶¶ã‰E‰E‰Eã¶¶¶‰º‰Eã‰E‰E‰º¶ã¶‰º¶ã‰E‰E‰º¶¶ã
‰ð3
¶¶¶ã‰E‰E‰Eã¶¶‰º¶ã‰E‰E‰E‰º¶ã¶¶‰º‰Eã‰E‰º¶¶ã
‰ð4
¶¶¶ã‰E‰E‰Eã¶¶‰º¶ã‰E‰º¶ã‰E‰º¶ã‰E‰E‰E‰º¶¶¶ã
‰ð5
¶¶¶ã‰E‰E‰Eã¶¶‰º¶‰º‰Eãã‰E‰E‰º¶¶‰º¶ãã
‰ð6
¶¶¶ã‰E‰E‰Eã¶‰º¶¶ã‰E‰º‰Eã‰E‰º¶¶ã¶
‰ð7
¶¶¶ã‰E‰E‰Eã¶‰º¶‰º‰Eãã‰E‰º¶‰º¶ã¶ã
‰ð8
¶¶¶ã‰E‰E‰Eã¶‰º‰Eã¶‰º‰Eã¶‰º¶¶ã
‰ð9
¶¶¶ã‰E‰E‰E‰º¶ã‰E‰º¶ã‰E‰º¶ã¶¶ã
‰ð10
¶¶¶ã‰E‰Eã¶‰º¶‰º‰Eãã‰E‰º¶‰º¶ãã
‰ð11
¶¶¶ã‰E‰Eã¶‰º‰Eã¶‰º‰Eã¶‰º¶ã
‰ð12
¶¶¶ã‰E‰E‰º¶ã¶ã‰E‰º‰º‰Eã¶ã¶
‰ð13
¶¶¶ã‰E‰E‰º¶ã‰E‰º¶ã‰E‰º¶ã¶ã
‰ð14
¶¶¶ã‰Eã¶‰º‰Eã¶‰º‰Eã¶
‰ð15
¶¶¶ãã