Cマガ電脳クラブ(第131回) チェス盤の分割

問題

4×4の板を、小正方形の辺に沿って大きさも形も同じ2枚の板に分割するには、回転・鏡像解を除いて6通りある。
その全解をFig.1に示す。
では、同じ要領で8×8の板での合同2分割は何通りあるだろうか

Fig.1  4×4の板を2分割する場合の全解
      ■■□□    ■■■□    ■■■□
      ■■□□    ■■■□    ■□■□
      ■■□□    ■□□□    ■□■□
      ■■□□    ■□□□    ■□□□

      ■■□□    ■■■□    ■■■□
      ■□□□    ■□□□    ■■□□
      ■■■□    ■■■□    ■■□□
      ■■□□    ■□□□    ■□□□

ソース

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

class Program
{
    static int UB;

    static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

    static void Main()
    {
        foreach (int EachI in new int[] { 4, 6, 8 }) {
            Console.WriteLine("■■■■■■■■■■■■■■■■■■■■");
            Console.WriteLine("{0}*{0}の盤で解きます。", EachI);
            UB = EachI - 1;
            Solve();
        }
    }

    //DFSでの分割用
    struct JyoutaiDefDFS
    {
        internal int CurrX;
        internal int CurrY;
        internal char[,] BanArr;
    }

    //UnionFindで島のチェック用
    struct JyoutaiDefUnionFind
    {
        internal int CurrX;
        internal int CurrY;
    }

    static void Solve()
    {
        var stk = new Stack<JyoutaiDefDFS>();
        JyoutaiDefDFS WillPush;

        WillPush.BanArr = new char[UB + 1, UB + 1];
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                WillPush.BanArr[X, Y] = ' ';
            }
        }
        for (int X = 0; X <= UB; X++) {
            WillPush.BanArr[X, 0] = 'B';
            WillPush.BanArr[X, UB] = 'W';
        }
        WillPush.BanArr[0, 1] = 'B';
        WillPush.BanArr[UB, UB - 1] = 'W';
        WillPush.CurrX = 1;
        WillPush.CurrY = 1;
        stk.Push(WillPush);

        var PushedBanStrSet = new HashSet<string>();
        int AnswerCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDefDFS Popped = stk.Pop();

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

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

            Action<char> PushSyori = pChar =>
            {
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[Popped.CurrX, Popped.CurrY] = pChar;

                //対をなす座標にも設定
                WillPush.BanArr[UB - Popped.CurrX, UB - Popped.CurrY] =
                    (pChar == 'B' ? 'W' : 'B');

                //特殊枝切り
                if (UB == 8 - 1) {
                    char[,] wkP = WillPush.BanArr;
                    if ((wkP[0, 2] == 'W' || wkP[0, 3] == 'W')
                     && (wkP[UB, 1] == 'W' || wkP[UB, 2] == 'W' || wkP[UB, 3] == 'W')) {
                        return;
                    }
                }

                //閉路チェック(対称形なので黒マスの分断のみチェック)
                if (WillEdakiri(WillPush.BanArr)) return;

                HashSet<string> wkStrSet = BanToStrSet(WillPush.BanArr);
                if (PushedBanStrSet.Overlaps(wkStrSet)) return;
                PushedBanStrSet.Add(wkStrSet.First());

                stk.Push(WillPush);
            };
            PushSyori('B'); PushSyori('W');
        }
        Console.WriteLine("解は、{0}通り。経過時間{1}", AnswerCnt, sw.Elapsed);
    }

    //UnionFindで枝切り判定
    static bool WillEdakiri(char[,] pBanArr)
    {
        var stk = new Stack<JyoutaiDefUnionFind>();
        JyoutaiDefUnionFind WillPush;

        int CanVisitCnt = 0;
        WillPush.CurrX = 0;
        WillPush.CurrY = 0;
        stk.Push(WillPush);

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

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

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

                if (pBanArr[pNewX, pNewY] == 'W') return;
                string wkStr = string.Format("{0},{1}", pNewX, pNewY);
                if (VisitedSet.Add(wkStr) == false) return;

                if (pBanArr[pNewX, pNewY] == 'B') CanVisitCnt++;

                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);
        }

        //全てのチェック対象マスに訪問不可なら枝切り
        return CanVisitCnt < pBanArr.Cast<char>().Count(X => X == 'B');
    }

    //盤面をString型のSetに変換
    static HashSet<string> BanToStrSet(char[,] pBanArr)
    {
        var WillReturn = new HashSet<string>();

        var sbList = new List<System.Text.StringBuilder>();
        for (int I = 1; I <= 8; I++) {
            sbList.Add(new System.Text.StringBuilder());
        }
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                sbList[0].Append(pBanArr[X, Y]);
                sbList[1].Append(pBanArr[X, UB - Y]);
                sbList[2].Append(pBanArr[UB - X, Y]);
                sbList[3].Append(pBanArr[UB - X, UB - Y]);
                sbList[4].Append(pBanArr[Y, X]);
                sbList[5].Append(pBanArr[UB - Y, X]);
                sbList[6].Append(pBanArr[Y, UB - X]);
                sbList[7].Append(pBanArr[UB - Y, UB - X]);
            }
        }
        sbList.ForEach(X => WillReturn.Add(X.ToString()));
        return WillReturn;
    }

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

