Q39 「白」で埋めつくせ！

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 4 - 1;

    struct JyoutaiDef
    {
        internal int Level;
        internal char[,] BanArr;
    }

    static void Main()
    {
        var que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Level = 0;
        WillEnqueue.BanArr = new char[UB + 1, UB + 1];
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                WillEnqueue.BanArr[LoopX, LoopY] = '□';
            }
        }
        que.Enqueue(WillEnqueue);

        //訪問済の盤面のHashSet
        var VisitedBan = new HashSet<ushort>();
        VisitedBan.Add(BanToUShort(WillEnqueue.BanArr));

        int AnswerLevel = int.MinValue;
        var AnswerBanArrList = new List<char[,]>();

        while (que.Count > 0) {
            JyoutaiDef Dequeued = que.Dequeue();

            if (AnswerLevel < Dequeued.Level) {
                AnswerLevel = Dequeued.Level;
                AnswerBanArrList.Clear();
            }
            if (AnswerLevel == Dequeued.Level) {
                AnswerBanArrList.Add(Dequeued.BanArr);
            }

            WillEnqueue.Level = Dequeued.Level + 1;
            for (int LoopX = 0; LoopX <= UB; LoopX++) {
                for (int LoopY = 0; LoopY <= UB; LoopY++) {
                    char[,] ChangedBan = DeriveChangedBan(LoopX, LoopY, Dequeued.BanArr);

                    //訪問済なら枝切り
                    if (VisitedBan.Add(BanToUShort(ChangedBan)) == false)
                        continue;

                    WillEnqueue.BanArr = ChangedBan;
                    que.Enqueue(WillEnqueue);
                }
            }
        }
        //最長手数な盤面を1つ表示する
        Console.WriteLine("最長手数は{0}手で、{1}通り", AnswerLevel, AnswerBanArrList.Count);
        Console.WriteLine();

        for (int I = 0; I <= AnswerBanArrList.Count - 1; I++) {
            Console.WriteLine("解{0}は、", I + 1);
            PrintBan(AnswerBanArrList[I]);
        }
    }

    //選択したマス目を引数とし、反転後の盤面を返す
    static char[,] DeriveChangedBan(int pBaseX, int pBaseY, char[,] pBanArr)
    {
        char[,] ChangedBan = (char[,])pBanArr.Clone();

        Func<char, char> HantenFunc = pTarget => pTarget == '■' ? '□' : '■';

        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            ChangedBan[LoopX, pBaseY] = HantenFunc(pBanArr[LoopX, pBaseY]);
        }
        for (int LoopY = 0; LoopY <= UB; LoopY++) {
            ChangedBan[pBaseX, LoopY] = HantenFunc(pBanArr[pBaseX, LoopY]);
        }
        return ChangedBan;
    }

    //盤面をUShort型に変換
    static ushort BanToUShort(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                sb.Append(pBanArr[X, Y] == '■' ? '1' : '0');
            }
        }
        return Convert.ToUInt16(sb.ToString(), 2);
    }

    //盤面を出力
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

最長手数は16手で、1通り

解1は、
■■■■
■■■■
■■■■
■■■■

解説

訪問済の盤面への再訪を防いだ、幅優先探索で解いてます。