Q67 クロスワードパズルを作成せよ！

C#のソース

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

class Program
{
    struct JyoutaiDefDFS
    {
        internal int CurrX;
        internal int CurrY;
        internal char[,] BanArr;
    }

    const int UB_X = 6 - 1;
    const int UB_Y = 5 - 1;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        var stk = new Stack<JyoutaiDefDFS>();
        JyoutaiDefDFS WillPush;
        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++)
            for (int Y = 0; Y <= UB_Y; Y++)
                WillPush.BanArr[X, Y] = ' ';
        stk.Push(WillPush);

        int AnswerCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDefDFS Popped = stk.Pop();
            //PrintBan(Popped.BanArr);

            //X座標の繰上げ処理
            if (Popped.CurrX > UB_X) {
                Popped.CurrX = 0;
                Popped.CurrY++;
            }

            //最終行を超えた場合
            if (Popped.CurrY > UB_Y) {
                AnswerCnt++;
                if (AnswerCnt % 10000 == 1) {
                    Console.WriteLine("解{0}を発見。経過時間={1}",
                        AnswerCnt, sw.Elapsed);
                    PrintBan(Popped.BanArr);
                }
                continue;
            }

            Action<bool> PushSyori = (pIsBlack) =>
            {
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;

                if (pIsBlack) {
                    WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                    WillPush.BanArr[Popped.CurrX, Popped.CurrY] = 'B';

                    //カレントマスが黒マスに隣接しているかを判定
                    if (HasRinsetuBlack(WillPush.BanArr, Popped.CurrX, Popped.CurrY))
                        return;

                    //UnionFindで盤面が分断されてるかを判定
                    if (IsBundan(WillPush.BanArr)) return;
                }
                else {
                    WillPush.BanArr = Popped.BanArr;
                }
                stk.Push(WillPush);
            };
            PushSyori(false);
            PushSyori(true);
        }
        Console.WriteLine("解は{0}通り", AnswerCnt);
    }

    //カレントマスが黒マスに隣接しているかを判定
    static bool HasRinsetuBlack(char[,] pBanArr, int pCurrX, int pCurrY)
    {
        if (0 < pCurrX && pBanArr[pCurrX - 1, pCurrY] == 'B')
            return true;
        if (0 < pCurrY && pBanArr[pCurrX, pCurrY - 1] == 'B')
            return true;
        return false;
    }

    struct JyoutaiDefUnionFind
    {
        internal int CurrX;
        internal int CurrY;
    }

    //UnionFindで盤面が分断されてるかを判定
    static bool IsBundan(char[,] pBanArr)
    {
        int StaX = -1;
        int StaY = -1;

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (pBanArr[X, Y] != 'B') {
                    StaX = X; StaY = Y;
                }
            }
        }

        var stk = new Stack<JyoutaiDefUnionFind>();
        JyoutaiDefUnionFind WillPush;
        WillPush.CurrX = StaX;
        WillPush.CurrY = StaY;
        stk.Push(WillPush);

        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(string.Format("({0},{1})", StaX, StaY));

        while (stk.Count > 0) {
            JyoutaiDefUnionFind Popped = stk.Pop();

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                //Bは訪問不可
                if (pBanArr[pNewX, pNewY] == 'B') return;

                //再訪不可
                string wkStr = string.Format("({0},{1})", pNewX, pNewY);
                if (VisitedSet.Add(wkStr) == false)
                    return;

                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                stk.Push(WillPush);
            };

            PushSyori(Popped.CurrX, Popped.CurrY - 1);
            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }
        int wkCnt = pBanArr.Cast<char>().Count(X => X == ' ');
        return VisitedSet.Count < wkCnt;
    }

    //盤面を出力
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y] == ' ' ? 'W' : 'B');
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

省略
解130001を発見。経過時間=00:00:28.0023938
WWWWWW
BWBWBW
WWWBWW
WWWWWW
WWWWWB

解140001を発見。経過時間=00:00:30.1721883
WWWWWW
WWBWBW
BWWBWB
WWBWWW
WWWWBW

解は149283通り

解説

深さ優先探索で順にマスを埋めつつ、
UnionFindで分断されてないかをチェックしてます。