Cマガ電脳クラブ(第149回) マッチ方陣

問題

マッチ棒をFig.1のように並べると，カドまたは交差点が16個できる。
この16を4×4の魔方陣に見立てて，
マッチの「頭」の数を魔方陣のように縦4本，横4本，斜め2本の列で同じにして並べたい。
全体を回転したものや鏡像のものは別の解とはしないで，全部で何通りの並べ方があるだろうか。

Fig.1では，縦，横，そして斜め1本ではどこも6個になっているが，
破線で示したところだけ8個になっていて，惜しくも失敗している。

Fig.1　マッチ方陣(失敗例)
　　　　　　　　　／
　　・←・←・→・
　　↑　↓　↑／↑
　　・→・→・→・
　　↓　↓／↑　↑
　　・←・←・→・
　　↓／↓　↑　↓
　　・←・→・←・
　／

ソース

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

class Program
{
    const int UB = 4 - 1;

    struct JyoutaiDef
    {
        internal char CurrPos;
        internal Dictionary<char, char> BanDict;
    }

    static void Main()
    {
        //下記の文字が、マッチ棒の場所を表す
        // A B C
        //D E F G
        // H I J
        //K L M N
        // O P Q
        //R S T U
        // V W X

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrPos = 'A';
        WillPush.BanDict = new Dictionary<char, char>();
        Stk.Push(WillPush);

        var AnswerKouhoList = new List<Dictionary<char, char>>();
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.CurrPos > 'X') {
                AnswerKouhoList.Add(Popped.BanDict);
                continue;
            }