実行結果

■■■■■■■■■■■■■■■■■■■■
4*4の盤で解きます。
解は、6通り。経過時間00:00:00.0233758
■■■■■■■■■■■■■■■■■■■■
6*6の盤で解きます。
解は、255通り。経過時間00:00:00.1634358
■■■■■■■■■■■■■■■■■■■■
8*8の盤で解きます。
解30000を発見。経過時間00:00:31.1693553
解60000を発見。経過時間00:01:13.7788696
解90000を発見。経過時間00:02:06.4775229
解は、92263通り。経過時間00:02:10.3822851

解説

4*4の盤で計算量を減らす考察です。

■■■手順1■■■■■■■■■■■■■■■■■■■■■■■■■■■
回転解を考えなくていいので、左上をBとします。
中心点と点対称で、別の色であれば、合同分割なので右下はWとなります。

B???
????
????
???W

■■■手順2■■■■■■■■■■■■■■■■■■■■■■■■■■■
右上をBとすれば左下がWとなり、
右上をWとすれば左下がBとなり、
どちらも回転解なので、前者とします。

B??B
????
????
W??W

■■■手順3■■■■■■■■■■■■■■■■■■■■■■■■■■■
下記のように、上辺にWがあると、
左上のBと右上のBを結んで、かつ
上辺のWと下辺のWが結べなくなりますので、
矛盾します。(ナンバーリンクの感覚)

BW?B
????
????
W??W

なので、上辺と下辺が確定して、下記の形となります。

BBBB
????
????
WWWW

■■■手順4■■■■■■■■■■■■■■■■■■■■■■■■■
下記のように1行目の左端と右端がWと仮定すると、
上辺のBは、もう外周のマスと結べなくなり、
矛盾します。(ナンバーリンクの感覚)

BBBB
W??W
????
WWWW

なので、
上辺のBは、少なくとも1つがBですので、
回転解の排除で左端をBとします。

BBBB
B???
????
WWWW

上記の形から深さ優先探索します。
8*8の盤では、2の23乗=8388608 が探索ノード数となります。

■■■手順5■■■■■■■■■■■■■■■■■■■■■■■■■■■
特殊枝切りとして、8*8の盤では、下記で、
1か2の少なくとも1つがW、かつ、3か4か5の少なくとも1つがW
だったら、
外周のBが14個未満になってしまうので(ナンバーリンクの感覚)
枝切りしてます。

BBBBBBBB
B??????3
1??????4
2??????5
????????
????????
???????W
WWWWWWWW