Cマガ電脳クラブ(第051回) 分断寸前

問題

8×8の盤に次の条件に従ってコインを配置する。
　1) 縦横にコインが隣り合わないこと
　2) コインの置かれていないマスは全体がひとつにつながっていること
Fig.1は19個のコインを置いたもので、これ以上置けなくなっている。
さて、コインは最大いくつ置けるだろうか。また、どんな置き方があるだろうか。
最大個数と何パターンあるか調べてほしい。
なお、裏返ししたり回転して一致するパターンも別のものとしてカウントしてかまわない。

Fig.1 置き方の例(コイン19個)

ソース

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

class Program
{
    static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

    struct JyoutaiDef
    {
        internal int CoinMaisuu;
        internal bool[,] CoinHaitiArr;
    }

    static void Main()
    {
        //4*4のコインの配置を列挙
        Console.WriteLine("4*4のコインの配置を列挙中。経過時間={0}", sw.Elapsed);
        JyoutaiDef[] CoinHaiti_4_4_Arr = DeriveCoinHaiti_4_4_Arr();
        Console.WriteLine("4*4のコインの配置数={0}。経過時間={1}",
            CoinHaiti_4_4_Arr.Length, sw.Elapsed);
        Console.WriteLine();

        //上の8*4のコインの配置を列挙
        Console.WriteLine("上の8*4のコインの配置を列挙中。経過時間={0}", sw.Elapsed);
        JyoutaiDef[] CoinHaiti_Ue_8_4_Arr = DeriveCoinHaiti_Ue_8_4_Arr(CoinHaiti_4_4_Arr);
        Console.WriteLine("上の8*4のコインの配置数={0}。経過時間={1}",
            CoinHaiti_Ue_8_4_Arr.Length, sw.Elapsed);
        Console.WriteLine();

        //下の8*4のコインの配置を列挙
        Console.WriteLine("下の8*4のコインの配置を列挙中。経過時間={0}", sw.Elapsed);
        JyoutaiDef[] CoinHaiti_Shita_8_4_Arr = DeriveCoinHaiti_Shita_8_4_Arr(CoinHaiti_Ue_8_4_Arr);
        Console.WriteLine("下の8*4のコインの配置数={0}。経過時間={1}",
            CoinHaiti_Shita_8_4_Arr.Length, sw.Elapsed);
        Console.WriteLine();

        //8*8のコインの配置を列挙
        Console.WriteLine("8*8のコインの配置を列挙中。経過時間={0}", sw.Elapsed);
        DeriveAnswer(CoinHaiti_Ue_8_4_Arr, CoinHaiti_Shita_8_4_Arr);
    }

