3-8 川渡り 農夫と狼とヤギとキャベツ

Javaアルゴリズムパズル

この問題は、8世紀にカンタベリーの大主教が提示した問題といわれている。

オオカミとヤギを連れキャベツを持った農夫が川岸にいる。
川にはボートがあるが農夫の他には動物一頭かキャベツ一個しか乗せられない。
農夫がいなければオオカミはヤギを襲うし、ヤギはキャベツを食べてしまう。

すべてを無事に対岸に渡すにはどうしたらよいか?

ソース

public final class kawawatari{

    class StackDataDef {
        int pNouhu   =0;
        int pOOkami  =0;
        int pYagi    =0;
        int pKyabetu =0;

        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].pNouhu   = pushData.pNouhu;
            stackData[stackP].pOOkami  = pushData.pOOkami;
            stackData[stackP].pYagi    = pushData.pYagi;
            stackData[stackP].pKyabetu = pushData.pKyabetu;
            stackData[stackP].Level    = pushData.Level;

            String willWrite ="(";
            if (pushData.pNouhu   == 0) willWrite += "人";
            if (pushData.pOOkami  == 0) willWrite += "狼";
            if (pushData.pYagi    == 0) willWrite += "ヤ";
            if (pushData.pKyabetu == 0) willWrite += "キ";
            willWrite +="■";
            if (pushData.pNouhu   == 1) willWrite += "人";
            if (pushData.pOOkami  == 1) willWrite += "狼";
            if (pushData.pYagi    == 1) willWrite += "ヤ";
            if (pushData.pKyabetu == 1) 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) {
        kawawatari mi = new kawawatari();
        mi.main();
    }

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

        //Start With句
        willPush.Level = 1;
        willPush.pNouhu = 1;
        willPush.pOOkami = 0; willPush.pYagi = 0;willPush.pKyabetu = 1; st.push(willPush);
        willPush.pOOkami = 0; willPush.pYagi = 1;willPush.pKyabetu = 0; st.push(willPush);
        willPush.pOOkami = 1; willPush.pYagi = 0;willPush.pKyabetu = 0; st.push(willPush);

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

            //合格経路なら表示
            if (priInfo.pNouhu == 1 && priInfo.pOOkami == 1 && priInfo.pYagi == 1 && priInfo.pKyabetu == 1){
                System.out.println("解" + Integer.toString(++ansCnt));
                System.out.println(priInfo.Log);
                continue;
            }

            if (++priInfo.Level == 6) continue;

            if (priInfo.pNouhu ==0){
                priInfo.pNouhu = 1;
                if (isValid(priInfo)) st.push(priInfo);

                if (priInfo.pOOkami == 0){
                    priInfo.pOOkami = 1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.pOOkami = 0;
                }
                if (priInfo.pYagi == 0){
                    priInfo.pYagi = 1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.pYagi = 0;
                }
                if (priInfo.pKyabetu == 0){
                    priInfo.pKyabetu = 1;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.pKyabetu = 0;
                }
            }
            else {
                priInfo.pNouhu = 0;
                if (isValid(priInfo)) st.push(priInfo);

                if (priInfo.pOOkami == 1){
                    priInfo.pOOkami = 0;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.pOOkami = 1;
                }
                if (priInfo.pYagi == 1){
                    priInfo.pYagi = 0;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.pYagi = 1;
                }
                if (priInfo.pKyabetu == 1){
                    priInfo.pKyabetu = 0;
                    if (isValid(priInfo)) st.push(priInfo);
                    priInfo.pKyabetu = 1;
                }
            }
        }
    }

    private boolean isValid(StackDataDef StackData){
        if (StackData.pNouhu == 0 && StackData.pOOkami==1 && StackData.pYagi == 1) return false;
        if (StackData.pNouhu == 1 && StackData.pOOkami==0 && StackData.pYagi == 0) return false;

        if (StackData.pNouhu == 0 && StackData.pYagi==1 && StackData.pKyabetu == 1) return false;
        if (StackData.pNouhu == 1 && StackData.pYagi==0 && StackData.pKyabetu == 0) return false;

        return true;
    }
}

実行結果

解1
(ヤキ■人狼)(人ヤキ■狼)(ヤ■人狼キ)(人ヤ■狼キ)(■人狼ヤキ)
解2
(狼ヤ■人キ)(人狼ヤ■キ)(ヤ■人狼キ)(人ヤ■狼キ)(■人狼ヤキ)