Q49 反転で作る互い違い

C#のソース

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

class Program
{
    static void Main()
    {
        Solve(3);
        Solve(8);
    }

    struct JyoutaiDef
    {
        internal int CurrP;
        internal bool[] IsBlackArr;
        internal List<bool[]> Log;
    }

    static void Solve(int pN)
    {
        var que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrP = 0;
        WillEnqueue.IsBlackArr = new bool[pN * 2];
        int UB = WillEnqueue.IsBlackArr.GetUpperBound(0);
        for (int I = 0; I <= pN - 1; I++)
            WillEnqueue.IsBlackArr[I] = true;

        WillEnqueue.Log = new List<bool[]>() { WillEnqueue.IsBlackArr };
        que.Enqueue(WillEnqueue);
        while (que.Count > 0) {
            JyoutaiDef Dequeued = que.Dequeue();

            //クリア判定
            if (IsClear(UB, Dequeued.IsBlackArr)) {
                Console.WriteLine("n={0}での解を発見", pN);
                for (int I = 0; I <= Dequeued.Log.Count - 1; I++) {
                    Console.WriteLine("{0}手目", I);
                    Array.ForEach(Dequeued.Log[I], X => Console.Write(X ? '■' : '□'));
                    Console.WriteLine();
                }
                return;
            }

            for (int I = Dequeued.CurrP; I <= UB; I++) {
                WillEnqueue.CurrP = I + 1;
                WillEnqueue.IsBlackArr = (bool[])Dequeued.IsBlackArr.Clone();
                for (int J = 0; J <= 2; J++) {
                    int wkInd = I + J;
                    if (wkInd > UB) {
                        wkInd -= (UB + 1);
                    }
                    WillEnqueue.IsBlackArr[wkInd] = !WillEnqueue.IsBlackArr[wkInd];
                }
                WillEnqueue.Log = new List<bool[]>(Dequeued.Log) { WillEnqueue.IsBlackArr };
                que.Enqueue(WillEnqueue);
            }
        }
    }

    //クリア判定
    static bool IsClear(int pUB, bool[] pIsBlackArr)
    {
        bool[] Answer1 = new bool[pUB + 1];
        bool[] Answer2 = new bool[pUB + 1];

        for (int I = 0; I <= pUB; I++) {
            //偶数が黒で、奇数が白
            Answer1[I] = (I % 2 == 0);

            //偶数が白で、奇数が黒
            Answer2[I] = (I % 2 == 1);
        }
        return pIsBlackArr.SequenceEqual(Answer1) || pIsBlackArr.SequenceEqual(Answer2);
    }
}

実行結果

n=3での解を発見
0手目
■■■□□□
1手目
■□□■□□
2手目
■□■□■□
n=8での解を発見
0手目
■■■■■■■■□□□□□□□□
1手目
□□□■■■■■□□□□□□□□
2手目
□■■□■■■■□□□□□□□□
3手目
□■□■□■■■□□□□□□□□
4手目
□■□■□■□□■□□□□□□□
5手目
□■□■□■□■□■□□□□□□
6手目
□■□■□■□■□■□■■■□□
7手目
□■□■□■□■□■□■□□■□
8手目
□■□■□■□■□■□■□■□■

解説

最短の回数を求めればいいので、幅優先探索を使ってます。