8-10 カエルの整列

問題

4匹のカエルが、左から番号の大きい順に葉の上に並んでいる。
このカエルを、番号の小さい順に並べ替えてほしい。

カエルは左右両隣の葉に飛び移ることができ、
また、もう1つ向こうの葉が空いている場合は、他のカエルを飛び越して移動することもできる。
ただし、1枚の葉に同時に2匹以上のカエルが乗ることはできない。

さて、カエルを指定した順に並び替えるにはどうすればよいだろうか?

カエルの整列 : クイズ＆パズルの部屋「Quizzical Days.」

ソース

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

class Program
{
    private struct JyoutaiDef
    {
        internal int[] FrogArr;
        internal List<int[]> Log;
    }

    static void Main()
    {
        var que = new Queue<JyoutaiDef>();

        JyoutaiDef WillEnqueue;
        WillEnqueue.FrogArr = new int[5] { 4, 3, 2, 1, 0 };
        WillEnqueue.Log = new List<int[]>() { WillEnqueue.FrogArr };
        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.FrogArr.SequenceEqual(new int[] { 1, 2, 3, 4, 0 })
             || Dequeued.FrogArr.SequenceEqual(new int[] { 0, 1, 2, 3, 4 })) {
                Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);

                PrintFrogArrLog(Dequeued.Log);
                if (MaxLevel > Dequeued.Log.Count)
                    MaxLevel = Dequeued.Log.Count;

                continue;
            }

            int IndZero = Array.IndexOf<int>(Dequeued.FrogArr, 0);

            Action<int> EnqueSyori = (IndChanged) =>
            {
                WillEnqueue.FrogArr = (int[])Dequeued.FrogArr.Clone();
                WillEnqueue.FrogArr[IndZero] = WillEnqueue.FrogArr[IndChanged];
                WillEnqueue.FrogArr[IndChanged] = 0;

                //既存の配置だったら枝切り
                if (Dequeued.Log.Exists(X => X.SequenceEqual(WillEnqueue.FrogArr))) {
                    return;
                }
                WillEnqueue.Log = new List<int[]>(Dequeued.Log);
                WillEnqueue.Log.Add(WillEnqueue.FrogArr);

                que.Enqueue(WillEnqueue);
            };

            if (1 <= IndZero) EnqueSyori(IndZero - 1); //0の1つ左
            if (2 <= IndZero) EnqueSyori(IndZero - 2); //0の2つ左

            int UB = Dequeued.FrogArr.GetUpperBound(0);

            if (IndZero <= UB - 1) EnqueSyori(IndZero + 1); //0の1つ右
            if (IndZero <= UB - 2) EnqueSyori(IndZero + 2); //0の2つ右
        }
    }

    static void PrintFrogArrLog(List<int[]> pFrogArrLog)
    {
        int Level = 0;
        foreach (int[] AnyArr in pFrogArrLog) {
            Console.Write("LV{0,2}=", ++Level);
            foreach (int AnyInt in AnyArr) {
                Console.Write("{0},", AnyInt);
            }
            Console.WriteLine();
        }
    }
}

実行結果

解1を発見しました
LV 1=4,3,2,1,0,
LV 2=4,3,2,0,1,
LV 3=4,0,2,3,1,
LV 4=0,4,2,3,1,
LV 5=2,4,0,3,1,
LV 6=2,4,1,3,0,
LV 7=2,4,1,0,3,
LV 8=2,0,1,4,3,
LV 9=0,2,1,4,3,
LV10=1,2,0,4,3,
LV11=1,2,3,4,0,
解2を発見しました
LV 1=4,3,2,1,0,
LV 2=4,3,0,1,2,
LV 3=4,0,3,1,2,
LV 4=4,1,3,0,2,
LV 5=4,1,3,2,0,
LV 6=4,1,0,2,3,
LV 7=0,1,4,2,3,
LV 8=1,0,4,2,3,
LV 9=1,2,4,0,3,
LV10=1,2,0,4,3,
LV11=1,2,3,4,0,
解3を発見しました
LV 1=4,3,2,1,0,
LV 2=4,3,0,1,2,
LV 3=0,3,4,1,2,
LV 4=3,0,4,1,2,
LV 5=3,1,4,0,2,
LV 6=3,1,4,2,0,
LV 7=3,1,0,2,4,
LV 8=0,1,3,2,4,
LV 9=1,0,3,2,4,
LV10=1,2,3,0,4,
LV11=1,2,3,4,0,
解4を発見しました
LV 1=4,3,2,1,0,
LV 2=4,3,0,1,2,
LV 3=4,3,1,0,2,
LV 4=4,0,1,3,2,
LV 5=0,4,1,3,2,
LV 6=1,4,0,3,2,
LV 7=1,4,2,3,0,
LV 8=1,4,2,0,3,
LV 9=1,0,2,4,3,
LV10=1,2,0,4,3,
LV11=1,2,3,4,0,

解説

ListジェネリックのExistsメソッドの引数の、Predicateデリゲートで
LINQのSequenceEqual拡張メソッドを使って枝切りしてます。

MSDN --- List<T>.Existsメソッド
MSDN --- Enumerable.SequenceEqual<TSource>メソッド