8-24 おしどりの遊び3 石が8個

問題

白と黒の碁石がこのように、交互に並んでいる。
    ○●○●○●○●

これらの碁石を空きスペースを利用して移動させ、
白と黒の碁石が別々に連続して並ぶようにしてほしい。

ただし、移動の際は、隣り合った碁石を同時に、
向きを変えることなく移動させなければならない。

おしどりの遊び : クイズ＆パズルの部屋「Quizzical Days.」

ソース

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

class Program
{
    enum MasuDef
    {
        Kuuhaku = 0,
        White = 1,
        Black = 2
    }

    struct JyoutaiDef
    {
        internal MasuDef[] IshiArr;
        internal List<MasuDef[]> Log;
        internal int LastMoveP;
    }

    const int WhiteCnt = 4;
    const int BlackCnt = 4;

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

        JyoutaiDef WillEnqueue;
        var WKList = new List<MasuDef>();
        WKList.AddRange(Enumerable.Repeat(MasuDef.Kuuhaku, 2));
        WKList.AddRange(new MasuDef[] {MasuDef.White,MasuDef.Black,
                                       MasuDef.White,MasuDef.Black,
                                       MasuDef.White,MasuDef.Black,
                                       MasuDef.White,MasuDef.Black,});
        WKList.AddRange(Enumerable.Repeat(MasuDef.Kuuhaku, 2));
        WillEnqueue.IshiArr = WKList.ToArray();
        WillEnqueue.Log = new List<MasuDef[]>() { WillEnqueue.IshiArr };
        WillEnqueue.LastMoveP = -1;
        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 (IsOK(Dequeued.IshiArr)) {
                Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);

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

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

                que.Enqueue(WillEnqueue);
            };

            MasuDef[] WK_P = Dequeued.IshiArr;

            //2マスの空白への移動
            for (int I = 0; I <= WK_P.GetUpperBound(0) - 1; I++) {
                if (WK_P[I] == MasuDef.Kuuhaku && WK_P[I + 1] == MasuDef.Kuuhaku) {
                    for (int J = 0; J <= WK_P.GetUpperBound(0) - 1; J++) {
                        if (J == Dequeued.LastMoveP) continue;
                        if (WK_P[J] != MasuDef.Kuuhaku &&
                            WK_P[J + 1] != MasuDef.Kuuhaku) {
                            WillEnqueue.IshiArr = (MasuDef[])WK_P.Clone();
                            WillEnqueue.IshiArr[I] = WK_P[J];
                            WillEnqueue.IshiArr[I + 1] = WK_P[J + 1];
                            WillEnqueue.IshiArr[J] = MasuDef.Kuuhaku;
                            WillEnqueue.IshiArr[J + 1] = MasuDef.Kuuhaku;
                            WillEnqueue.LastMoveP = I;
                            EnqueSyori();
                        }
                    }
                }
            }

            //1マスの空白への移動
            for (int I = 0; I <= WK_P.GetUpperBound(0) - 2; I++) {
                if (I + 1 == Dequeued.LastMoveP) continue;
                WillEnqueue.LastMoveP = I;
                if (WK_P[I] == MasuDef.Kuuhaku &&
                    WK_P[I + 1] != MasuDef.Kuuhaku &&
                    WK_P[I + 2] != MasuDef.Kuuhaku) {
                    WillEnqueue.IshiArr = (MasuDef[])WK_P.Clone();
                    WillEnqueue.IshiArr[I] = WK_P[I + 1];
                    WillEnqueue.IshiArr[I + 1] = WK_P[I + 2];
                    WillEnqueue.IshiArr[I + 2] = MasuDef.Kuuhaku;
                    EnqueSyori();
                }
                if (WK_P[I] != MasuDef.Kuuhaku &&
                    WK_P[I + 1] != MasuDef.Kuuhaku &&
                    WK_P[I + 2] == MasuDef.Kuuhaku) {
                    WillEnqueue.IshiArr = (MasuDef[])WK_P.Clone();
                    WillEnqueue.IshiArr[I + 2] = WK_P[I + 1];
                    WillEnqueue.IshiArr[I + 1] = WK_P[I];
                    WillEnqueue.IshiArr[I] = MasuDef.Kuuhaku;
                    EnqueSyori();
                }
            }
        }
    }

    static bool IsOK(MasuDef[] pIshiArr)
    {
        var Query = pIshiArr.SkipWhile(X => X == MasuDef.Kuuhaku)
                            .TakeWhile(X => X != MasuDef.Kuuhaku);

        var WK1 = Enumerable.Repeat(MasuDef.White, WhiteCnt);
        var WK2 = Enumerable.Repeat(MasuDef.Black, BlackCnt);

        return Query.SequenceEqual(WK1.Concat(WK2)) ||
               Query.SequenceEqual(WK2.Concat(WK1));
    }

    static void PrintLog(List<MasuDef[]> pLog)
    {
        int Level = 0;
        var sb = new System.Text.StringBuilder();
        foreach (MasuDef[] AnyArr in pLog) {
            sb.AppendFormat("LV{0,2}=", ++Level);
            foreach (MasuDef AnyMasu in AnyArr) {
                if (AnyMasu == MasuDef.Kuuhaku) sb.Append('　');
                if (AnyMasu == MasuDef.White) sb.Append('○');
                if (AnyMasu == MasuDef.Black) sb.Append('●');
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

解1を発見しました。
LV 1=　　○●○●○●○●
LV 2=●○○●○●○　　●
LV 3=●○○●　　○○●●
LV 4=●　　●○○○○●●
LV 5=●●●●○○○○

解2を発見しました。
LV 1=　　○●○●○●○●
LV 2=　　○　　●○●○●●○
LV 3=　　○○●●　　○●●○
LV 4=　　○○●●●●○　　○
LV 5=　　　　●●●●○○○○

解説

空白が前後に2つの状態で解を列挙してから、
空白が小さいことが原因での手数増加がないことを検証しました。

Enqueの共通処理は、Actionデリゲートでまとめてます。