3-1 ぶどうの房パズル初級編

Javaアルゴリズムパズル

下の図に１〜３までの自然数を１つずつ入れるパズルです。
下の段にある○の中には、すぐ上にある２つの○の中にある数字の差が入ります。
同じ数字は１回しか使えません。

正解例はこうなります


以上をふまえて、下の図での1〜6までの自然数の組み合わせを求めます。

ぶどうの房パズル

ソース

public final class budou1{

    //スタックで使うデータ
    class StackDataDef {
        int ptr;
        int[] ValList;
        StackDataDef(){
            this.ptr = 0;
            this.ValList = new int[6];
        }
    };

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

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

        private void push(StackDataDef pushData){
            stackData[stackP++] = pushData;
            //System.out.println("push" + pushData.ptr + "," + pushData.ValList[pushData.ptr]);
        }
        private StackDataDef pop(){
            //System.out.println("pop");
            return stackData[--stackP];
        }
        boolean isEmpty(){ return stackP == 0; }
    }

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

    void main() {

        StackClass st = new StackClass();

        for (int i=1;i<=6;i++){ //Start With句
            StackDataDef willPush = new StackDataDef();
            willPush.ValList[0] = i;
            st.push(willPush);
        }

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

            for (int i=1;i<=6;i++){
                boolean connBy = true;

                for (int J=0;J<= priInfo.ptr;J++)
                    if (priInfo.ValList[J] == i) connBy = false;

                if (priInfo.ptr == 2)
                    if (Math.abs(priInfo.ValList[0]-priInfo.ValList[1]) != i)
                        connBy = false;

                if (priInfo.ptr == 3)
                    if (Math.abs(priInfo.ValList[1]-priInfo.ValList[2]) != i)
                        connBy = false;

                if (priInfo.ptr == 4)
                    if (Math.abs(priInfo.ValList[3]-priInfo.ValList[4]) != i)
                        connBy = false;

                if (connBy){ //connect by句
                    StackDataDef willPush = new StackDataDef();
                    willPush.ptr = priInfo.ptr+1;
                    for (int WK=0;WK <= 5;WK++)
                        willPush.ValList[WK] = priInfo.ValList[WK];
                    willPush.ValList[willPush.ptr] = i;

                    st.push(willPush);
                }
            }

            //合格経路なら表示
            if (priInfo.ptr==5){
                String willOut ="";
                for (int WK=0;WK <= 5;WK++)
                    willOut += Integer.toString(priInfo.ValList[WK]) + ",";
                System.out.println(willOut);
            }
        }
    }
}

実行結果

6,2,5,4,3,1,
6,1,4,5,3,2,
5,6,2,1,4,3,
5,2,6,3,4,1,
4,6,1,2,5,3,
4,1,6,3,5,2,
2,6,5,4,1,3,
1,6,4,5,2,3,