Cマガ電脳クラブ(第164回) ミスティック・エイト

問題

　8個の立方体の各面に1から48までの数が書いてある。
その数の配列を展開図で示したのがFig.1で、数の書かれた面が立方体の表側である。

これを、Fig.2のような2×2×2の大きな立方体に組んで、
その外側に見えている各面の4つの数の和を6面とも同じにしたい。

　解の数は意外に多く、6面とも同じにする和(定和と呼ぶ)もいろいろな値にして組むことができる。
そこで今回は、この定和を指定したときに、
解(組み合わせ)の数がもっとも少なくなる定和をお答えいただきたい(もちろんそのときの解の数も)。
この「最少解を持つ定和」が複数ある場合はすべてあげること。
なお、解の数え方として、全体を回転しただけのものは別の解としてカウントしない。

　　Fig.1　8個の立方体の展開図

　(ａ)　　　　(ｂ)　　　　(ｃ)　　　　(ｄ)
　 13　　　　　47　　　　　４　　　　　48
25 １ ３　　29 15 37　　６ ２ 42　　38 14 20
 　11　　　　　21　　　　　16　　　　　44
 　19　　　　　43　　　　　36　　　　　30

　(ｅ)　　　　(ｆ)　　　　(ｇ)　　　　(ｈ)
 　27　　　　　17　　　　　28　　　　　46
33 ５ ９　　23 ７ 35　　32 ８ 34　　24 10 26
 　31　　　　　39　　　　　12　　　　　22
 　41　　　　　45　　　　　18　　　　　40

Fig.2　2×2×2の立方体

ソース

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

class Program
{
    //ダイス番号(1〜8)と、6面の配置候補の配列のList
    static Dictionary<int, List<int[]>> Use6MenArrListDict =
        new Dictionary<int, List<int[]>>();

    struct JyoutaiDef
    {
        internal int Teiwa;
        internal int Level;
        internal List<int> SetDiceNo; //配置したダイス番号
        internal List<int[]> Set6MenArrList; //配置したダイスの展開図のList
    }
    static List<JyoutaiDef> mAnswerKouhoList = new List<JyoutaiDef>();
    static HashSet<int> mNGTeiwaSet = new HashSet<int>();

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

        DeriveUse6MenArrListDict();

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

        WillPush.Teiwa = -1;
        WillPush.Level = 0;
        WillPush.SetDiceNo = new List<int>();
        WillPush.Set6MenArrList = new List<int[]>();
        Stk.Push(WillPush);

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

            if (mNGTeiwaSet.Contains(Popped.Teiwa)) continue;
            if (mAnswerKouhoList.Count(X => X.Teiwa == Popped.Teiwa) >= 2) {
                mNGTeiwaSet.Add(Popped.Teiwa);
                mAnswerKouhoList.RemoveAll(X => X.Teiwa == Popped.Teiwa);
                continue;
            }

            if (Popped.Level == 8) {
                mAnswerKouhoList.Add(Popped);
                Console.WriteLine("定和={0}の解候補を発見。{1}", Popped.Teiwa, sw.Elapsed);
                continue;
            }

