Cマガ電脳クラブ(第012回) 別れたボード

問題

Fig.1を見てほしい。
4×4のマス目に1〜16の数を左上から順番に書き込んだ正方形の板がある。
この板を赤線に沿って切り離すと、2枚の板それぞれの数の合計が等しくなった。
このような切り方をほかにも見つけてほしい。

Fig.1

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal int SumVal;
        internal bool[,] IsSelectedArr;
    }

    const int AnswerSumVal = (16 * (16 + 1) / 2) / 2; //等差数列の和の公式
    static int[,] MasuArr = new int[4, 4];

    static void Main()
    {
        var wkIntArr = new int[,] {{ 1, 2, 3, 4},
                                   { 5, 6, 7, 8},
                                   { 9,10,11,12},
                                   {13,14,15,16}};
        for (int X = 0; X <= wkIntArr.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= wkIntArr.GetUpperBound(1); Y++) {
                MasuArr[X, Y] = wkIntArr[Y, X];
            }
        }

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        //(0,0)を含む解は、(0,0)を含まない解と対をなすので
        //(0,0)を固定で含めて計算量を減らす
        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.SumVal = MasuArr[0, 0];
        WillPush.IsSelectedArr = new bool[4, 4];
        WillPush.IsSelectedArr[0, 0] = true;
        stk.Push(WillPush);

        int AnswerCnt = 0;
        var AnswerBanSet = new HashSet<string>();

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

            if (Popped.SumVal == AnswerSumVal) {
                //UnionFindのアルゴリズムで連結ノードをまとめる
                HashSet<string> TrueSet = ExecUnionFind(Popped.IsSelectedArr, 0, 0);

                var FalseSet = new HashSet<string>();
                for (int Y = 0; Y <= Popped.IsSelectedArr.GetUpperBound(1); Y++) {
                    for (int X = 0; X <= Popped.IsSelectedArr.GetUpperBound(0); X++) {
                        if (Popped.IsSelectedArr[X, Y] == false) {
                            FalseSet = ExecUnionFind(Popped.IsSelectedArr, X, Y);
                        }
                    }
                }
                if (TrueSet.Count + FalseSet.Count < 16) continue;

                string AnswerBan = DeriveAnswerBan(Popped.IsSelectedArr);

                //既出解なら出力しない
                if (AnswerBanSet.Add(AnswerBan) == false) continue;

                Console.WriteLine("解{0}を発見。", ++AnswerCnt);
                Console.WriteLine(AnswerBan);
                continue;
            }

            Action<int, int> PushSyori = (pX, pY) =>
            {
                WillPush.CurrX = pX;
                WillPush.CurrY = pY;
                WillPush.SumVal = Popped.SumVal;

                //初回訪問なら値を加算
                if (Popped.IsSelectedArr[pX, pY] == false) {
                    WillPush.SumVal += MasuArr[pX, pY];
                    //総合計の半分を超えたら枝切り
                    if (WillPush.SumVal > AnswerSumVal) return;
                }

                WillPush.IsSelectedArr = (bool[,])Popped.IsSelectedArr.Clone();
                WillPush.IsSelectedArr[pX, pY] = true;
                //既存の状態なら枝切り
                if (IsAlreadyPushed(WillPush.IsSelectedArr, pX, pY) == false) return;

                stk.Push(WillPush);
            };

            //左に移動
            if (Popped.CurrX > 0)
                PushSyori(Popped.CurrX - 1, Popped.CurrY);
            //右に移動
            if (Popped.CurrX < MasuArr.GetUpperBound(0))
                PushSyori(Popped.CurrX + 1, Popped.CurrY);
            //上に移動
            if (Popped.CurrY > 0)
                PushSyori(Popped.CurrX, Popped.CurrY - 1);
            //下に移動
            if (Popped.CurrY < MasuArr.GetUpperBound(1))
                PushSyori(Popped.CurrX, Popped.CurrY + 1);
        }
    }

    static HashSet<string> StrBanSet = new HashSet<string>();
    static bool IsAlreadyPushed(bool[,] pIsSelectedArr, int pCurrX, int pCurrY)
    {
        var sb = new System.Text.StringBuilder();
        sb.AppendFormat("CurrX={0},CurrY={1},", pCurrX, pCurrY);
        for (int Y = 0; Y <= pIsSelectedArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pIsSelectedArr.GetUpperBound(0); X++) {
                if (pIsSelectedArr[X, Y])
                    sb.AppendFormat("({0},{1})", X, Y);
            }
        }
        return StrBanSet.Add(sb.ToString());
    }

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

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

        var stk = new Stack<PointDef>();
        PointDef WillPush;
        WillPush.X = pStaX;
        WillPush.Y = pStaY;
        VisitedSet.Add(string.Format("({0},{1})", pStaX, pStaY));
        stk.Push(WillPush);

        while (stk.Count > 0) {
            PointDef Popped = stk.Pop();
            bool CurrVal = pIsSelectedArr[Popped.X, Popped.Y];

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                //値が違ってたら対象外
                if (CurrVal != pIsSelectedArr[pNewX, pNewY]) return;

                //訪問済なら枝切り
                if (VisitedSet.Add(string.Format("({0},{1})", pNewX, 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 < MasuArr.GetUpperBound(0))
                PushSyori(Popped.X + 1, Popped.Y);
            //下に移動
            if (Popped.Y > 0)
                PushSyori(Popped.X, Popped.Y - 1);
            //上に移動
            if (Popped.Y < MasuArr.GetUpperBound(1))
                PushSyori(Popped.X, Popped.Y + 1);
        }
        return VisitedSet;
    }

    static string DeriveAnswerBan(bool[,] pIsSelectedArr)
    {
        string PrintBanStr = "";
        for (int Y = 0; Y <= pIsSelectedArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pIsSelectedArr.GetUpperBound(0); X++) {
                string FormatStr = pIsSelectedArr[X, Y] ? "[{0,2}]" : " {0,2} ";
                PrintBanStr += string.Format(FormatStr, MasuArr[X, Y]);
            }
            PrintBanStr += Environment.NewLine;
        }
        return PrintBanStr;
    }
}

実行結果

解1を発見。
[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10] 11  12
[13] 14  15  16

解2を発見。
[ 1][ 2][ 3]  4
[ 5][ 6]  7   8
[ 9] 10  11  12
[13][14][15] 16

解3を発見。
[ 1][ 2][ 3][ 4]
[ 5]  6   7 [ 8]
[ 9] 10 [11][12]
[13] 14  15  16

解4を発見。
[ 1][ 2][ 3]  4
[ 5]  6   7   8
[ 9][10][11] 12
[13][14] 15  16

解5を発見。
[ 1]  2   3   4
[ 5]  6   7   8
[ 9] 10 [11] 12
[13][14][15] 16

解6を発見。
[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9] 10 [11][12]
 13  14  15  16

解7を発見。
[ 1][ 2][ 3][ 4]
  5   6 [ 7][ 8]
  9  10  11 [12]
 13  14 [15][16]

解説

重複した要素を扱うことがなく、
重複のチェックも行う場合は、HashSetジェネリックを使うと便利です。