    //4*4のコインの配置を列挙
    static JyoutaiDef[] DeriveCoinHaiti_4_4_Arr()
    {
        var WillReturnCoinHaiti_4_4_List = new List<JyoutaiDef>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CoinMaisuu = 0;
        WillPush.CoinHaitiArr = new bool[4, 4];
        stk.Push(WillPush);

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

            //外周を1マス増やしたとしても閉路があったら枝切り
            if (HasHeiro_4_4(Popped.CoinHaitiArr, Popped.CoinMaisuu)) {
                continue;
            }

            //コイン2枚以上なら候補としてAdd
            if (Popped.CoinMaisuu >= 2) {
                JyoutaiDef WillAdd;
                WillAdd.CoinMaisuu = Popped.CoinMaisuu;
                WillAdd.CoinHaitiArr = Popped.CoinHaitiArr;
                WillReturnCoinHaiti_4_4_List.Add(WillAdd);
            }

            int CountCoinMaisuu = 0;

            bool WillBreakYLoop = false;
            for (int Y = 0; Y <= 3; Y++) {
                for (int X = 0; X <= 3; X++) {
                    if (Popped.CoinMaisuu > 0) {
                        if (CountCoinMaisuu < Popped.CoinMaisuu) {
                            if (Popped.CoinHaitiArr[X, Y])
                                CountCoinMaisuu++;

                            //配置済コイン数に到達するまでは、Continue
                            continue;
                        }
                    }

                    //配置済コインと隣接していたら配置しない
                    if (IsRinsetuCoin(Popped.CoinHaitiArr, X, Y)) continue;

                    //コインの配置処理
                    WillPush.CoinMaisuu = Popped.CoinMaisuu + 1;
                    WillPush.CoinHaitiArr = (bool[,])Popped.CoinHaitiArr.Clone();
                    WillPush.CoinHaitiArr[X, Y] = true;

                    //Y座標が3以上で配置コインが1枚未満なら枝切り
                    if (3 <= Y && WillPush.CoinMaisuu < 1) {
                        WillBreakYLoop = true; break;
                    }

                    stk.Push(WillPush);
                }
                if (WillBreakYLoop) break;
            }
        }
        //コインの枚数の降順にソートしておく
        return WillReturnCoinHaiti_4_4_List.OrderByDescending(X => X.CoinMaisuu).ToArray();
    }

    //外周を1マス増やしたとしても閉路があるかを返す(4*4用)
    static bool HasHeiro_4_4(bool[,] pCoinArr_4_4, int pCoinMaisuu)
    {
        bool[,] CoinArr_6_6 = new bool[6, 6];

        for (int X = 0; X <= 3; X++) {
            for (int Y = 0; Y <= 3; Y++) {
                CoinArr_6_6[X + 1, Y + 1] = pCoinArr_4_4[X, Y];
            }
        }

        int VisitedCnt = ExecUnionFind(CoinArr_6_6, 2, CoinArr_6_6[2, 2] ? 3 : 2);
        return (VisitedCnt + pCoinMaisuu < 6 * 6);
    }

    //指定した座標にコインが隣接しているかを返す
    static bool IsRinsetuCoin(bool[,] pCoinHaitiArr, int pX, int pY)
    {
        if (pX - 1 >= 0 && pCoinHaitiArr[pX - 1, pY]) return true;
        if (pY - 1 >= 0 && pCoinHaitiArr[pX, pY - 1]) return true;
        return false;
    }

    //盤面の上半分の8*4のコインの配置を列挙
    static JyoutaiDef[] DeriveCoinHaiti_Ue_8_4_Arr(JyoutaiDef[] pCoinHaiti_4_4_Arr)
    {
        var WillReturnCoinHaiti_Ue_8_4_List = new List<JyoutaiDef>();

        foreach (JyoutaiDef Jyoutai1 in pCoinHaiti_4_4_Arr) {
            foreach (JyoutaiDef Jyoutai2 in pCoinHaiti_4_4_Arr) {

                //コインの枚数が9枚未満なら枝切り
                int CoinMaisuuSum = Jyoutai1.CoinMaisuu + Jyoutai2.CoinMaisuu;
                if (CoinMaisuuSum < 9) break;

                //コインの隣接のチェック
                bool HasRinsetuCoin = false;
                for (int Y = 0; Y <= 3; Y++) {
                    if (Jyoutai1.CoinHaitiArr[3, Y] && Jyoutai2.CoinHaitiArr[0, Y]) {
                        HasRinsetuCoin = true; break;
                    }
                }
                if (HasRinsetuCoin) continue;

                //値をコピー
                bool[,] CoinHaitiArr = new bool[8, 4];
                for (int X = 0; X <= 3; X++) {
                    for (int Y = 0; Y <= 3; Y++) {
                        CoinHaitiArr[X, Y] = Jyoutai1.CoinHaitiArr[X, Y];
                        CoinHaitiArr[X + 4, Y] = Jyoutai2.CoinHaitiArr[X, Y];
                    }
                }

                //最低1枚のコインを配置可能なマスに配置済かチェック
                if (IsSetCoinLatest1(CoinHaitiArr) == false) continue;

                //閉路のチェック
                if (HasHeiro_Ue_8_4(CoinHaitiArr, CoinMaisuuSum)) continue;

                JyoutaiDef WillAdd;
                WillAdd.CoinMaisuu = CoinMaisuuSum;
                WillAdd.CoinHaitiArr = CoinHaitiArr;
                WillReturnCoinHaiti_Ue_8_4_List.Add(WillAdd);
            }
        }

        //コインの枚数の降順にソートしておく
        return WillReturnCoinHaiti_Ue_8_4_List.OrderByDescending(X => X.CoinMaisuu).ToArray();
    }

    //最低1枚のコインを配置可能なマスに配置済かチェック
    static bool IsSetCoinLatest1(bool[,] pCoinHaitiArr)
    {
        //最低1枚のコインがあるか？
        Func<int, int, int, int, bool> HasCoin = (pFromX, pFromY, pToX, pToY) =>
        {
            for (int X = pFromX; X <= pToX; X++) {
                for (int Y = pFromY; Y <= pToY; Y++) {
                    if (pCoinHaitiArr[X, Y]) return true;
                }
            }
            return false;
        };

        if (HasCoin(0, 0, 1, 1) == false) return false;
        if (HasCoin(1, 0, 3, 1) == false) return false;
        if (HasCoin(2, 0, 4, 1) == false) return false;
        if (HasCoin(3, 0, 5, 1) == false) return false;
        if (HasCoin(4, 0, 6, 1) == false) return false;
        if (HasCoin(6, 0, 7, 1) == false) return false;

        if (HasCoin(0, 1, 1, 3) == false) return false;
        if (HasCoin(1, 1, 3, 3) == false) return false;
        if (HasCoin(2, 1, 4, 3) == false) return false;
        if (HasCoin(3, 1, 5, 3) == false) return false;
        if (HasCoin(4, 1, 6, 3) == false) return false;
        if (HasCoin(6, 1, 7, 3) == false) return false;

        return true;
    }

    //下に1行増やしたとしても閉路があるかを返す(8*4用)
    static bool HasHeiro_Ue_8_4(bool[,] pCoinArr_8_4, int pCoinMaisuu)
    {
        bool[,] CoinArr_8_5 = new bool[8, 5];

        for (int X = 0; X <= 7; X++) {
            for (int Y = 0; Y <= 3; Y++) {
                CoinArr_8_5[X, Y] = pCoinArr_8_4[X, Y];
            }
        }

        int VisitedCnt = ExecUnionFind(CoinArr_8_5, 3, CoinArr_8_5[3, 1] ? 2 : 1);
        return (VisitedCnt + pCoinMaisuu < 8 * 5);
    }

    //盤面の下半分の8*4のコインの配置を列挙
    static JyoutaiDef[] DeriveCoinHaiti_Shita_8_4_Arr(JyoutaiDef[] pCoinHaiti_Ue_8_4_Arr)
    {
        var WillReturnCoinHaiti_Shita_8_4_List = new List<JyoutaiDef>();

        foreach (JyoutaiDef AnyJyoutai in pCoinHaiti_Ue_8_4_Arr) {
            int SetCoinMaisuu = AnyJyoutai.CoinMaisuu;

            //値をコピー
            bool[,] CoinHaitiArr = new bool[8, 4];
            for (int X = 0; X <= 7; X++) {
                for (int Y = 0; Y <= 3; Y++) {
                    CoinHaitiArr[X, 3 - Y] = AnyJyoutai.CoinHaitiArr[X, Y];
                }
            }
            JyoutaiDef WillAdd;
            WillAdd.CoinMaisuu = SetCoinMaisuu;
            WillAdd.CoinHaitiArr = CoinHaitiArr;
            WillReturnCoinHaiti_Shita_8_4_List.Add(WillAdd);
        }

        //コインの枚数の降順にソートしておく
        return WillReturnCoinHaiti_Shita_8_4_List.OrderByDescending(X => X.CoinMaisuu).ToArray();
    }

    //8*8のコインの配置を列挙
    static void DeriveAnswer(JyoutaiDef[] pCoinHaiti_Ue_8_4_Arr, JyoutaiDef[] pCoinHaiti_Shita_8_4_Arr)
    {
        int MaxCoinCnt = 0;
        int AnswerCnt = 0;

        foreach (JyoutaiDef Jyoutai1 in pCoinHaiti_Ue_8_4_Arr) {
            foreach (JyoutaiDef Jyoutai2 in pCoinHaiti_Shita_8_4_Arr) {

                //コインの枚数が現在の解未満なら枝切り
                int CoinMaisuuSum = Jyoutai1.CoinMaisuu + Jyoutai2.CoinMaisuu;
                if (CoinMaisuuSum < MaxCoinCnt) break;

                //コインの隣接のチェック
                bool HasRinsetuCoin = false;
                for (int X = 0; X <= 7; X++) {
                    if (Jyoutai1.CoinHaitiArr[X, 3] && Jyoutai2.CoinHaitiArr[X, 0]) {
                        HasRinsetuCoin = true; break;
                    }
                }
                if (HasRinsetuCoin) continue;

                //値をコピー
                bool[,] CoinHaitiArr = new bool[8, 8];
                for (int X = 0; X <= 7; X++) {
                    for (int Y = 0; Y <= 3; Y++) {
                        CoinHaitiArr[X, Y] = Jyoutai1.CoinHaitiArr[X, Y];
                        CoinHaitiArr[X, Y + 4] = Jyoutai2.CoinHaitiArr[X, Y];
                    }
                }

                //閉路のチェック
                if (HasHeiro_8_8(CoinHaitiArr, CoinMaisuuSum)) continue;

                if (MaxCoinCnt < CoinMaisuuSum) {
                    MaxCoinCnt = CoinMaisuuSum;
                    AnswerCnt = 0;
                }
                AnswerCnt++;
                if (AnswerCnt % 2000 == 1) {
                    Console.WriteLine("解候補{0}(コインの枚数={1})を発見。経過時間={2}",
                        AnswerCnt, CoinMaisuuSum, sw.Elapsed);
                }
                if (AnswerCnt == 1) PrintAnswer(CoinHaitiArr);
            }
        }
        Console.WriteLine("解は{0}通りで、コインの枚数={1}。経過時間={2}",
            AnswerCnt, MaxCoinCnt, sw.Elapsed);
    }

    //閉路があるかを返す(8*8用)
    static bool HasHeiro_8_8(bool[,] pCoinArr_8_8, int pCoinMaisuu)
    {
        int VisitedCnt = ExecUnionFind(pCoinArr_8_8, 3, pCoinArr_8_8[3, 3] ? 4 : 3);
        return (VisitedCnt + pCoinMaisuu < 8 * 8);
    }

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    static int ExecUnionFind(bool[,] pCoinHaitiArr, int pStaX, int pStaY)
    {
        var VisitedSet = new HashSet<int>(); //訪問済座標のセット

        var stk = new Stack<PointDef>();
        PointDef WillPush;
        WillPush.X = pStaX;
        WillPush.Y = pStaY;
        VisitedSet.Add(pStaX * 10 + pStaY);
        stk.Push(WillPush);

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

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                //コインの配置マスなら枝切り
                if (pCoinHaitiArr[pNewX, pNewY]) return;

                //訪問済なら枝切り
                if (VisitedSet.Add(pNewX * 10 + pNewY) == false)
                    return;

                WillPush.X = pNewX;
                WillPush.Y = pNewY;
                stk.Push(WillPush);
            };

            //左に移動
            if (Popped.X > 0) PushSyori(Popped.X - 1, Popped.Y);
            //右に移動
            if (Popped.X < pCoinHaitiArr.GetUpperBound(0)) PushSyori(Popped.X + 1, Popped.Y);
            //上に移動
            if (Popped.Y > 0) PushSyori(Popped.X, Popped.Y - 1);
            //下に移動
            if (Popped.Y < pCoinHaitiArr.GetUpperBound(1)) PushSyori(Popped.X, Popped.Y + 1);
        }
        return VisitedSet.Count;
    }

    //解を出力
    static void PrintAnswer(bool[,] pCoinHaitiArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= pCoinHaitiArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pCoinHaitiArr.GetUpperBound(0); X++) {
                sb.Append(pCoinHaitiArr[X, Y] ? '●' : '□');
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

4*4のコインの配置を列挙中。経過時間=00:00:00.0023905
4*4のコインの配置数=1145。経過時間=00:00:00.1860906

上の8*4のコインの配置を列挙中。経過時間=00:00:00.1868226
上の8*4のコインの配置数=45005。経過時間=00:00:08.2490970

下の8*4のコインの配置を列挙中。経過時間=00:00:08.2493867
下の8*4のコインの配置数=45005。経過時間=00:00:08.5029605

8*8のコインの配置を列挙中。経過時間=00:00:08.5032516
解候補1(コインの枚数=21)を発見。経過時間=00:00:08.6032213
●□□●□●□●
□□●□□□□□
●□□□●□●□
□●□●□●□●
□□□□□□□□
□●□●□●□●
□□●□□□□□
●□□●□●□●

解候補2001(コインの枚数=21)を発見。経過時間=00:00:24.7820435
解候補4001(コインの枚数=21)を発見。経過時間=00:00:42.3958206
解候補6001(コインの枚数=21)を発見。経過時間=00:01:02.8731257
解候補8001(コインの枚数=21)を発見。経過時間=00:01:09.0898834
解は8896通りで、コインの枚数=21。経過時間=00:01:17.8060069

解説

4*4のコインの配置を列挙する際に
Y座標が3以上で配置コインが1枚未満なら枝切りしてます。
下記のように、外周を空けたとしても、1枚を配置可能だからです。
□□□□
□●□□
□□□□

4*4のコインの配置を列挙する際に
コインが2枚未満の配置を枝切りしてます。
下記のように、外周を空けたとしても、2枚を配置可能だからです。
□□□□
□●□□
□□●□
□□□□

上の8*4のコインの配置を列挙する際に
コインが9枚未満の配置を枝切りしてます。
下記のように、1番下のマスを空けたとしても、9枚を配置可能だからです。
□□●□□●□●
●□□□●□□□
□●□●□●□●
□□□□□□□□