トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

20-056 2004年年賀パズル(問題1)

問題

小田原充宏さんの2004年年賀パズルの問題1を解きます。

問題1
 ここに1〜64が渦巻き状に書かれた板があります。
これを点線に沿って2つに分け、片方の板の数の和が2004になるようにしてください。
解はたくさんあります。全部見つけてください。



ソース

using System;
using System.Collections.Generic;

class Program
{
    const int NeedSum = 64 * (64 + 1) / 2 - 2004;

    const int UB = 7;
    static int[,] mQuestionArr = new int[UB + 1, UB + 1];

    //問題を定義
    static void QuestionDef()
    {
        //右向きが1,下向きが2,左向きが3,上向きが4
        int Muki = 1;
        int CurrX = 0, CurrY = 0;
        int CurrNum = 1;

        mQuestionArr[0, 0] = CurrNum++;
        while (true) {
            int HeniX = 0, HeniY = 0;
            if (Muki == 1) HeniX = 1;
            if (Muki == 2) HeniY = 1;
            if (Muki == 3) HeniX = -1;
            if (Muki == 4) HeniY = -1;

            int NewX = CurrX + HeniX;
            int NewY = CurrY + HeniY;
            if (NewX < 0 || UB < NewX || NewY < 0 || UB < NewY
             || mQuestionArr[NewX, NewY] > 0) {
                if (++Muki == 5) Muki = 1;
                continue;
            }
            mQuestionArr[NewX, NewY] = CurrNum++;
            CurrX = NewX;
            CurrY = NewY;
            if (CurrNum > 64) break;
        }
    }

    static void Main()
    {
        //問題を定義
        QuestionDef();

        var AnswerList = new List<JyoutaiDef>();

        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (X == 0 || X == UB || Y == 0 || Y == UB)
                    AnswerList.AddRange(ExecUnionFind(X, Y));
            }
        }
        for (int I = 0; I <= AnswerList.Count - 1; I++) {
            Console.WriteLine("配置{0}", I + 1);
            PrintBan(ExecReduceArr(AnswerList[I].BanArr));
        }
    }

    struct JyoutaiDef
    {
        internal int[,] BanArr;
        internal int SumVal;
    }

    static HashSet<string> mVisitedSet = new HashSet<string>();

    //始点の座標を引数をしてUnionFind
    static List<JyoutaiDef> ExecUnionFind(int pStaX, int pStaY)
    {
        var WillReturn = new List<JyoutaiDef>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new int[UB + 1, UB + 1];
        WillPush.BanArr[pStaX, pStaY] = mQuestionArr[pStaX, pStaY];
        WillPush.SumVal = mQuestionArr[pStaX, pStaY];
        Stk.Push(WillPush);

        mVisitedSet.Add(GetBanHash(WillPush.BanArr));
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.SumVal == NeedSum) {
                WillReturn.Add(Popped);
                continue;
            }

            var wkUsedFromPos = new HashSet<int>();

            for (int LoopX = 0; LoopX <= UB; LoopX++) {
                for (int LoopY = 0; LoopY <= UB; LoopY++) {
                    if (Popped.BanArr[LoopX, LoopY] == 0) continue;

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

                        if (Popped.BanArr[pNewX, pNewY] > 0) return;

                        WillPush.BanArr = (int[,])Popped.BanArr.Clone();
                        WillPush.BanArr[pNewX, pNewY] = mQuestionArr[pNewX, pNewY];
                        WillPush.SumVal = Popped.SumVal + mQuestionArr[pNewX, pNewY];

                        //再訪不可
                        if (mVisitedSet.Add(GetBanHash(WillPush.BanArr)) == false)
                            return;

                        //枝切り
                        if (WillPush.SumVal <= NeedSum)
                            Stk.Push(WillPush);
                    };
                    PushSyori(LoopX, LoopY - 1);
                    PushSyori(LoopX, LoopY + 1);
                    PushSyori(LoopX - 1, LoopY);
                    PushSyori(LoopX + 1, LoopY);
                    wkUsedFromPos.Add(GetPointHash(LoopX, LoopY));
                }
            }
        }
        return WillReturn;
    }

    static int GetPointHash(int pX, int pY)
    {
        return pX * (UB + 1) + pY;
    }

    static string GetBanHash(int[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                sb.AppendFormat("{0},", pBanArr[X, Y]);
            }
        }
        return sb.ToString();
    }

    //最小の2次元配列に縮小する
    static int[,] ExecReduceArr(int[,] pBanArr)
    {
        int[,] WillReturnArr;
        int XMin = pBanArr.GetUpperBound(0), YMin = pBanArr.GetUpperBound(1);
        int XMax = 0, YMax = 0;

        for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
                if (pBanArr[X, Y] == 0) continue;
                if (XMin > X) XMin = X;
                if (YMin > Y) YMin = Y;
                if (XMax < X) XMax = X;
                if (YMax < Y) YMax = Y;
            }
        }

        WillReturnArr = new int[XMax - XMin + 1, YMax - YMin + 1];
        for (int X = 0; X <= WillReturnArr.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= WillReturnArr.GetUpperBound(1); Y++) {
                WillReturnArr[X, Y] = pBanArr[XMin + X, YMin + Y];
            }
        }
        return WillReturnArr;
    }

    //盤面を出力
    static void PrintBan(int[,] 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++) {
                //if (pBanArr[X, Y] == 0) continue;
                sb.AppendFormat("{0,2},", pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

配置1
 1, 2, 3, 4, 5, 6, 7, 8,
 0, 0, 0,31, 0, 0, 0, 9,

配置2
 1, 2, 3, 4, 5, 6,
28, 0, 0, 0, 0, 0,
27, 0, 0, 0, 0, 0,

配置3
 1, 2, 3, 4, 5,
 0,29, 0, 0,32,

配置4
 1, 2, 3, 4, 5,
 0, 0,30,31, 0,

配置5
 2, 3, 4, 5, 6, 7, 8,
 0, 0, 0,32, 0, 0, 9,

配置6
 2, 3, 4, 5,
 0,30, 0,32,

配置7
 3, 4, 5, 6, 7, 8,
 0, 0, 0, 0,34, 9,

配置8
 0, 4, 5, 6,
30,31, 0, 0,

配置9
 5, 6,
32,33,

配置10
41, 0,
18,17,

配置11
 6, 7, 8,
 0, 0, 9,
 0, 0,10,
 0, 0,11,
 0, 0,12,
 0, 0,13,

配置12
 7,
34,
35,

配置13
34, 9,
 0,10,
 0,11,
 0,12,

配置14
33,34, 9,

配置15
37,12,
 0,13,
 0,14,


解説

1から64までの整数の和 - 2004 = 76
ですので、正方形の外周のいすれかのマスから
深さ優先探索で和が76になるマスの組み合わせを列挙してます。