            WillPush.Level = Popped.Level + 1;
            WillPush.Teiwa = Popped.Teiwa;
            foreach (var EachPair in Use6MenArrListDict) {
                //最初に配置するダイスは、固定で1番とする
                if (WillPush.Level == 1 && EachPair.Key != 1) continue;

                if (Popped.SetDiceNo.Contains(EachPair.Key)) continue;

                var UseNumSet = new HashSet<string>();
                foreach (int[] EachKouhoArr in EachPair.Value) {
                    //回転解の除外
                    if (WillPush.Level == 1) {
                        var UseIndList = new List<int>();
                        UseIndList.Add(EachKouhoArr[0]);
                        UseIndList.Add(EachKouhoArr[1]);
                        UseIndList.Add(EachKouhoArr[2]);
                        UseIndList.Sort();
                        if (UseNumSet.Add(
                            string.Format("{0}{1}{2}",
                            UseIndList[0], UseIndList[1], UseIndList[2])) == false)
                            continue;
                    }
                    WillPush.SetDiceNo = new List<int>(Popped.SetDiceNo) { EachPair.Key };
                    WillPush.Set6MenArrList = new List<int[]>(Popped.Set6MenArrList);
                    WillPush.Set6MenArrList.Add(EachKouhoArr);
                    bool GuukiDiff;
                    if (IsValid(WillPush.SetDiceNo, WillPush.Set6MenArrList, ref WillPush.Teiwa,
                                out GuukiDiff) == false) {
                        if (GuukiDiff) break; //定和と2で偶奇が違ったらBreak
                        continue;
                    }
                    Stk.Push(WillPush);
                }
            }
        }
        mAnswerKouhoList.Sort((A, B) => A.Teiwa.CompareTo(B.Teiwa));
        for (int I = 0; I <= mAnswerKouhoList.Count - 1; I++) {
            Console.WriteLine("解{0}。定和={1}", I + 1, mAnswerKouhoList[I].Teiwa);
            PrintAnswer(mAnswerKouhoList[I]);
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //8つのダイスの、使用する6面の候補を求める
    static void DeriveUse6MenArrListDict()
    {
        //この展開図と配列の添字を対応させて、8つのダイスの展開図を定義
        // 0
        //123
        // 4
        // 5

        var wk6MenArrList = new List<int[]>();
        wk6MenArrList.Add(new int[] { 13, 25, 01, 03, 11, 19 });
        wk6MenArrList.Add(new int[] { 47, 29, 15, 37, 21, 43 });
        wk6MenArrList.Add(new int[] { 04, 06, 02, 42, 16, 36 });
        wk6MenArrList.Add(new int[] { 48, 38, 14, 20, 44, 30 });
        wk6MenArrList.Add(new int[] { 27, 33, 05, 09, 31, 41 });
        wk6MenArrList.Add(new int[] { 17, 23, 07, 35, 39, 45 });
        wk6MenArrList.Add(new int[] { 28, 32, 08, 34, 12, 18 });
        wk6MenArrList.Add(new int[] { 46, 24, 10, 26, 22, 40 });

        for (int I = 0; I <= wk6MenArrList.Count - 1; I++) {
            Use6MenArrListDict[I + 1] = DeriveUse6MenArrList(wk6MenArrList[I]);
        }
    }

    //1つのダイスの、配置の候補を求める(ダイス1つにつき24通り)
    static List<int[]> DeriveUse6MenArrList(int[] p6MenArr)
    {
        var WillReturn = new List<int[]>();

        Action<int, int, int[]> wkAct = (pSokumenInd1, pSokumenInd2, pIndArr) =>
        {
            var wk4MenArr = new int[4];
            wk4MenArr[0] = p6MenArr[pIndArr[0]];
            wk4MenArr[1] = p6MenArr[pIndArr[1]];
            wk4MenArr[2] = p6MenArr[pIndArr[2]];
            wk4MenArr[3] = p6MenArr[pIndArr[3]];

            WillReturn.AddRange(DeriveUse4MenArrList(p6MenArr[pSokumenInd1],
                p6MenArr[pSokumenInd2], wk4MenArr));
        };

        wkAct(0, 4, new int[] { 3, 2, 1, 5 }); //0と4を側面としてダイスを配置
        wkAct(1, 3, new int[] { 0, 2, 4, 5 }); //1と3を側面としてダイスを配置
        wkAct(2, 5, new int[] { 3, 4, 1, 0 }); //2と5を側面としてダイスを配置
        return WillReturn;
    }

    //使用する4面の並び順を求める(8通り)
    static List<int[]> DeriveUse4MenArrList(int pSokumen1, int pSokumen2, int[] p4MenArr)
    {
        const int UB = 3;
        var WillReturn = new List<int[]>();

        //正順と逆順での共通処理
        Action<List<int>, bool> CommonAct = (pWKList, pIsRev) =>
        {
            int[] WillAddArr = new int[6];
            WillAddArr[0] = pWKList[0];
            WillAddArr[2] = pWKList[1];
            WillAddArr[4] = pWKList[2];
            WillAddArr[5] = pWKList[3];
            if (pIsRev) {
                WillAddArr[1] = pSokumen2; WillAddArr[3] = pSokumen1;
            }
            else {
                WillAddArr[1] = pSokumen1; WillAddArr[3] = pSokumen2;
            }
            WillReturn.Add(WillAddArr);
        };

        //正順の4つ
        for (int StaPos = 0; StaPos <= UB; StaPos++) {
            var WKList = new List<int>();
            for (int KasanP = 0; KasanP <= UB; KasanP++) {
                int TargetPos = StaPos + KasanP;
                if (TargetPos > UB) TargetPos -= (UB + 1);
                WKList.Add(p4MenArr[TargetPos]);
            }
            CommonAct(WKList, false);
        }

        //逆順の4つ
        for (int StaPos = 0; StaPos <= UB; StaPos++) {
            var WKList = new List<int>();
            for (int GenzanP = 0; GenzanP <= UB; GenzanP++) {
                int TargetPos = StaPos - GenzanP;
                if (TargetPos < 0) TargetPos += (UB + 1);
                WKList.Add(p4MenArr[TargetPos]);
            }
            CommonAct(WKList, true);
        }
        return WillReturn;
    }

    //上段左後  上段右後
    //上段左前  上段右前
    //下段左後  下段右後
    //下段左前  下段右前
    //の順番でダイスを配置するので、有効な状態かをチェックする
    static bool IsValid(List<int> pSetDiceNo, List<int[]> pSet6MenArrList, 
                        ref int pTeiwa, out bool pGuukiDiff)
    {
        pGuukiDiff = false;
        if (pSet6MenArrList.Count <= 3) return true;

        //未使用ダイスの最小値と最大値のList
        var NonUseMinList = new List<int>();
        var NonUseMaxList = new List<int>();
        foreach (var EachPair in Use6MenArrListDict) {
            if (pSetDiceNo.Contains(EachPair.Key)) continue;
            NonUseMinList.Add(EachPair.Value[0].Min());
            NonUseMaxList.Add(EachPair.Value[0].Max());
        }
        NonUseMinList.Sort();
        NonUseMaxList.Sort((A, B) => B.CompareTo(A));

        int MinSum1 = (NonUseMinList.Count == 0 ? 0 : NonUseMinList.First());
        int MinSum2 = NonUseMinList.Take(2).Sum();
        int MinSum3 = NonUseMinList.Take(3).Sum();
        int MaxSum1 = (NonUseMaxList.Count == 0 ? 0 : NonUseMaxList.First());
        int MaxSum2 = NonUseMaxList.Take(2).Sum();
        int MaxSum3 = NonUseMaxList.Take(3).Sum();

        Func<int[], int, int> DeriveSum = (pIndArr, pMenInd) =>
        {
            int WillReturn = 0;
            foreach (int EachInd in pIndArr) {
                WillReturn += pSet6MenArrList[EachInd][pMenInd];
            }
            return WillReturn;
        };

        //上段右前の配置
        if (pSet6MenArrList.Count == 4) {
            int wkTeiwa = DeriveSum(new int[] { 0, 1, 2, 3 }, 2);

            if (mNGTeiwaSet.Contains(wkTeiwa)) return false;
            if (mAnswerKouhoList.Count(X => X.Teiwa == wkTeiwa) >= 2) {
                mNGTeiwaSet.Add(wkTeiwa);
                mAnswerKouhoList.RemoveAll(X => X.Teiwa == wkTeiwa);
                return false;
            }

            if (wkTeiwa < MinSum2 + DeriveSum(new int[] { 0, 1 }, 0)) return false;
            if (wkTeiwa > MaxSum2 + DeriveSum(new int[] { 0, 1 }, 0)) return false;

            if (wkTeiwa < MinSum2 + DeriveSum(new int[] { 0, 2 }, 1)) return false;
            if (wkTeiwa > MaxSum2 + DeriveSum(new int[] { 0, 2 }, 1)) return false;

            if (wkTeiwa < MinSum2 + DeriveSum(new int[] { 1, 3 }, 3)) return false;
            if (wkTeiwa > MaxSum2 + DeriveSum(new int[] { 1, 3 }, 3)) return false;

            if (wkTeiwa < MinSum2 + DeriveSum(new int[] { 2, 3 }, 4)) return false;
            if (wkTeiwa > MaxSum2 + DeriveSum(new int[] { 2, 3 }, 4)) return false;

            pTeiwa = wkTeiwa;
        }

        //下段左後の配置
        if (pSet6MenArrList.Count == 5) {
            if (pTeiwa < MinSum1 + DeriveSum(new int[] { 0, 2, 4 }, 1)) return false;
            if (pTeiwa > MaxSum1 + DeriveSum(new int[] { 0, 2, 4 }, 1)) return false;

            if (pTeiwa < MinSum1 + DeriveSum(new int[] { 0, 1, 4 }, 0)) return false;
            if (pTeiwa > MaxSum1 + DeriveSum(new int[] { 0, 1, 4 }, 0)) return false;
        }

        //下段右後の配置
        if (pSet6MenArrList.Count == 6) {
            int wkSum = DeriveSum(new int[] { 0, 1, 4, 5 }, 0);
            if (pTeiwa != wkSum) {
                pGuukiDiff = (pTeiwa % 2 != wkSum % 2);
                return false;
            }
            if (pTeiwa < MinSum1 + DeriveSum(new int[] { 1, 3, 5 }, 3)) return false;
            if (pTeiwa > MaxSum1 + DeriveSum(new int[] { 1, 3, 5 }, 3)) return false;

            if (pTeiwa < MinSum3 + DeriveSum(new int[] { 4, 5 }, 5)) return false;
            if (pTeiwa > MaxSum3 + DeriveSum(new int[] { 4, 5 }, 5)) return false;
        }

        //下段左前の配置
        if (pSet6MenArrList.Count == 7) {
            int wkSum = DeriveSum(new int[] { 0, 2, 4, 6 }, 1);
            if (pTeiwa != wkSum) {
                pGuukiDiff = (pTeiwa % 2 != wkSum % 2);
                return false;
            }
            if (pTeiwa < MinSum1 + DeriveSum(new int[] { 4, 5, 6 }, 5)) return false;
            if (pTeiwa > MaxSum1 + DeriveSum(new int[] { 4, 5, 6 }, 5)) return false;

            if (pTeiwa < MinSum1 + DeriveSum(new int[] { 2, 3, 6 }, 4)) return false;
            if (pTeiwa > MaxSum1 + DeriveSum(new int[] { 2, 3, 6 }, 4)) return false;
        }

        //下段右前の配置
        if (pSet6MenArrList.Count == 8) {
            int wkSum = DeriveSum(new int[] { 2, 3, 6, 7 }, 4);
            if (pTeiwa != wkSum) {
                pGuukiDiff = (pTeiwa % 2 != wkSum % 2);
                return false;
            }
            wkSum = DeriveSum(new int[] { 1, 3, 5, 7 }, 3);
            if (pTeiwa != wkSum) {
                pGuukiDiff = (pTeiwa % 2 != wkSum % 2);
                return false;
            }
            wkSum = DeriveSum(new int[] { 4, 5, 6, 7 }, 5);
            if (pTeiwa != wkSum) {
                pGuukiDiff = (pTeiwa % 2 != wkSum % 2);
                return false;
            }
        }
        return true;
    }

    //配置したダイスを展開図で表示する
    //上段左後  上段右後
    //上段左前  上段右前
    //下段左後  下段右後
    //下段左前  下段右前
    //の順番で展開図を表示する
    static void PrintAnswer(JyoutaiDef pJyoutaiDef)
    {
        Action<int> PrintPairTenkaizu = pBaseSoeji =>
        {
            var sb = new System.Text.StringBuilder();
            sb.AppendFormat("Dice{0}       Dice{1}",
                pJyoutaiDef.SetDiceNo[pBaseSoeji], pJyoutaiDef.SetDiceNo[pBaseSoeji + 1]);
            sb.AppendLine();

            Action<int> CommonSyori = (pTargetMen) =>
            {
                sb.AppendFormat("   {0,2}          {1,2}",
                    pJyoutaiDef.Set6MenArrList[pBaseSoeji][pTargetMen],
                    pJyoutaiDef.Set6MenArrList[pBaseSoeji + 1][pTargetMen]);
                sb.AppendLine();
            };

            CommonSyori(0);

            sb.AppendFormat("{0,2} {1,2} {2,2}    {3,2} {4,2} {5,2}",
                pJyoutaiDef.Set6MenArrList[pBaseSoeji][1],
                pJyoutaiDef.Set6MenArrList[pBaseSoeji][2],
                pJyoutaiDef.Set6MenArrList[pBaseSoeji][3],
                pJyoutaiDef.Set6MenArrList[pBaseSoeji + 1][1],
                pJyoutaiDef.Set6MenArrList[pBaseSoeji + 1][2],
                pJyoutaiDef.Set6MenArrList[pBaseSoeji + 1][3]);
            sb.AppendLine();

            CommonSyori(4);
            CommonSyori(5);

            Console.WriteLine(sb.ToString());
        };

        for (int I = 0; I <= pJyoutaiDef.SetDiceNo.Count - 1; I += 2) {
            if (I == 0) Console.WriteLine("上段左後と上段右後の展開図");
            if (I == 2) Console.WriteLine("上段左前と上段右前の展開図");
            if (I == 4) Console.WriteLine("下段左後と下段右後の展開図");
            if (I == 6) Console.WriteLine("下段左前と下段右前の展開図");
            PrintPairTenkaizu(I);
        }
    }
}

