3-9 川渡り 3匹の狼と小鳥

Javaアルゴリズムパズル

3匹ずつの狼と小鳥を、向こう岸に渡す。

・いかだに乗れるのは2匹まで
・1匹も乗ってないと動かない
・どちらの岸でも狼が小鳥の数より大きくなると、
  小鳥が食べられて失敗する

ソース

public final class ookami_kotori{
    int maxLevel = 20; //高さ制限

    class StackDataDef {
        int pHune  =0;
        int OOkami =3;
        int Kotori =3;

        int Level = 0;
        String Log ="";
    }

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

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

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

            stackData[stackP].pHune   = pushData.pHune;
            stackData[stackP].OOkami  = pushData.OOkami;
            stackData[stackP].Kotori  = pushData.Kotori;
            stackData[stackP].Level   = pushData.Level;

            String willWrite ="(";
            if (pushData.OOkami == 3) willWrite += "狼3";
            if (pushData.OOkami == 2) willWrite += "狼2";
            if (pushData.OOkami == 1) willWrite += "狼";
            if (pushData.Kotori == 3) willWrite += "鳥3";
            if (pushData.Kotori == 2) willWrite += "鳥2";
            if (pushData.Kotori == 1) willWrite += "鳥";

            if (pushData.pHune == 0) willWrite += "←";
            else willWrite += "→";

            if (pushData.OOkami == 0) willWrite += "狼3";
            if (pushData.OOkami == 1) willWrite += "狼2";
            if (pushData.OOkami == 2) willWrite += "狼";
            if (pushData.Kotori == 0) willWrite += "鳥3";
            if (pushData.Kotori == 1) willWrite += "鳥2";
            if (pushData.Kotori == 2) willWrite += "鳥";
            willWrite +=")";

            stackData[stackP].Log = pushData.Log + willWrite;

            stackP++;
        }

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

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

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

        //Start With句
        willPush.Level = 1;
        willPush.pHune = 1;
        willPush.OOkami = 2; willPush.Kotori = 3; st.push(willPush);
        willPush.OOkami = 1; willPush.Kotori = 3; st.push(willPush);
        willPush.OOkami = 2; willPush.Kotori = 2; st.push(willPush);

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

            int queenCnt = 0;
            //合格経路なら表示
            if (priInfo.OOkami == 0 && priInfo.Kotori == 0){
                System.out.println("解" + Integer.toString(++ansCnt));
                System.out.println(priInfo.Log);

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

            if (++priInfo.Level >=maxLevel) continue; //高さ制限

            if (priInfo.pHune ==0){
                priInfo.pHune = 1;

                if (priInfo.OOkami >= 2){
                    priInfo.OOkami -=2;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.OOkami +=2;
                }

                if (priInfo.OOkami >= 1){
                    priInfo.OOkami -=1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.OOkami +=1;
                }

                if (priInfo.Kotori >= 2){
                    priInfo.Kotori -=2;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.Kotori +=2;
                }

                if (priInfo.Kotori >= 1){
                    priInfo.Kotori -=1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.Kotori +=1;
                }

                if (priInfo.OOkami >= 1 && priInfo.Kotori >= 1){
                    priInfo.OOkami -=1; priInfo.Kotori -=1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.OOkami +=1; priInfo.Kotori -=1;
                }
            }
            else {
                priInfo.pHune = 0;

                if (priInfo.OOkami <= 1){
                    priInfo.OOkami +=2;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.OOkami -=2;
                }

                if (priInfo.OOkami <= 2){
                    priInfo.OOkami +=1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.OOkami -=1;
                }

                if (priInfo.Kotori <= 1){
                    priInfo.Kotori +=2;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.Kotori -=2;
                }

                if (priInfo.Kotori <= 2){
                    priInfo.Kotori +=1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.Kotori -=1;
                }

                if (priInfo.OOkami <= 2 && priInfo.Kotori <= 2){
                    priInfo.OOkami +=1; priInfo.Kotori +=1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.OOkami -=1; priInfo.Kotori -=1;
                }
            }
        }
    }

    private boolean isValid(StackDataDef StackData){
        if (StackData.Kotori != 0 && StackData.Kotori < StackData.OOkami) return false;
        if (StackData.Kotori != 3 && (3-StackData.Kotori) < (3-StackData.OOkami)) return false;

        return true;
    }
}

実行結果

解5
(狼2鳥2→狼鳥)
(狼2鳥3←狼)
(鳥3→狼3)
(狼鳥3←狼2)
(狼鳥→狼2鳥2)
(狼2鳥2←狼鳥)
(狼2→狼鳥3)
(狼3←鳥3)
(狼→狼2鳥3)
(狼鳥←狼2鳥2)
(→狼3鳥3)