8-27 油分け算3 {16,9,7}を{8,8,0}

問題

16リットル入りの容器に油がいっぱい入っており、
他に9リットルと7リットルの容器がある。
これらの容器だけを使って、油を正確に8リットルずつ分けるには
どうすればよいか。

￣torito＿ パズル遊びへの招待 １−７．油分け算

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Youki16;
        internal int Youki09;
        internal int Youki07;
        internal List<string> Log;
    }

    static void Main()
    {
        var que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Youki16 = 16;
        WillEnqueue.Youki09 = WillEnqueue.Youki07 = 0;
        WillEnqueue.Log = new List<string>();
        WillEnqueue.Log.Add(MakeOneLog(16, 0, 0));
        que.Enqueue(WillEnqueue);

        int MaxLevel = int.MaxValue;
        int AnswerCnt = 0;
        while (que.Count > 0) {
            JyoutaiDef Dequeued = que.Dequeue();
            if (MaxLevel < Dequeued.Log.Count) continue;

            if (Dequeued.Youki16 == 8 && Dequeued.Youki09 == 8) {
                Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);
                Dequeued.Log.ForEach(X => Console.WriteLine(X));
                if (MaxLevel > Dequeued.Log.Count)
                    MaxLevel = Dequeued.Log.Count;
                continue;
            }

            Action<int, int, int> EnqueSyori = (pYouki16, pYouki09, pYouki07) =>
            {
                WillEnqueue.Youki16 = pYouki16;
                WillEnqueue.Youki09 = pYouki09;
                WillEnqueue.Youki07 = pYouki07;

                string NewLog = MakeOneLog(pYouki16, pYouki09, pYouki07);
                if (Dequeued.Log.Contains(NewLog)) return;

                WillEnqueue.Log = new List<string>(Dequeued.Log);
                WillEnqueue.Log.Add(NewLog);
                que.Enqueue(WillEnqueue);
            };

            if (Dequeued.Youki16 > 0) {
                if (Dequeued.Youki09 < 9) {
                    int Aki = 9 - Dequeued.Youki09;
                    int Fill = Math.Min(Aki, Dequeued.Youki16);
                    EnqueSyori(Dequeued.Youki16 - Fill, Dequeued.Youki09 + Fill, Dequeued.Youki07);
                }
                if (Dequeued.Youki07 < 7) {
                    int Aki = 7 - Dequeued.Youki07;
                    int Fill = Math.Min(Aki, Dequeued.Youki16);
                    EnqueSyori(Dequeued.Youki16 - Fill, Dequeued.Youki09, Dequeued.Youki07 + Fill);
                }
            }
            if (Dequeued.Youki09 > 0) {
                if (Dequeued.Youki16 < 16) {
                    int Aki = 16 - Dequeued.Youki16;
                    int Fill = Math.Min(Aki, Dequeued.Youki09);
                    EnqueSyori(Dequeued.Youki16 + Fill, Dequeued.Youki09 - Fill, Dequeued.Youki07);
                }
                if (Dequeued.Youki07 < 7) {
                    int Aki = 7 - Dequeued.Youki07;
                    int Fill = Math.Min(Aki, Dequeued.Youki09);
                    EnqueSyori(Dequeued.Youki16, Dequeued.Youki09 - Fill, Dequeued.Youki07 + Fill);
                }
            }
            if (Dequeued.Youki07 > 0) {
                if (Dequeued.Youki16 < 16) {
                    int Aki = 16 - Dequeued.Youki16;
                    int Fill = Math.Min(Aki, Dequeued.Youki07);
                    EnqueSyori(Dequeued.Youki16 + Fill, Dequeued.Youki09, Dequeued.Youki07 - Fill);
                }
                if (Dequeued.Youki09 < 9) {
                    int Aki = 9 - Dequeued.Youki09;
                    int Fill = Math.Min(Aki, Dequeued.Youki07);
                    EnqueSyori(Dequeued.Youki16, Dequeued.Youki09 + Fill, Dequeued.Youki07 - Fill);
                }
            }
        }
    }

    static string MakeOneLog(int pYouki16, int pYouki09, int pYouki07)
    {
        return string.Format("容器16={0,2},容器9={1},容器7={2}", pYouki16, pYouki09, pYouki07);
    }
}

実行結果

解1を発見しました。
容器16=16,容器9=0,容器7=0
容器16= 7,容器9=9,容器7=0
容器16= 7,容器9=2,容器7=7
容器16=14,容器9=2,容器7=0
容器16=14,容器9=0,容器7=2
容器16= 5,容器9=9,容器7=2
容器16= 5,容器9=4,容器7=7
容器16=12,容器9=4,容器7=0
容器16=12,容器9=0,容器7=4
容器16= 3,容器9=9,容器7=4
容器16= 3,容器9=6,容器7=7
容器16=10,容器9=6,容器7=0
容器16=10,容器9=0,容器7=6
容器16= 1,容器9=9,容器7=6
容器16= 1,容器9=8,容器7=7
容器16= 8,容器9=8,容器7=0

解説

幅優先探索は、便利ですねぇ