実行結果

省略
定和=64の解候補を発見。00:11:48.1682685
定和=62の解候補を発見。00:12:35.9144413
定和=65の解候補を発見。00:14:22.5786768
定和=133の解候補を発見。00:17:24.3405969
定和=133の解候補を発見。00:17:28.4452786
解1。定和=62
上段左後と上段右後の展開図
Dice1       Dice4
    1          20
11  3 13    30 48 14
   19          38
   25          44

上段左前と上段右前の展開図
Dice5       Dice3
   31          36
 9  5 33    16  6  4
   27           2
   41          42

下段左後と下段右後の展開図
Dice7       Dice2
   12          29
32 18 34    47 43 21
   28          37
    8          15

下段左前と下段右前の展開図
Dice8       Dice6
   24          45
10 46 40    35 39 23
   26           7
   22          17

解2。定和=63
上段左後と上段右後の展開図
Dice1       Dice7
    1          12
11  3 13    34  8 32
   19          28
   25          18

上段左前と上段右前の展開図
Dice4       Dice3
   38          42
14 48 30    36  4  2
   20           6
   44          16

下段左後と下段右後の展開図
Dice6       Dice5
   23          27
17 45 39    41 33  5
   35          31
    7           9

下段左前と下段右前の展開図
Dice2       Dice8
   43          46
21 29 47    26 40 24
   15          22
   37          10

経過時間=00:22:39.9818041

解説

深さ優先探索でダイスを配置してます。

ベクトルの外積を使えば、計算量が減るらしいので
数学の勉強後に、速度改善したい。