Cマガ電脳クラブ(第136回) 小町の輪

問題

Fig.1のように、5つ描かれた円に、1から9までの数字を1字ずつ書き入れる。
よく見ると、どの円の中も合計が13になっている。

このように、1から9までの数字を1字ずつ書き入れて、
5つある円の中の数字の合計がすべて同じになるものをほかにも見つけていただきたい。

例を含めて何通りあるだろうか。ただし、全体をそっくり裏返したものは別の解とはしない。

Fig.1 小町の輪

ソース

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

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

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrPos = 'A';
        WillPush.BanDict = new Dictionary<char, int>();
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.CurrPos > 'I') {
                Console.WriteLine("解{0}を発見", ++AnswerCnt);
                string[] wkArr = Popped.BanDict.Values.Select(X => X.ToString()).ToArray();
                Console.WriteLine(string.Join(",", wkArr));
                continue;
            }

            for (int I = 1; I <= 9; I++) {
                if (Popped.BanDict.ContainsValue(I)) continue;

                WillPush.BanDict = new Dictionary<char, int>(Popped.BanDict);
                WillPush.BanDict[Popped.CurrPos] = I;
                if (WillEdakiri(WillPush.BanDict)) continue;

                WillPush.CurrPos = (char)(Popped.CurrPos + 1);
                stk.Push(WillPush);
            }
        }
    }

    //枝切り判定
    static bool WillEdakiri(Dictionary<char, int> pBanDict)
    {
        //対称解の排除で、1はEまでに使用する
        if (pBanDict.ContainsKey('E')) {
            if (pBanDict.ContainsValue(1) == false)
                return true;
        }

        Func<string, int> DeriveSumFunc = pStr =>
            pStr.Sum(X => pBanDict[X]);

        if (pBanDict.ContainsKey('B')) {
            int wkSum = DeriveSumFunc("AB");
            if (pBanDict.ContainsKey('D')) {
                if (wkSum != DeriveSumFunc("BCD")) return true;
            }
            if (pBanDict.ContainsKey('F')) {
                if (wkSum != DeriveSumFunc("DEF")) return true;
            }
            if (pBanDict.ContainsKey('H')) {
                if (wkSum != DeriveSumFunc("FGH")) return true;
            }
            if (pBanDict.ContainsKey('I')) {
                if (wkSum != DeriveSumFunc("HI")) return true;
            }
        }
        return false;
    }
}

実行結果

解1を発見
9,4,1,8,3,2,5,6,7
解2を発見
8,6,1,7,4,3,2,9,5
解3を発見
8,3,7,1,6,4,5,2,9
解4を発見
4,9,1,3,8,2,5,6,7

解説

深さ優先探索で、小まめに枝切りしてます。