トップページに戻る    次のJavaアルゴリズムパズルへ    前のJavaアルゴリズムパズルへ

3-6 15パズル

Javaアルゴリズムパズル

15パズルを解きます。


ソース

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;
    }

    //スタック
    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;
        }

        //右の数字を移動
        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;
            //合格経路なら表示
            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("↓","右");
                System.out.println(priInfo.Log);

                if (maxLevel > priInfo.Level) maxLevel = priInfo.Level; //高さ制限値を更新
            }

            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;
            }

            //右の数字を移動
            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;
            }
        }
    }
}


実行結果

解1
左左左上右右右上左左左下右上左下右上左下右上右右下左左左上
解2
左左左上右右右上左左左下右上右右下左上左下左上右右下左左上
解3
左左左上右右右上左左下左上右右右下左上左左下右上右下左左上
解4
左左左上右右右上左左下左上右下左上右下左上右右右下左左左上
解5
左左左上右右右上左左下左下右上上右右下左左下左上上
解6
左左左上右右右上左下左左上右下右上右下左左上左
解7
左左左上右右右上左下左下右上上右下左下左上左上
解8
左左左上右右右上左下右上左下右上左下左左上
解9
左左左上右右右下左上右下左上右下左上左左上
解10
左左左上右右上左下左下右上上右下左下左上上
解11
左左左上右右上左下右上左下右上左下左上
解12
左左左上右右下左上左上右下下右上左上左
解13
左左左上右右下左上右下左上右下左上左上
解14
左左左上右上左下右上左下右上左
解15
左左左上上