Cマガ電脳クラブ(第023回) マッチング・パズル

問題

Fig.1のように、各辺にaからfの文字が書かれた正六角形の板が7枚ある。
これをFig.2のように配置するのだが、同じ文字の辺が接するように、というのが条件だ。

何通りの置き方があるだろうか。
ただし、板の裏面の各辺には、それぞれ表と同じ文字が書かれており、裏返して使うことが可能である。

     

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Level;
        internal List<int> NoList; //使用済の板のList
        internal List<char[]> StrArrList; //文字の配置配列のList
    }

    //板を回転、裏返ししたDict
    static Dictionary<int, List<char[]>> KaitenItaDict = new Dictionary<int, List<char[]>>();

    static void Main()
    {
        for (int I = 1; I <= 7; I++) KaitenItaDict[I] = DeriveItaArrList(I);

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

        foreach (var AnyPair in KaitenItaDict) {
            WillPush.Level = 1;
            WillPush.NoList = new List<int>() { AnyPair.Key };

            AnyPair.Value.ForEach(X =>
            {
                WillPush.StrArrList = new List<char[]>() { X };
                stk.Push(WillPush);
            });
        }

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

            if (Popped.Level == 7) {
                Console.WriteLine("解{0}を発見", ++AnswerCnt);
                PrintAnswer(Popped.NoList, Popped.StrArrList);
                continue;
            }

            foreach (var AnyPair in KaitenItaDict) {
                if (Popped.NoList.Contains(AnyPair.Key)) continue; //使用済の板は除外

                WillPush.Level = Popped.Level + 1;
                WillPush.NoList = new List<int>(Popped.NoList) { AnyPair.Key };

                //回転解の除外で、中央の板は回転も裏返しもせずに配置
                if (WillPush.Level == 4) {
                    WillPush.StrArrList = new List<char[]>(Popped.StrArrList);
                    WillPush.StrArrList.Add(AnyPair.Value[0]);
                    if (IsValid(WillPush)) stk.Push(WillPush);
                    continue;
                }

                AnyPair.Value.ForEach(X =>
                {
                    WillPush.StrArrList = new List<char[]>(Popped.StrArrList) { X };
                    if (IsValid(WillPush)) stk.Push(WillPush);
                });
            }
        }
    }

    //裏返しと回転を含む板の配列のListを返す
    static List<char[]> DeriveItaArrList(int pNo)
    {
        char[] BaseStrArr;
        if (pNo == 1) BaseStrArr = "decbfa".ToCharArray();
        else if (pNo == 2) BaseStrArr = "acdfeb".ToCharArray();
        else if (pNo == 3) BaseStrArr = "dabfce".ToCharArray();
        else if (pNo == 4) BaseStrArr = "bcadef".ToCharArray();
        else if (pNo == 5) BaseStrArr = "defabc".ToCharArray();
        else if (pNo == 6) BaseStrArr = "fdcbae".ToCharArray();
        else BaseStrArr = "debfca".ToCharArray();

        var ItaArrList = new List<char[]>();
        int StrArrUB = BaseStrArr.GetUpperBound(0);

        //始点変更の分
        Action<char[]> AddSitenhenkouHaiti = pStrArr =>
        {
            for (int BaseInd = 0; BaseInd <= StrArrUB; BaseInd++) {
                char[] WillAdd = new char[StrArrUB + 1];
                for (int I = 0; I <= StrArrUB; I++) {
                    int FromInd = I + BaseInd;
                    if (FromInd > StrArrUB) FromInd -= (StrArrUB + 1);
                    WillAdd[I] = pStrArr[FromInd];
                }
                ItaArrList.Add(WillAdd);
            }
        };

        //始点変更の分
        AddSitenhenkouHaiti(BaseStrArr);

        //回転と始点変更の分
        char[] RevBaseStrArr = new char[StrArrUB + 1];
        RevBaseStrArr[0] = BaseStrArr[5];
        RevBaseStrArr[1] = BaseStrArr[4];
        RevBaseStrArr[2] = BaseStrArr[3];
        RevBaseStrArr[3] = BaseStrArr[2];
        RevBaseStrArr[4] = BaseStrArr[1];
        RevBaseStrArr[5] = BaseStrArr[0];
        AddSitenhenkouHaiti(RevBaseStrArr);

        return ItaArrList;
    }

    //有効な状態かを返す
    static bool IsValid(JyoutaiDef pJyoutaiDef)
    {
        if (pJyoutaiDef.Level == 2) { //右上の六角形
            if (pJyoutaiDef.StrArrList[1][4] != pJyoutaiDef.StrArrList[0][1]) return false;
        }
        if (pJyoutaiDef.Level == 3) { //左の六角形
            if (pJyoutaiDef.StrArrList[2][0] != pJyoutaiDef.StrArrList[0][3]) return false;
        }
        if (pJyoutaiDef.Level == 4) { //中央の六角形
            if (pJyoutaiDef.StrArrList[3][0] != pJyoutaiDef.StrArrList[1][3]) return false;
            if (pJyoutaiDef.StrArrList[3][4] != pJyoutaiDef.StrArrList[2][1]) return false;
            if (pJyoutaiDef.StrArrList[3][5] != pJyoutaiDef.StrArrList[0][2]) return false;
        }
        if (pJyoutaiDef.Level == 5) { //右の六角形
            if (pJyoutaiDef.StrArrList[4][4] != pJyoutaiDef.StrArrList[3][1]) return false;
            if (pJyoutaiDef.StrArrList[4][5] != pJyoutaiDef.StrArrList[1][2]) return false;
        }
        if (pJyoutaiDef.Level == 6) { //左下の六角形
            if (pJyoutaiDef.StrArrList[5][0] != pJyoutaiDef.StrArrList[3][3]) return false;
            if (pJyoutaiDef.StrArrList[5][5] != pJyoutaiDef.StrArrList[2][2]) return false;
        }
        if (pJyoutaiDef.Level == 7) { //右下の六角形
            if (pJyoutaiDef.StrArrList[6][0] != pJyoutaiDef.StrArrList[4][3]) return false;
            if (pJyoutaiDef.StrArrList[6][4] != pJyoutaiDef.StrArrList[5][1]) return false;
            if (pJyoutaiDef.StrArrList[6][5] != pJyoutaiDef.StrArrList[3][2]) return false;
        }
        return true;
    }

    //解を表示
    static void PrintAnswer(List<int> pSetNoList, List<char[]> pStrArrList)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= pSetNoList.Count - 1; I++) {
            sb.AppendFormat("{0}枚目 ", I + 1);
            if (I == 0) sb.Append("(左上) ");
            if (I == 1) sb.Append("(右上) ");
            if (I == 2) sb.Append("(左  ) ");
            if (I == 3) sb.Append("(中央) ");
            if (I == 4) sb.Append("(右  ) ");
            if (I == 5) sb.Append("(左下) ");
            if (I == 6) sb.Append("(右下) ");

            sb.AppendFormat("板番号={0}  ", pSetNoList[I]);

            Array.ForEach(pStrArrList[I], X => sb.AppendFormat("{0} ", X));
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

実行結果

解1を発見
1枚目 (左上) 板番号=1  a f b c e d
2枚目 (右上) 板番号=5  d c b a f e
3枚目 (左  ) 板番号=3  c e d a b f
4枚目 (中央) 板番号=2  a c d f e b
5枚目 (右  ) 板番号=4  f e d a c b
6枚目 (左下) 板番号=6  f e a b c d
7枚目 (右下) 板番号=7  a c f b e d

解説

回転解の除外で、中央の板は回転も裏返しもせずに配置してます。