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

Cマガ電脳クラブ(第115回) ラドクリフの六角陣

問題

Fig.1の19個の正六角形の中に、1から19までの19個の数すべてをダブりなく入れる。
このとき、左斜め・右斜め・横のいずれの方向も、和が38になるようにしたい。
何通りの配置が考えられるだろうか。
全体を回転した解や、裏返した解は別の解とはしない。

Fig.1 ラドクリフの六角陣


ソース

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

class Program
{
    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal int[][] BanArr;
        internal HashSet<int> UsedNumSet;
    }

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

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = 0;
        WillPush.CurrY = 0;

        //ジャグ配列で下記のデータ構造とする
        //  □□□
        // □□□□
        //□□□□□
        // □□□□
        //  □□□
        WillPush.BanArr = new int[5][];
        WillPush.BanArr[0] = new int[3];
        WillPush.BanArr[1] = new int[4];
        WillPush.BanArr[2] = new int[5];
        WillPush.BanArr[3] = new int[4];
        WillPush.BanArr[4] = new int[3];

        WillPush.UsedNumSet = new HashSet<int>();
        stk.Push(WillPush);

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

            if (++PopCnt % 1000000 == 1) {
                Console.WriteLine("{0}回目のPopを行いました。経過時間={1}", PopCnt, sw.Elapsed);
            }

            int UB_X = Popped.BanArr[Popped.CurrY].GetUpperBound(0);

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

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

            for (int I = 1; I <= 19; I++) {
                if (Popped.UsedNumSet.Contains(I)) continue;

                //対称解の除外で、正6角形の左上の頂点を最小とする
                if (Popped.CurrX == 2 && Popped.CurrY == 0)
                    if (Popped.BanArr[0][0] > I) continue;
                if (Popped.CurrX == 0 && Popped.CurrY == 2)
                    if (Popped.BanArr[0][0] > I) continue;
                if (Popped.CurrX == 4 && Popped.CurrY == 2)
                    if (Popped.BanArr[0][0] > I) continue;
                if (Popped.CurrX == 0 && Popped.CurrY == 4)
                    if (Popped.BanArr[0][0] > I) continue;
                if (Popped.CurrX == 2 && Popped.CurrY == 4)
                    if (Popped.BanArr[0][0] > I) continue;
                if (Popped.CurrX == 2 && Popped.CurrY == 4)
                    if (Popped.BanArr[0][0] > I) continue;
                //対称解の除外で、
                //左上の頂点から見た右の頂点 < 左上の頂点から見た左下の頂点とする
                if (Popped.CurrX == 0 && Popped.CurrY == 2)
                    if (Popped.BanArr[0][2] > I) continue;

                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.BanArr = ExecArrDeepCopy(Popped.BanArr, WillPush.CurrY);
                WillPush.BanArr[Popped.CurrY][Popped.CurrX] = I;
                WillPush.UsedNumSet = new HashSet<int>(Popped.UsedNumSet);
                WillPush.UsedNumSet.Add(I);

                //枝切り判定
                if (WillEdakiri(WillPush.BanArr, Popped.CurrX, Popped.CurrY) == false)
                    stk.Push(WillPush);
            }
        }
        Console.WriteLine("解は{0}通り。経過時間={1}", AnswerCnt, sw.Elapsed);
    }

    //ジャグ配列のディープコピーを返す
    static int[][] ExecArrDeepCopy(int[][] pArr, int pCurrY)
    {
        int[][] WillReturn = new int[pArr.GetUpperBound(0) + 1][];
        for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
            if (I == pCurrY)
                WillReturn[I] = (int[])pArr[I].Clone();
            else
                WillReturn[I] = pArr[I];
        }
        return WillReturn;
    }

    //枝切り判定
    static bool WillEdakiri(int[][] pBanArr, int pCurrX, int pCurrY)
    {
        //横方向の範囲チェック
        if (pCurrX == 2 && pCurrY == 1 && pBanArr[1].Sum() + 1 > 38) return true;
        if (pCurrX == 2 && pCurrY == 1 && pBanArr[1].Sum() + 19 < 38) return true;
        if (pCurrX == 2 && pCurrY == 2 && pBanArr[2].Sum() + 1 + 2 > 38) return true;
        if (pCurrX == 3 && pCurrY == 2 && pBanArr[2].Sum() + 1 > 38) return true;
        if (pCurrX == 3 && pCurrY == 2 && pBanArr[2].Sum() + 19 < 38) return true;
        if (pCurrX == 2 && pCurrY == 3 && pBanArr[3].Sum() + 1 > 38) return true;
        if (pCurrX == 2 && pCurrY == 3 && pBanArr[3].Sum() + 19 < 38) return true;

        //左下方向の範囲チェック
        if (pCurrX == 1 && pCurrY == 2) {
            int wkSum = pBanArr[0][1] + pBanArr[1][1] + pBanArr[2][1];
            if (wkSum + 1 > 38 || wkSum + 19 < 38)
                return true;
        }
        if (pCurrX == 2 && pCurrY == 2) {
            int wkSum = pBanArr[0][2] + pBanArr[1][2] + pBanArr[2][2];
            if (wkSum + 1 + 2 > 38)
                return true;
        }

        //右下方向の範囲チェック
        if (pCurrX == 2 && pCurrY == 2) {
            int wkSum = pBanArr[0][0] + pBanArr[1][1] + pBanArr[2][2];
            if (wkSum + 1 + 2 > 38)
                return true;
        }

        //横方向の合計チェック1
        if (pCurrX == 2 && pCurrY == 0 && pBanArr[0].Sum() != 38) return true;
        //横方向の合計チェック2
        if (pCurrX == 3 && pCurrY == 1 && pBanArr[1].Sum() != 38) return true;
        //横方向の合計チェック3
        if (pCurrX == 4 && pCurrY == 2 && pBanArr[2].Sum() != 38) return true;
        //横方向の合計チェック4
        if (pCurrX == 3 && pCurrY == 3 && pBanArr[3].Sum() != 38) return true;
        //横方向の合計チェック5
        if (pCurrX == 2 && pCurrY == 4 && pBanArr[4].Sum() != 38) return true;

        //左下方向の合計チェック1
        if (pCurrX == 0 && pCurrY == 2) {
            if (pBanArr[0][0] + pBanArr[1][0] + pBanArr[2][0] != 38)
                return true;
        }
        //左下方向の合計チェック2
        if (pCurrX == 0 && pCurrY == 3) {
            if (pBanArr[0][1] + pBanArr[1][1] + pBanArr[2][1] + pBanArr[3][0] != 38)
                return true;
        }
        //左下方向の合計チェック3
        if (pCurrX == 0 && pCurrY == 4) {
            if (pBanArr[0][2] + pBanArr[1][2] + pBanArr[2][2] + pBanArr[3][1] + pBanArr[4][0] != 38)
                return true;
        }
        //左下方向の合計チェック4
        if (pCurrX == 1 && pCurrY == 4) {
            if (pBanArr[1][3] + pBanArr[2][3] + pBanArr[3][2] + pBanArr[4][1] != 38)
                return true;
        }
        //左下方向の合計チェック5
        if (pCurrX == 2 && pCurrY == 4) {
            if (pBanArr[2][4] + pBanArr[3][3] + pBanArr[4][2] != 38)
                return true;
        }

        //右下方向の合計チェック1
        if (pCurrX == 4 && pCurrY == 2) {
            if (pBanArr[0][2] + pBanArr[1][3] + pBanArr[2][4] != 38)
                return true;
        }
        //右下方向の合計チェック2
        if (pCurrX == 3 && pCurrY == 3) {
            if (pBanArr[0][1] + pBanArr[1][2] + pBanArr[2][3] + pBanArr[3][3] != 38)
                return true;
        }
        //右下方向の合計チェック3
        if (pCurrX == 2 && pCurrY == 4) {
            if (pBanArr[0][0] + pBanArr[1][1] + pBanArr[2][2] + pBanArr[3][2] + pBanArr[4][2] != 38)
                return true;
        }
        //右下方向の合計チェック4
        if (pCurrX == 1 && pCurrY == 4) {
            if (pBanArr[1][0] + pBanArr[2][1] + pBanArr[3][1] + pBanArr[4][1] != 38)
                return true;
        }
        //右下方向の合計チェック5
        if (pCurrX == 0 && pCurrY == 4) {
            if (pBanArr[2][0] + pBanArr[3][0] + pBanArr[4][0] != 38)
                return true;
        }

        return false;
    }

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

        for (int I = 0; I <= pBanArr.GetUpperBound(0); I++) {
            if (pBanArr[I].Length == 3) sb.Append(new string(' ', 3));
            if (pBanArr[I].Length == 4) sb.Append(new string(' ', 1));
            foreach (int EachInt in pBanArr[I]) {
                sb.AppendFormat("{0,2},", EachInt);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

1回目のPopを行いました。経過時間=00:00:00.0030811
1000001回目のPopを行いました。経過時間=00:00:28.2666336
2000001回目のPopを行いました。経過時間=00:00:59.5157744
3000001回目のPopを行いました。経過時間=00:01:31.9194168
4000001回目のPopを行いました。経過時間=00:02:08.3223105
解1を発見。経過時間=00:02:20.2983652
    3,19,16,
 17, 7, 2,12,
18, 1, 5, 4,10,
 11, 6, 8,13,
    9,14,15,

解は1通り。経過時間=00:02:23.4684776


解説

細かく枝切りして、計算量を減らしてます。

Wiki --- 魔六角陣