Cマガ電脳クラブ(第034回) 16スター

問題

Fig.1のように、8本の直線で作られた星形の図形があり、直線の交点上の16ヶ所に円が置かれている。
図では円のひとつに数字の1が置かれているが、同様に2〜16の数字をほかの円の上に配置してほしい。
ただし、ひとつの直線上にある4個の円の数字の合計が8本の直線すべてにおいて同じになるように、である。

なお、数字の1はFig.1の位置に固定しておくこととする。
上の条件を満たす解は何通りあるだろうか。いつものように、回転・裏返しによる解は別の解とはしない。

Fig.1

ソース

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

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

        var stk = new Stack<Dictionary<char, int>>();
        stk.Push(new Dictionary<char, int>());

        int AnswerCnt = 0;

        while (stk.Count > 0) {
            Dictionary<char, int> PoppedDict = stk.Pop();

            if (PoppedDict.Count == 15) {
                Console.WriteLine("{0}個目の解を発見。経過時間={1}", ++AnswerCnt, sw.Elapsed);
                PrintBan(PoppedDict);
                continue;
            }

            for (char AddChar = 'A'; AddChar <= 'O'; AddChar++) {
                if (PoppedDict.ContainsKey(AddChar)) continue;

                for (int I = 2; I <= 16; I++) {
                    if (PoppedDict.ContainsValue(I)) continue;

                    //回転解の除外で C < J とする
                    if (AddChar == 'J' && PoppedDict['C'] > I)
                        continue;

                    Dictionary<char, int> WillPushDict = new Dictionary<char, int>(PoppedDict);
                    WillPushDict[AddChar] = I;

                    if (IsEdakiri(WillPushDict)) continue;

                    stk.Push(WillPushDict);
                }
                break;
            }
        }
    }

    //枝切り判定
    static bool IsEdakiri(Dictionary<char, int> pHaitiDict)
    {
        Func<char, char, char, int> DeriveSumFrom3 = (pStr1, pStr2, pStr3) => (
            pHaitiDict[pStr1] + pHaitiDict[pStr2] + pHaitiDict[pStr3]);
        Func<char, char, char, char, int> DeriveSumFrom4 = (pStr1, pStr2, pStr3, pStr4) => (
            pHaitiDict[pStr1] + pHaitiDict[pStr2] + pHaitiDict[pStr3] + pHaitiDict[pStr4]);

        char MaxStr = pHaitiDict.Keys.Max();

        //各値は2回ずつ加算されるので、8本の直線の和の総合計は、1から16までの等差数列の和の2倍である。
        //8本の直線の和は、それぞれ等しいので、8で割れば、各直線の和が求まる。
        const int SumVal = 16 * (16 + 1) / 2 * 2 / 8;

        //途中の合計で枝切り
        if (MaxStr == 'C' && DeriveSumFrom3('A', 'B', 'C') > SumVal - 2) return true;
        if (MaxStr == 'G' && DeriveSumFrom3('E', 'F', 'G') > SumVal - 2) return true;
        if (MaxStr == 'I' && DeriveSumFrom3('B', 'F', 'I') > SumVal - 2) return true;
        if (MaxStr == 'J' && DeriveSumFrom3('I', 'J', 'H') > SumVal - 2) return true;

        //直線の合計で枝切り
        if (MaxStr == 'D' && SumVal != DeriveSumFrom4('A', 'B', 'C', 'D')) return true;
        if (MaxStr == 'H' && SumVal != DeriveSumFrom4('E', 'F', 'G', 'H')) return true;
        if (MaxStr == 'K' && SumVal != 1 + DeriveSumFrom3('J', 'K', 'E')) return true;
        if (MaxStr == 'L' && SumVal != DeriveSumFrom4('I', 'J', 'L', 'H')) return true;
        if (MaxStr == 'N' && SumVal != DeriveSumFrom4('I', 'B', 'F', 'N')) return true;
        if (MaxStr == 'N' && SumVal != DeriveSumFrom4('D', 'L', 'M', 'N')) return true;
        if (MaxStr == 'O' && SumVal != 1 + DeriveSumFrom3('C', 'G', 'O')) return true;
        if (MaxStr == 'O' && SumVal != DeriveSumFrom4('A', 'K', 'M', 'O')) return true;
        return false;
    }

    //盤面を表示
    static void PrintBan(Dictionary<char, int> pHaitiDict)
    {
        var sb = new System.Text.StringBuilder();
        const string SP = "  ";
        sb.AppendFormat("{0}{0}{1,2}{0}{2,2}{0}{0}", SP, pHaitiDict['I'], 1);
        sb.AppendLine();
        sb.AppendFormat("{0}{0}{0}{1,2}{0}{0}{0}", SP, pHaitiDict['J']);
        sb.AppendLine();
        sb.AppendFormat("{1,2}{0}{2,2}{0}{3,2}{0}{4,2}", SP,
            pHaitiDict['A'], pHaitiDict['B'], pHaitiDict['C'], pHaitiDict['D']);
        sb.AppendLine();
        sb.AppendFormat("{0}{1,2}{0}{0}{0}{2,2}{0}", SP, pHaitiDict['K'], pHaitiDict['L']);
        sb.AppendLine();
        sb.AppendFormat("{1,2}{0}{2,2}{0}{3,2}{0}{4,2}", SP,
            pHaitiDict['E'], pHaitiDict['F'], pHaitiDict['G'], pHaitiDict['H']);
        sb.AppendLine();
        sb.AppendFormat("{0}{0}{0}{1,2}{0}{0}{0}", SP, pHaitiDict['M']);
        sb.AppendLine();
        sb.AppendFormat("{0}{0}{1,2}{0}{2,2}{0}{0}", SP, pHaitiDict['N'], pHaitiDict['O']);
        sb.AppendLine();

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

実行結果

省略
62個目の解を発見。経過時間=00:05:40.4644875
    11   1
      15
 2   9  10  13
   4       3
14   8   7   5
      12
     6  16

63個目の解を発見。経過時間=00:05:45.1174154
    10   1
      16
 2   4  15  13
   9       3
 8  14   7   5
      12
     6  11

解説

下記を数字の配置として深さ優先探索で解いてます。

     I   1
       J
 A   B   C   D
   K       L
 E   F   G   H
       M
     O   P