            char[] KouhoArrowArr = DeriveKouhoArrowArr(Popped.CurrPos);
            foreach (char EachKouhoArrow in KouhoArrowArr) {
                WillPush.BanDict = new Dictionary<char, char>(Popped.BanDict);
                WillPush.BanDict[Popped.CurrPos] = EachKouhoArrow;
                WillPush.CurrPos = Popped.CurrPos;
                if (WillEdakiri(WillPush)) continue;

                WillPush.CurrPos++;
                Stk.Push(WillPush);
            }
        }

        //回転解の除外
        var AnswerHashSet = new HashSet<uint>();
        foreach (Dictionary<char, char> EachAnswerKouho in AnswerKouhoList) {
            var wkHashSet = new HashSet<uint>();

            //8通りの盤面のHash値を求める
            wkHashSet.Add(GetHash(EachAnswerKouho));

            //90度回転
            Dictionary<char, char> wkDict = Kaiten90do(EachAnswerKouho);
            wkHashSet.Add(GetHash(wkDict));

            //180度回転
            wkDict = Kaiten90do(wkDict);
            wkHashSet.Add(GetHash(wkDict));

            //270度回転
            wkDict = Kaiten90do(wkDict);
            wkHashSet.Add(GetHash(wkDict));

            //左右反転
            wkDict = SayuuHanten(EachAnswerKouho);
            wkHashSet.Add(GetHash(wkDict));

            //左右反転の90度回転
            wkDict = Kaiten90do(wkDict);
            wkHashSet.Add(GetHash(wkDict));

            //左右反転の180度回転
            wkDict = Kaiten90do(wkDict);
            wkHashSet.Add(GetHash(wkDict));

            //左右反転の270度回転
            wkDict = Kaiten90do(wkDict);
            wkHashSet.Add(GetHash(wkDict));

            if (AnswerHashSet.Overlaps(wkHashSet) == false) {
                AnswerHashSet.Add(wkHashSet.First());
                Console.WriteLine("解{0}を発見", AnswerHashSet.Count);
                PrintBan(EachAnswerKouho);
            }
        }
    }

    //マッチ棒の場所ごとの矢印の候補を返す
    static char[] DeriveKouhoArrowArr(char pChar)
    {
        if ("ABCHIJOPQVWX".Contains(pChar)) return new char[] { '←', '→' };
        return new char[] { '↑', '↓' };
    }

    //枝切り判定
    static bool WillEdakiri(JyoutaiDef pJyoutai)
    {
        //回転解の排除で、一番上の辺で、右の数 > 左の数 なら枝切り
        if (pJyoutai.CurrPos == 'C') {
            var tmp = pJyoutai.BanDict.Values;
            if (tmp.Count(X => X == '→') > tmp.Count(X => X == '←'))
                return true;
        }

        if (pJyoutai.CurrPos < 'N') return false;

        int[,] HeadCntArr = DeriveHeadCntArr(pJyoutai.BanDict);
        //横計のチェック
        int YokoSum0 = 0, YokoSum1 = 0, YokoSum2 = 0, YokoSum3 = 0;
        for (int X = 0; X <= UB; X++) {
            YokoSum0 += HeadCntArr[X, 0];
            YokoSum1 += HeadCntArr[X, 1];
            YokoSum2 += HeadCntArr[X, 2];
            YokoSum3 += HeadCntArr[X, 3];
        }
        if (pJyoutai.CurrPos >= 'N' && YokoSum0 != YokoSum1) return true;
        if (pJyoutai.CurrPos >= 'U' && YokoSum0 != YokoSum2) return true;
        if (pJyoutai.CurrPos >= 'X' && YokoSum0 != YokoSum3) return true;

        //縦計のチェック
        int TateSum0 = 0, TateSum1 = 0, TateSum2 = 0, TateSum3 = 0;
        for (int Y = 0; Y <= UB; Y++) {
            TateSum0 += HeadCntArr[0, Y];
            TateSum1 += HeadCntArr[1, Y];
            TateSum2 += HeadCntArr[2, Y];
            TateSum3 += HeadCntArr[3, Y];
        }
        if (pJyoutai.CurrPos >= 'V' && YokoSum0 != TateSum0) return true;
        if (pJyoutai.CurrPos >= 'W' && YokoSum0 != TateSum1) return true;
        if (pJyoutai.CurrPos >= 'X' && YokoSum0 != TateSum2) return true;
        if (pJyoutai.CurrPos >= 'X' && YokoSum0 != TateSum3) return true;

        //斜めのチェック
        int NanameSum0 = 0, NanameSum1 = 0;
        for (int I = 0; I <= UB; I++) {
            NanameSum0 += HeadCntArr[I, I];
            NanameSum1 += HeadCntArr[I, UB - I];
        }
        if (pJyoutai.CurrPos >= 'X' && YokoSum0 != NanameSum0) return true;
        if (pJyoutai.CurrPos >= 'V' && YokoSum0 != NanameSum1) return true;

        return false;
    }

    //頭の数を設定した2次元配列を作成
    static int[,] DeriveHeadCntArr(Dictionary<char, char> pBanDict)
    {
        int[,] WillReturn = new int[UB + 1, UB + 1];

        Action<char, char, int, int> wkAct = (pKey, pValue, pX, pY) =>
        {
            if (pBanDict.ContainsKey(pKey))
                if (pBanDict[pKey] == pValue) WillReturn[pX, pY]++;
        };

        wkAct('A', '←', 0, 0); wkAct('A', '→', 1, 0);
        wkAct('B', '←', 1, 0); wkAct('B', '→', 2, 0);
        wkAct('C', '←', 2, 0); wkAct('C', '→', 3, 0);

        wkAct('D', '↑', 0, 0); wkAct('D', '↓', 0, 1);
        wkAct('E', '↑', 1, 0); wkAct('E', '↓', 1, 1);
        wkAct('F', '↑', 2, 0); wkAct('F', '↓', 2, 1);
        wkAct('G', '↑', 3, 0); wkAct('G', '↓', 3, 1);

        wkAct('H', '←', 0, 1); wkAct('H', '→', 1, 1);
        wkAct('I', '←', 1, 1); wkAct('I', '→', 2, 1);
        wkAct('J', '←', 2, 1); wkAct('J', '→', 3, 1);

        wkAct('K', '↑', 0, 1); wkAct('K', '↓', 0, 2);
        wkAct('L', '↑', 1, 1); wkAct('L', '↓', 1, 2);
        wkAct('M', '↑', 2, 1); wkAct('M', '↓', 2, 2);
        wkAct('N', '↑', 3, 1); wkAct('N', '↓', 3, 2);

        wkAct('O', '←', 0, 2); wkAct('O', '→', 1, 2);
        wkAct('P', '←', 1, 2); wkAct('P', '→', 2, 2);
        wkAct('Q', '←', 2, 2); wkAct('Q', '→', 3, 2);

        wkAct('R', '↑', 0, 2); wkAct('R', '↓', 0, 3);
        wkAct('S', '↑', 1, 2); wkAct('S', '↓', 1, 3);
        wkAct('T', '↑', 2, 2); wkAct('T', '↓', 2, 3);
        wkAct('U', '↑', 3, 2); wkAct('U', '↓', 3, 3);

        wkAct('V', '←', 0, 3); wkAct('V', '→', 1, 3);
        wkAct('W', '←', 1, 3); wkAct('W', '→', 2, 3);
        wkAct('X', '←', 2, 3); wkAct('X', '→', 3, 3);

        return WillReturn;
    }

    //右に90度回転させた盤面を返す
    static Dictionary<char, char> Kaiten90do(Dictionary<char, char> pBanDict)
    {
        //90度回転した矢印を返す
        Func<char, char> wkFunc = pChar =>
        {
            if (pChar == '↑') return '→';
            if (pChar == '→') return '↓';
            if (pChar == '↓') return '←';
            if (pChar == '←') return '↑';
            return pChar;
        };

        var wkP = new Dictionary<char, char>();
        wkP['A'] = wkFunc(pBanDict['R']);
        wkP['B'] = wkFunc(pBanDict['K']);
        wkP['C'] = wkFunc(pBanDict['D']);

        wkP['D'] = wkFunc(pBanDict['V']);
        wkP['E'] = wkFunc(pBanDict['O']);
        wkP['F'] = wkFunc(pBanDict['H']);
        wkP['G'] = wkFunc(pBanDict['A']);

        wkP['H'] = wkFunc(pBanDict['S']);
        wkP['I'] = wkFunc(pBanDict['L']);
        wkP['J'] = wkFunc(pBanDict['E']);

        wkP['K'] = wkFunc(pBanDict['W']);
        wkP['L'] = wkFunc(pBanDict['P']);
        wkP['M'] = wkFunc(pBanDict['I']);
        wkP['N'] = wkFunc(pBanDict['B']);

        wkP['O'] = wkFunc(pBanDict['T']);
        wkP['P'] = wkFunc(pBanDict['M']);
        wkP['Q'] = wkFunc(pBanDict['F']);

        wkP['R'] = wkFunc(pBanDict['X']);
        wkP['S'] = wkFunc(pBanDict['Q']);
        wkP['T'] = wkFunc(pBanDict['J']);
        wkP['U'] = wkFunc(pBanDict['C']);

        wkP['V'] = wkFunc(pBanDict['U']);
        wkP['W'] = wkFunc(pBanDict['N']);
        wkP['X'] = wkFunc(pBanDict['G']);

        return wkP;
    }

    //左右反転させた盤面を返す
    static Dictionary<char, char> SayuuHanten(Dictionary<char, char> pBanDict)
    {
        //左右反転させた矢印を返す
        Func<char, char> RevFunc = pChar =>
        {
            if (pChar == '←') return '→';
            if (pChar == '→') return '←';
            return pChar;
        };

        var wkP = new Dictionary<char, char>();
        wkP['A'] = RevFunc(pBanDict['C']);
        wkP['B'] = RevFunc(pBanDict['B']);
        wkP['C'] = RevFunc(pBanDict['A']);
        
        wkP['D'] = RevFunc(pBanDict['G']);
        wkP['E'] = RevFunc(pBanDict['F']);
        wkP['F'] = RevFunc(pBanDict['E']);
        wkP['G'] = RevFunc(pBanDict['D']);

        wkP['H'] = RevFunc(pBanDict['J']);
        wkP['I'] = RevFunc(pBanDict['I']);
        wkP['J'] = RevFunc(pBanDict['H']);

        wkP['K'] = RevFunc(pBanDict['N']);
        wkP['L'] = RevFunc(pBanDict['M']);
        wkP['M'] = RevFunc(pBanDict['L']);
        wkP['N'] = RevFunc(pBanDict['K']);

        wkP['O'] = RevFunc(pBanDict['Q']);
        wkP['P'] = RevFunc(pBanDict['P']);
        wkP['Q'] = RevFunc(pBanDict['O']);

        wkP['R'] = RevFunc(pBanDict['U']);
        wkP['S'] = RevFunc(pBanDict['T']);
        wkP['T'] = RevFunc(pBanDict['S']);
        wkP['U'] = RevFunc(pBanDict['R']);

        wkP['V'] = RevFunc(pBanDict['X']);
        wkP['W'] = RevFunc(pBanDict['W']);
        wkP['X'] = RevFunc(pBanDict['V']);
        return wkP;
    }

    //盤面をハッシュ値に変換
    static uint GetHash(Dictionary<char, char> pBanDict)
    {
        var sb = new System.Text.StringBuilder();
        for (char I = 'A'; I <= 'X'; I++) {
            char CurrChar = pBanDict[I];
            if (CurrChar == '←') sb.Append(0);
            if (CurrChar == '→') sb.Append(1);

            if (CurrChar == '↑') sb.Append(0);
            if (CurrChar == '↓') sb.Append(1);
        }
        return Convert.ToUInt32(sb.ToString(), 2);
    }

    //盤面を出力
    static void PrintBan(Dictionary<char, char> pBanDict)
    {
        var sb = new System.Text.StringBuilder();

        Dictionary<char, char> wkP = pBanDict;
        sb.AppendFormat("・{0}・{1}・{2}・", wkP['A'], wkP['B'], wkP['C']);
        sb.AppendLine();
        sb.AppendFormat("{0}　{1}　{2}　{3}", wkP['D'], wkP['E'], wkP['F'], wkP['G']);
        sb.AppendLine();
        sb.AppendFormat("・{0}・{1}・{2}・", wkP['H'], wkP['I'], wkP['J']);
        sb.AppendLine();
        sb.AppendFormat("{0}　{1}　{2}　{3}", wkP['K'], wkP['L'], wkP['M'], wkP['N']);
        sb.AppendLine();
        sb.AppendFormat("・{0}・{1}・{2}・", wkP['O'], wkP['P'], wkP['Q']);
        sb.AppendLine();
        sb.AppendFormat("{0}　{1}　{2}　{3}", wkP['R'], wkP['S'], wkP['T'], wkP['U']);
        sb.AppendLine();
        sb.AppendFormat("・{0}・{1}・{2}・", wkP['V'], wkP['W'], wkP['X']);
        sb.AppendLine();

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

実行結果

省略
解117を発見
・←・←・→・
↑　↑　↑　↓
・←・→・←・
↑　↑　↓　↓
・←・←・→・
↓　↑　↓　↓
・→・→・→・

解118を発見
・←・←・→・
↑　↑　↑　↓
・←・←・←・
↑　↓　↑　↓
・→・→・→・
↑　↓　↓　↓
・←・→・→・

解説

回転させた盤面のHash値を使って、distinctして回転解を除外してます。