8-30 川渡り問題1 農夫と狼とヤギとキャベツ

問題

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

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

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

旅人と狼と山羊とキャベツ : クイズ＆パズルの部屋「Quizzical Days.」

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Level;
        internal string MoveLog;
        internal bool IsKyabetuLeft;
        internal bool IsHitujiLeft;
        internal bool IsOOkamiLeft;
        internal bool IsNouhuLeft;

        internal void Init()
        {
            IsKyabetuLeft = IsHitujiLeft = IsOOkamiLeft = IsNouhuLeft = true;
        }
    }

    static void Main()
    {
        var Jyoutai = new JyoutaiDef();
        Jyoutai.Init();

        var que = new Queue<JyoutaiDef>();
        que.Enqueue(Jyoutai);

        int AnswerLevel = int.MaxValue;
        while (que.Count != 0) {
            Jyoutai = que.Dequeue();
            //Console.WriteLine(jyoutai.MoveLog);
            if (++Jyoutai.Level > AnswerLevel) continue;

            if (!Jyoutai.IsKyabetuLeft
             && !Jyoutai.IsHitujiLeft
             && !Jyoutai.IsOOkamiLeft) {
                AnswerLevel = Jyoutai.Level;
                Console.WriteLine("Answer");
                Console.WriteLine(Jyoutai.MoveLog);
                continue;
            }

            JyoutaiDef Saved;
            if (Jyoutai.IsNouhuLeft) {
                Saved = Jyoutai;
                Saved.IsNouhuLeft = false;
                Saved.MoveLog += "何も連れずに右,";
                if (IsValid(Saved)) que.Enqueue(Saved);

                if (Jyoutai.IsKyabetuLeft) {
                    Saved = Jyoutai;
                    Saved.IsKyabetuLeft = Saved.IsNouhuLeft = false;
                    Saved.MoveLog += "キャベツを連れて右,";
                    if (IsValid(Saved)) que.Enqueue(Saved);
                }
                if (Jyoutai.IsHitujiLeft) {
                    Saved = Jyoutai;
                    Saved.IsHitujiLeft = Saved.IsNouhuLeft = false;
                    Saved.MoveLog += "羊を連れて右,";
                    if (IsValid(Saved)) que.Enqueue(Saved);
                }
                if (Jyoutai.IsOOkamiLeft) {
                    Saved = Jyoutai;
                    Saved.IsOOkamiLeft = Saved.IsNouhuLeft = false;
                    Saved.MoveLog += "狼を連れて右,";
                    if (IsValid(Saved)) que.Enqueue(Saved);
                }
            }
            else {
                Saved = Jyoutai;
                Saved.IsNouhuLeft = true;
                Saved.MoveLog += "何も連れずに左,";
                if (IsValid(Saved)) que.Enqueue(Saved);

                if (Jyoutai.IsKyabetuLeft == false) {
                    Saved = Jyoutai;
                    Saved.IsKyabetuLeft = Saved.IsNouhuLeft = true;
                    Saved.MoveLog += "キャベツを連れて左,";
                    if (IsValid(Saved)) que.Enqueue(Saved);
                }

                if (Jyoutai.IsHitujiLeft == false) {
                    Saved = Jyoutai;
                    Saved.IsHitujiLeft = Saved.IsNouhuLeft = true;
                    Saved.MoveLog += "羊を連れて左,";
                    if (IsValid(Saved)) que.Enqueue(Saved);
                }

                if (Jyoutai.IsOOkamiLeft == false) {
                    Saved = Jyoutai;
                    Saved.IsOOkamiLeft = Saved.IsNouhuLeft = true;
                    Saved.MoveLog += "狼を連れて左,";
                    if (IsValid(Saved)) que.Enqueue(Saved);
                }
            }
        }
    }

    static bool IsValid(JyoutaiDef p)
    {
        if (p.IsNouhuLeft && !p.IsKyabetuLeft && !p.IsHitujiLeft) return false;
        if (p.IsNouhuLeft && !p.IsHitujiLeft && !p.IsOOkamiLeft) return false;
        if (!p.IsNouhuLeft && p.IsKyabetuLeft && p.IsHitujiLeft) return false;
        if (!p.IsNouhuLeft && p.IsHitujiLeft && p.IsOOkamiLeft) return false;
        return true;
    }
}

実行結果

Answer
羊を連れて右,何も連れずに左,キャベツを連れて右,羊を連れて左,狼を連れて右,何も連れずに左,羊を連れて右,
Answer
羊を連れて右,何も連れずに左,狼を連れて右,羊を連れて左,キャベツを連れて右,何も連れずに左,羊を連れて右,

解説

Queueジェネリックは強力ですねぇ