8-11 カエルの引越し

問題

池の左側にアマガエルが、右側にヒキガエルが3匹ずつ並んでいる。
このカエルのいる場所をそっくり入れ替えてほしい。

カエルは前に飛ぶことしかできないが、1匹だけなら前にいるカエルを飛び越すことができる。
また、1枚の葉に同時に2匹以上のカエルが乗ることはできない。

さて、すべてのカエルを入れ替えるにはどうすればよいだろうか?

カエルの引越し : クイズ＆パズルの部屋「Quizzical Days.」

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    private enum MasuDef
    {
        Kuuhaku = 0,
        Ama = 1,
        Hiki = 2
    }

    private struct JyoutaiDef
    {
        internal MasuDef[] MasuArr;
        internal List<MasuDef[]> Log;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();

        JyoutaiDef WillPush;
        WillPush.MasuArr = new MasuDef[] {
            MasuDef.Ama, MasuDef.Ama,MasuDef.Ama,
            MasuDef.Kuuhaku,
            MasuDef.Hiki,MasuDef.Hiki,MasuDef.Hiki};
        WillPush.Log = new List<MasuDef[]>() { WillPush.MasuArr };
        stk.Push(WillPush);

        int MaxLevel = (6 + 5 + 4) * 2;
        int AnswerCnt = 0;

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();
            if (MaxLevel < Popped.Log.Count) continue;

            MasuDef[] AnswerArr = new MasuDef[] {
                MasuDef.Hiki, MasuDef.Hiki,MasuDef.Hiki,
                MasuDef.Kuuhaku,
                MasuDef.Ama,MasuDef.Ama,MasuDef.Ama};

            if (Popped.MasuArr.SequenceEqual(AnswerArr)) {
                Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);

                PrintLog(Popped.Log);

                if (MaxLevel > Popped.Log.Count)
                    MaxLevel = Popped.Log.Count;
                continue;
            }

            int IndZero = Array.IndexOf<MasuDef>(Popped.MasuArr, MasuDef.Kuuhaku);

            Action<int> PushSyori = (IndChanged) =>
            {
                WillPush.MasuArr = (MasuDef[])Popped.MasuArr.Clone();
                WillPush.MasuArr[IndZero] = Popped.MasuArr[IndChanged];
                WillPush.MasuArr[IndChanged] = 0;

                WillPush.Log = new List<MasuDef[]>(Popped.Log);
                WillPush.Log.Add(WillPush.MasuArr);

                stk.Push(WillPush);
            };

            //空白の1つ左
            if (1 <= IndZero && Popped.MasuArr[IndZero - 1] == MasuDef.Ama) {
                PushSyori(IndZero - 1);
            }
            //空白の2つ左
            if (2 <= IndZero && Popped.MasuArr[IndZero - 2] == MasuDef.Ama) {
                PushSyori(IndZero - 2);
            }

            int UB = Popped.MasuArr.GetUpperBound(0);

            //空白の1つ右
            if (IndZero <= UB - 1 && Popped.MasuArr[IndZero + 1] == MasuDef.Hiki) {
                PushSyori(IndZero + 1);
            }
            //空白の2つ右
            if (IndZero <= UB - 2 && Popped.MasuArr[IndZero + 2] == MasuDef.Hiki) {
                PushSyori(IndZero + 2);
            }
        }
    }

    static void PrintLog(List<MasuDef[]> pLog)
    {
        int Level = 0;
        foreach (MasuDef[] AnyMasuDefineArr in pLog) {
            Console.Write("LV{0,2}=", ++Level);
            foreach (MasuDef AnyMasuDefine in AnyMasuDefineArr) {
                if (AnyMasuDefine == MasuDef.Ama) Console.Write("アマ,");
                if (AnyMasuDefine == MasuDef.Kuuhaku) Console.Write("空白,");
                if (AnyMasuDefine == MasuDef.Hiki) Console.Write("ヒキ,");
            }
            Console.WriteLine();
        }
    }
}

実行結果

解1を発見しました。
LV 1=アマ,アマ,アマ,空白,ヒキ,ヒキ,ヒキ,
LV 2=アマ,アマ,アマ,ヒキ,空白,ヒキ,ヒキ,
LV 3=アマ,アマ,空白,ヒキ,アマ,ヒキ,ヒキ,
LV 4=アマ,空白,アマ,ヒキ,アマ,ヒキ,ヒキ,
LV 5=アマ,ヒキ,アマ,空白,アマ,ヒキ,ヒキ,
LV 6=アマ,ヒキ,アマ,ヒキ,アマ,空白,ヒキ,
LV 7=アマ,ヒキ,アマ,ヒキ,アマ,ヒキ,空白,
LV 8=アマ,ヒキ,アマ,ヒキ,空白,ヒキ,アマ,
LV 9=アマ,ヒキ,空白,ヒキ,アマ,ヒキ,アマ,
LV10=空白,ヒキ,アマ,ヒキ,アマ,ヒキ,アマ,
LV11=ヒキ,空白,アマ,ヒキ,アマ,ヒキ,アマ,
LV12=ヒキ,ヒキ,アマ,空白,アマ,ヒキ,アマ,
LV13=ヒキ,ヒキ,アマ,ヒキ,アマ,空白,アマ,
LV14=ヒキ,ヒキ,アマ,ヒキ,空白,アマ,アマ,
LV15=ヒキ,ヒキ,空白,ヒキ,アマ,アマ,アマ,
LV16=ヒキ,ヒキ,ヒキ,空白,アマ,アマ,アマ,
解2を発見しました。
LV 1=アマ,アマ,アマ,空白,ヒキ,ヒキ,ヒキ,
LV 2=アマ,アマ,空白,アマ,ヒキ,ヒキ,ヒキ,
LV 3=アマ,アマ,ヒキ,アマ,空白,ヒキ,ヒキ,
LV 4=アマ,アマ,ヒキ,アマ,ヒキ,空白,ヒキ,
LV 5=アマ,アマ,ヒキ,空白,ヒキ,アマ,ヒキ,
LV 6=アマ,空白,ヒキ,アマ,ヒキ,アマ,ヒキ,
LV 7=空白,アマ,ヒキ,アマ,ヒキ,アマ,ヒキ,
LV 8=ヒキ,アマ,空白,アマ,ヒキ,アマ,ヒキ,
LV 9=ヒキ,アマ,ヒキ,アマ,空白,アマ,ヒキ,
LV10=ヒキ,アマ,ヒキ,アマ,ヒキ,アマ,空白,
LV11=ヒキ,アマ,ヒキ,アマ,ヒキ,空白,アマ,
LV12=ヒキ,アマ,ヒキ,空白,ヒキ,アマ,アマ,
LV13=ヒキ,空白,ヒキ,アマ,ヒキ,アマ,アマ,
LV14=ヒキ,ヒキ,空白,アマ,ヒキ,アマ,アマ,
LV15=ヒキ,ヒキ,ヒキ,アマ,空白,アマ,アマ,
LV16=ヒキ,ヒキ,ヒキ,空白,アマ,アマ,アマ,

解説

レベルの上限の初期値を(6+5+4)*2の30として、
深さ優先探索で探索してます。