3-2 ぶどうの房パズル上級編

Javaアルゴリズムパズル

下の図での1〜15までの自然数の組み合わせを求めます。

ぶどうの房パズル

---

ソース

public final class budou2{

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

    //スタック
    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) {
        budou2 mi = new budou2();
        mi.main();
    }

    void main() {

        StackClass st = new StackClass();

        for (int i=1;i<=15;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<=15;i++){
                boolean connBy = true;

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

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

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

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

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

                  if (priInfo.ptr == 8)
                      if (Math.abs(priInfo.ValList[5]-priInfo.ValList[6]) != i) connBy = false;

                  if (priInfo.ptr == 9)
                      if (Math.abs(priInfo.ValList[6]-priInfo.ValList[7]) != i) connBy = false;

                  if (priInfo.ptr == 10)
                      if (Math.abs(priInfo.ValList[7]-priInfo.ValList[8]) != i) connBy = false;

                  if (priInfo.ptr == 11)
                      if (Math.abs(priInfo.ValList[9]-priInfo.ValList[10]) != i) connBy = false;

                  if (priInfo.ptr == 12)
                      if (Math.abs(priInfo.ValList[10]-priInfo.ValList[11]) != i) connBy = false;

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

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

                    st.push(willPush);
                }
            }

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

実行結果

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