3-4 連環の数 上級編

Javaアルゴリズムパズル

連なった円の中に１から始まる、連続した自然数を入れていきます。
ただし、円の重なった部分には、その左右に入っている数の和を入れてください

円が８個の場合、１から１５までの数を入れてみてください。

ソース

public final class renjyu15{
    class StackDataDef {
        int[] ValList = new int[15];
    }

    //スタック
    class StackClass {
        int stackP;
        StackDataDef stackData[];

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

        private void push(StackDataDef pushData){
            stackData[stackP] = new StackDataDef();

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

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

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

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

        StackDataDef willPush = new StackDataDef();

        int X=0;

        for (int i=1;i<=15;i++){ //Start With句
            willPush.ValList[X] = i;
            if (isValid(willPush.ValList)) st.push(willPush);
        }

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

            boolean isOK = true;
            //合格経路なら表示
            for (X=0;X<=14;X++)
                if (priInfo.ValList[X] == 0)
                    isOK = false;

            if (isOK){
                System.out.println("解" + Integer.toString(++ansCnt));
                String willOut ="";
                for(X=0;X<=14;X++)
                    willOut += priInfo.ValList[X] + ",";

                System.out.println(willOut); willOut="";
                continue;
            }

            X=0;
            while(X!= 15 && priInfo.ValList[X] !=0) X++;

            if (X==15){
                st.push(priInfo);
                continue;
            }

            for (int i=1;i<=15;i++){ //connect by句
                priInfo.ValList[X] = i;
                if (isValid(priInfo.ValList)) st.push(priInfo);
            }
        }
    }

    private boolean isValid(int[] ValList){
        int[] counter = new int[16];
        //ユニークチェック
        for (int LoopX=0;LoopX<=14;LoopX++)
            counter[ValList[LoopX]]++;
        for (int i=1;i<=15;i++)
            if (counter[i] >=2) return false;

        //和のチェック
        if (ValList[2]  != 0 && ValList[1] != ValList[0] + ValList[2])
            return false;
        if (ValList[4]  != 0 && ValList[3] != ValList[2] + ValList[4])
            return false;
        if (ValList[6]  != 0 && ValList[5] != ValList[4] + ValList[6])
            return false;
        if (ValList[8]  != 0 && ValList[7] != ValList[6] + ValList[8])
            return false;
        if (ValList[10] != 0 && ValList[9] != ValList[8] + ValList[10])
            return false;
        if (ValList[12] != 0 && ValList[11] != ValList[10] + ValList[12])
            return false;
        if (ValList[14] != 0 && ValList[13] != ValList[12] + ValList[14])
            return false;

        return true;
    }
}

実行結果

解1
14,15,1,12,11,13,2,7,5,8,3,9,6,10,4,
解2
14,15,1,12,11,13,2,6,4,9,5,8,3,10,7,
解3
14,15,1,11,10,13,3,8,5,12,7,9,2,6,4,
以下略