Cマガ電脳クラブ(第137回) Ultimate Instant Insanity

問題

Fig.1のように、立方体の展開図がある。各面には色が塗ってあり、Rは赤、Gは緑、Bは青、Yは黄、Wは白である。
これを組み立てた5つの立方体を、Fig.2のように一直線に並べる。

このとき、5つの正方形が並んだ面が4面できることになるが、それぞれの面にすべての色が出現するようにしたい。
何通りの並べ方があるか。
ただし、全体を回転したり、立方体の順番を入れ替えたものは別の解とはしない。

   

ソース

using System;
using System.Collections.Generic;

class Program
{
    static Dictionary<int, List<char[]>> Use4MenArrListDict =
        new Dictionary<int, List<char[]>>();

    const int UB = 3;

    struct JyoutaiDef
    {
        internal int Level;
        internal List<char[]> CubeHaitiList; //要素数が4の配列のList
    }

    static void Main()
    {
        DeriveUse4MenArrListDict();

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

        WillPush.Level = 1;
        foreach (char[] Each4MenArr in Use4MenArrListDict[0]) {
            WillPush.CubeHaitiList = new List<char[]>() { Each4MenArr };
            stk.Push(WillPush);
        }

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

            //解判定
            if (Popped.Level == 5) {
                Console.WriteLine("解{0}を発見", ++AnswerCnt);
                PrintBan(Popped.CubeHaitiList);
                continue;
            }

            WillPush.Level = Popped.Level + 1;
            foreach (char[] Each4MenArr in Use4MenArrListDict[Popped.Level]) {
                WillPush.CubeHaitiList = new List<char[]>(Popped.CubeHaitiList) { Each4MenArr };

                //枝切り
                if (IsValid(WillPush.CubeHaitiList) == false) continue;

                stk.Push(WillPush);
            }
        }
    }

    //5つの立方体の、使用する4面の候補を求める
    static void DeriveUse4MenArrListDict()
    {
        //この展開図と配列の添字を対応させて、5つの立方体の展開図を定義
        // 0
        //123
        // 4
        // 5

        var wk6MenArrList = new List<char[]>();
        wk6MenArrList.Add(new char[] { 'W', 'R', 'Y', 'B', 'G', 'R' });
        wk6MenArrList.Add(new char[] { 'G', 'Y', 'R', 'W', 'B', 'Y' });
        wk6MenArrList.Add(new char[] { 'W', 'R', 'G', 'Y', 'G', 'B' });
        wk6MenArrList.Add(new char[] { 'B', 'G', 'W', 'R', 'Y', 'B' });
        wk6MenArrList.Add(new char[] { 'W', 'W', 'Y', 'B', 'R', 'G' });

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

        //回転解の除外で1つめのキューブの配置は、24通りではなく3通りとする
        Use4MenArrListDict[0].RemoveRange(17, 7);
        Use4MenArrListDict[0].RemoveRange(9, 7);
        Use4MenArrListDict[0].RemoveRange(1, 7);
    }

    //1つの立方体の、使用する4面の候補を求める
    static List<char[]> DeriveUse4MenArrList(char[] p6MenArr)
    {
        var WillReturn = new List<char[]>();

        Action<int, int> wkAct = (pDelInd1, pDelInd2) =>
        {
            var wk4MenList = new List<char>(p6MenArr);

            //2と5以外の4面を使用する場合は、番号順にならないので入れ替え
            if (pDelInd1 == 2 && pDelInd2 == 5) {
                char wkChar = wk4MenList[3];
                wk4MenList[3] = wk4MenList[4];
                wk4MenList[4] = wkChar;
            }

            wk4MenList.RemoveAt(Math.Max(pDelInd1, pDelInd2));
            wk4MenList.RemoveAt(Math.Min(pDelInd1, pDelInd2));

            WillReturn.AddRange(DeriveUse4MenArr(wk4MenList.ToArray()));
        };

        wkAct(0, 4); //0と4以外の4面を使用
        wkAct(1, 3); //1と3以外の4面を使用
        wkAct(2, 5); //2と5以外の4面を使用
        return WillReturn;
    }

    //使用する4面の組み合わせを求める(8通り)
    static List<char[]> DeriveUse4MenArr(char[] p4MenArr)
    {
        var WillReturn = new List<char[]>();

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

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

    //有効な状態かを返す
    static bool IsValid(List<char[]> pCubeHaitiList)
    {
        for (int I = 0; I <= UB; I++) {
            var wkHashSet = new HashSet<char>();
            for (int J = 0; J <= pCubeHaitiList.Count - 1; J++) {
                if (wkHashSet.Add(pCubeHaitiList[J][I]) == false) return false;
            }
        }
        return true;
    }

    //盤面を表示
    static void PrintBan(List<char[]> pCubeHaitiList)
    {
        var sb = new System.Text.StringBuilder();

        for (int I = 0; I <= UB; I++) {
            for (int J = 0; J <= pCubeHaitiList.Count - 1; J++) {
                sb.Append(pCubeHaitiList[J][I]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

解1を発見
WGYBR
RYWBG
GBRYW
BRGWY

解2を発見
WGYBR
YWGRB
GBRYW
RYBGW

解3を発見
RYWBG
YWGRB
BRGWY
RYBGW

解説

23-01 時間どろぼうのソースを流用して、
5個のダイスの定義部分のみ変更してます。