8-32 川渡り問題3 5匹の狼と小鳥

問題

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

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

渡船者に祝福を (宣教師5人の場合) : クイズ＆パズルの部屋「Quizzical Days.」

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Level;
        internal List<string> LogList;
        internal int KotoriLeft;
        internal int OOkamiLeft;
        internal bool IsIkadaLeft;

        internal void Init()
        {
            Level = 0;
            LogList = new List<string>();
            KotoriLeft = OOkamiLeft = 5;
            IsIkadaLeft = true;
            AddOneLog();
        }

        internal bool AddOneLog()
        {
            var sb = new System.Text.StringBuilder();
            sb.AppendFormat("鳥{0}", KotoriLeft);
            sb.AppendFormat("狼{0}", OOkamiLeft);
            sb.Append(IsIkadaLeft ? " 筏 川川川 " : " 川川川 筏 ");
            sb.AppendFormat("鳥{0}", 5 - KotoriLeft);
            sb.AppendFormat("狼{0}", 5 - OOkamiLeft);

            string wkStr = sb.ToString();
            if (LogList.Contains(wkStr)) return false;
            LogList.Add(wkStr);
            return true;
        }

        internal void PrintLog()
        {
            for (int I = 0; I <= LogList.Count - 1; I++)
                Console.WriteLine("レベル{0,2} {1}", I, LogList[I]);
        }
    }

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

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

        int AnswerLevel = int.MaxValue;
        int AnswerCnt = 0;
        while (que.Count != 0) {
            Jyoutai = que.Dequeue();
            if (++Jyoutai.Level > AnswerLevel) continue;

            if (Jyoutai.IsIkadaLeft == false
             && Jyoutai.KotoriLeft == 0
             && Jyoutai.OOkamiLeft == 0) {
                Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);
                Jyoutai.PrintLog();
                AnswerLevel = Jyoutai.Level;
                continue;
            }

            Action<int, int> EnqueueSyori = (pKotoriLeft, pOOkamiLeft) =>
            {
                JyoutaiDef WillEnqueue;
                WillEnqueue.Level = Jyoutai.Level;
                WillEnqueue.LogList = new List<string>(Jyoutai.LogList);
                WillEnqueue.KotoriLeft = pKotoriLeft;
                WillEnqueue.OOkamiLeft = pOOkamiLeft;
                WillEnqueue.IsIkadaLeft = !(Jyoutai.IsIkadaLeft);
                if (WillEnqueue.AddOneLog() && IsValid(WillEnqueue)) que.Enqueue(WillEnqueue);
            };

            if (Jyoutai.IsIkadaLeft) {
                if (Jyoutai.KotoriLeft >= 3) EnqueueSyori(Jyoutai.KotoriLeft - 3, Jyoutai.OOkamiLeft);
                if (Jyoutai.OOkamiLeft >= 3) EnqueueSyori(Jyoutai.KotoriLeft, Jyoutai.OOkamiLeft - 3);
                if (Jyoutai.KotoriLeft >= 2) EnqueueSyori(Jyoutai.KotoriLeft - 2, Jyoutai.OOkamiLeft);
                if (Jyoutai.OOkamiLeft >= 2) EnqueueSyori(Jyoutai.KotoriLeft, Jyoutai.OOkamiLeft - 2);
                if (Jyoutai.KotoriLeft >= 1) EnqueueSyori(Jyoutai.KotoriLeft - 1, Jyoutai.OOkamiLeft);
                if (Jyoutai.OOkamiLeft >= 1) EnqueueSyori(Jyoutai.KotoriLeft, Jyoutai.OOkamiLeft - 1);

                if (Jyoutai.KotoriLeft >= 1 && Jyoutai.OOkamiLeft >= 1) {
                    EnqueueSyori(Jyoutai.KotoriLeft - 1, Jyoutai.OOkamiLeft - 1);
                }
                if (Jyoutai.KotoriLeft >= 2 && Jyoutai.OOkamiLeft >= 1) {
                    EnqueueSyori(Jyoutai.KotoriLeft - 2, Jyoutai.OOkamiLeft - 1);
                }
                if (Jyoutai.KotoriLeft >= 1 && Jyoutai.OOkamiLeft >= 2) {
                    EnqueueSyori(Jyoutai.KotoriLeft - 1, Jyoutai.OOkamiLeft - 2);
                }
            }
            else {
                if (5 - Jyoutai.KotoriLeft >= 3) EnqueueSyori(Jyoutai.KotoriLeft + 3, Jyoutai.OOkamiLeft);
                if (5 - Jyoutai.OOkamiLeft >= 3) EnqueueSyori(Jyoutai.KotoriLeft, Jyoutai.OOkamiLeft + 3);
                if (5 - Jyoutai.KotoriLeft >= 2) EnqueueSyori(Jyoutai.KotoriLeft + 2, Jyoutai.OOkamiLeft);
                if (5 - Jyoutai.OOkamiLeft >= 2) EnqueueSyori(Jyoutai.KotoriLeft, Jyoutai.OOkamiLeft + 2);
                if (5 - Jyoutai.KotoriLeft >= 1) EnqueueSyori(Jyoutai.KotoriLeft + 1, Jyoutai.OOkamiLeft);
                if (5 - Jyoutai.OOkamiLeft >= 1) EnqueueSyori(Jyoutai.KotoriLeft, Jyoutai.OOkamiLeft + 1);

                if (5 - Jyoutai.KotoriLeft >= 1 && 5 - Jyoutai.OOkamiLeft >= 1) {
                    EnqueueSyori(Jyoutai.KotoriLeft + 1, Jyoutai.OOkamiLeft + 1);
                }
                if (5 - Jyoutai.KotoriLeft >= 2 && 5 - Jyoutai.OOkamiLeft >= 1) {
                    EnqueueSyori(Jyoutai.KotoriLeft + 2, Jyoutai.OOkamiLeft + 1);
                }
                if (5 - Jyoutai.KotoriLeft >= 1 && 5 - Jyoutai.OOkamiLeft >= 2) {
                    EnqueueSyori(Jyoutai.KotoriLeft + 1, Jyoutai.OOkamiLeft + 2);
                }
            }
        }
    }

    static bool IsValid(JyoutaiDef pJyoutai)
    {
        if (pJyoutai.KotoriLeft >= 1 &&
            pJyoutai.KotoriLeft < pJyoutai.OOkamiLeft) return false;
        if ((5 - pJyoutai.KotoriLeft) >= 1 &&
            (5 - pJyoutai.KotoriLeft) < (5 - pJyoutai.OOkamiLeft)) return false;

        return true;
    }
}

実行結果

省略
解25を発見しました。
レベル 0 鳥5狼5 筏 川川川 鳥0狼0
レベル 1 鳥4狼4 川川川 筏 鳥1狼1
レベル 2 鳥5狼4 筏 川川川 鳥0狼1
レベル 3 鳥5狼1 川川川 筏 鳥0狼4
レベル 4 鳥5狼2 筏 川川川 鳥0狼3
レベル 5 鳥2狼2 川川川 筏 鳥3狼3
レベル 6 鳥3狼3 筏 川川川 鳥2狼2
レベル 7 鳥0狼3 川川川 筏 鳥5狼2
レベル 8 鳥0狼4 筏 川川川 鳥5狼1
レベル 9 鳥0狼2 川川川 筏 鳥5狼3
レベル10 鳥0狼3 筏 川川川 鳥5狼2
レベル11 鳥0狼0 川川川 筏 鳥5狼5

解説

共通のEnQueue処理をActionデリゲートでまとめてます。