Cマガ電脳クラブ(第087回) 正12面体魔方陣

問題

Fig.1は正12面体である。正5角形の面が12枚あり、3枚ずつ面が集まってできている頂点が20か所ある。
この各頂点にすべて違う正の整数を1個ずつ置く。

このとき、各面の5個の頂点に5個の数が置かれていることになるが、
その面ごとの5数の合計がどこも同じになるようにする (この数を方陣の世界では定和という)。
それが今回の問題、正12面体魔方陣である。

実は、1〜20を各1個使って完成するのは不可能である。
それは全検などしないで、簡単な論理で証明ができる。
では置くべき20個の数をうまく選んで、定和を最小にする答えの例を見つけてほしい。

Fig.1 正12面体

ソース

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

class Program
{
    const int TeiwaKagen = 20;
    const int TeiwaJyougen = 60;

    static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

    static void Main()
    {
        //定和でループ
        for (int Teiwa = TeiwaKagen; Teiwa <= TeiwaJyougen; Teiwa++) {
            //定和を引数として、20個の数の候補を列挙
            List<int[]> KouhoArrList = DeriveKouhoArrList(Teiwa);

            Console.WriteLine("定和={0}での20個の数の候補は、{1}通り", Teiwa, KouhoArrList.Count);

            bool FoundAnswer = false;
            foreach (int[] EachIntArr in KouhoArrList) {
                FoundAnswer = FindAnswer(Teiwa, EachIntArr);
                if (FoundAnswer) break;
            }
            if (FoundAnswer) break;
        }
    }

    struct JyoutaiDef1
    {
        internal int CurrNum;
        internal int SumNum;
        internal List<int> NumList;
    }

    //定和を引数として、20個の数の候補を列挙
    static List<int[]> DeriveKouhoArrList(int pTeiwa)
    {
        var WillReturnList = new List<int[]>();

        var stk = new Stack<JyoutaiDef1>();
        JyoutaiDef1 WillPush;
        for (int I = 1; I <= pTeiwa; I++) {
            WillPush.CurrNum = WillPush.SumNum = I;
            WillPush.NumList = new List<int>() { I };
            stk.Push(WillPush);
        }

        while (stk.Count > 0) {
            JyoutaiDef1 Popped = stk.Pop();

            //クリア判定
            if (Popped.NumList.Count == 20) {
                //A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S+T != 定和の4倍でない場合
                if (Popped.SumNum != pTeiwa * 4) continue;
                WillReturnList.Add(Popped.NumList.ToArray());

                continue;
            }

            for (int I = Popped.CurrNum + 1; I <= pTeiwa; I++) {
                int RestCnt = 20 - Popped.NumList.Count;

                //定和の4倍を超えるなら枝切り
                if (Popped.SumNum + RestCnt * I > pTeiwa * 4) break;

                WillPush.CurrNum = I;
                WillPush.SumNum = Popped.SumNum + I;
                WillPush.NumList = new List<int>(Popped.NumList) { I };
                stk.Push(WillPush);
            }
        }
        return WillReturnList;
    }

    struct JyoutaiDef2
    {
        internal Dictionary<char, int> NumDict;
    }

    //20個の数の候補を引数として、解が存在するかを返す
    static bool FindAnswer(int pTeiwa, int[] pKouhoArr)
    {
        var stk = new Stack<JyoutaiDef2>();
        JyoutaiDef2 WillPush;
        WillPush.NumDict = new Dictionary<char, int>();
        //対称解の除外で、Aは20個の数の中の最小値とする
        WillPush.NumDict.Add('A', pKouhoArr.Min());
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef2 Popped = stk.Pop();

            //クリア判定
            if (Popped.NumDict.Count == 20) {
                Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
                foreach (var EachPair in Popped.NumDict.OrderBy(X => X.Key)) {
                    Console.WriteLine("{0}={1}", EachPair.Key, EachPair.Value);
                }
                return true;
            }

            foreach (int EachInt in pKouhoArr) {
                //数値の再使用は不可
                if (Popped.NumDict.ContainsValue(EachInt)) continue;

                char CurrChar = (char)(Popped.NumDict.Keys.Max() + 1);

                //対称解の除外で、B<Cとする
                if (CurrChar == 'C' && Popped.NumDict['B'] > EachInt) continue;

                WillPush.NumDict = new Dictionary<char, int>(Popped.NumDict);
                WillPush.NumDict.Add(CurrChar, EachInt);

                //枝切りの判定
                if (WillEdakiri(pTeiwa, WillPush.NumDict) == false)
                    stk.Push(WillPush);
            }
        }

        return false;
    }

    //枝切りの判定
    static bool WillEdakiri(int pTeiwa, Dictionary<char, int> pNumDict)
    {
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'A', 'B', 'C', 'E', 'F')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'E', 'F', 'K', 'Q', 'L')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'C', 'F', 'G', 'L', 'M')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'L', 'M', 'Q', 'T', 'R')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'A', 'C', 'D', 'G', 'H')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'G', 'H', 'M', 'R', 'N')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'H', 'D', 'I', 'N', 'O')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'N', 'O', 'R', 'T', 'S')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'A', 'D', 'B', 'I', 'J')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'I', 'J', 'O', 'S', 'P')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'B', 'J', 'E', 'P', 'K')) return true;
        if (WillEdakiriHelper(pTeiwa, pNumDict, 'P', 'K', 'S', 'Q', 'T')) return true;
        return false;
    }

    //枝切りの判定のヘルパメソッド
    static bool WillEdakiriHelper(int pTeiwa, Dictionary<char, int> pNumDict,
        char p1, char p2, char p3, char p4, char p5)
    {
        int Cnt = 0;
        int SumVal = 0;

        if (pNumDict.ContainsKey(p1)) { SumVal += pNumDict[p1]; Cnt++; }
        if (pNumDict.ContainsKey(p2)) { SumVal += pNumDict[p2]; Cnt++; }
        if (pNumDict.ContainsKey(p3)) { SumVal += pNumDict[p3]; Cnt++; }
        if (pNumDict.ContainsKey(p4)) { SumVal += pNumDict[p4]; Cnt++; }
        if (pNumDict.ContainsKey(p5)) { SumVal += pNumDict[p5]; Cnt++; }

        if (Cnt == 5)
            return SumVal != pTeiwa;
        return SumVal >= pTeiwa;
    }
}

実行結果

省略
定和=50での20個の数の候補は、0通り
定和=51での20個の数の候補は、0通り
定和=52での20個の数の候補は、0通り
定和=53での20個の数の候補は、2通り
解を発見。経過時間=00:05:18.9766710
A=1
B=17
C=21
D=12
E=3
F=11
G=4
H=15
I=5
J=18
K=9
L=10
M=7
N=13
O=8
P=6
Q=20
R=14
S=16
T=2

解説

正12面体の展開図の各頂点に、アルファベットのAからTを割り当てると、下記となります。



定和をSとすると、
 3*(A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S+T) = 12S
で、両辺を3で割った、
A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S+T = 4S
を20個の数の候補の、必要条件としてます。

Cマガ電脳クラブ(第074回) ノナ