Problem166 十字

問題

0 <= d <= 9 な d で埋められた 4x4 の格子がある.
以下の格子では, それぞれの行, 列の和が12となる. さらに, 斜めの和も12となる.

6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5

0 <= d <= 9 な d で 4x4 の格子を,
それぞれの行, 列, 斜めの和が同じとなるように埋める方法は何通りあるか?

ソース

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

class Program
{
    const int UB = 3;

    struct KouhoInfoDef
    {
        internal int A;
        internal int B;
        internal int C;
        internal int D;
        internal int SumVal;
    }

    static KouhoInfoDef[] mKouhoArr;
    static Dictionary<int, int> mStaIndDict = new Dictionary<int, int>();

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

        DeriveKouhoArr();

        int UB = mKouhoArr.GetUpperBound(0);

        int AnswerCnt = 0;
        foreach (KouhoInfoDef Each1 in mKouhoArr) {
            foreach (KouhoInfoDef Each2 in mKouhoArr) {
                int Teiwa = Each1.A + Each1.B + Each2.A + Each2.B;
                //Y=1の行の横計
                if (Each1.C + Each1.D + Each2.C + Each2.D != Teiwa)
                    continue;

                //対称解の除外
                if (Each1.A > Each2.B) continue;
                if (Each1.B > Each2.A) continue;

                int NeedSum3 = 2 * Teiwa - Each1.SumVal;
                for (int I = mStaIndDict[NeedSum3]; I <= UB; I++) {
                    KouhoInfoDef Each3 = mKouhoArr[I];
                    if (Each3.SumVal > NeedSum3) break;

                    //X=0の列の縦計
                    if (Each1.A + Each1.C + Each3.A + Each3.C != Teiwa)
                        continue;
                    //X=1の列の縦計
                    if (Each1.B + Each1.D + Each3.B + Each3.D != Teiwa)
                        continue;
                    //斜め計
                    if (Each2.B + Each2.C + Each3.B + Each3.C != Teiwa)
                        continue;

                    int NeedSum4 = 2 * Teiwa - Each3.SumVal;
                    for (int J = mStaIndDict[NeedSum4]; J <= UB; J++) {
                        KouhoInfoDef Each4 = mKouhoArr[J];
                        if (Each4.SumVal > NeedSum4) break;

                        //Y=2の行の横計
                        if (Each3.A + Each3.B + Each4.A + Each4.B != Teiwa)
                            continue;
                        //Y=3の行の横計
                        if (Each3.C + Each3.D + Each4.C + Each4.D != Teiwa)
                            continue;
                        //X=2の列の縦計
                        if (Each2.A + Each2.C + Each4.A + Each4.C != Teiwa)
                            continue;
                        //X=3の列の縦計
                        if (Each2.B + Each2.D + Each4.B + Each4.D != Teiwa)
                            continue;
                        //斜め計
                        if (Each1.A + Each1.D + Each4.A + Each4.D != Teiwa)
                            continue;

                        //除外した対称解の分を計上
                        int AnswerPattern = 1;
                        if (Each1.A < Each2.B) AnswerPattern *= 2;
                        if (Each1.B < Each2.A) AnswerPattern *= 2;
                        AnswerCnt += AnswerPattern;
                    }
                }
            }
        }
        Console.WriteLine("解は{0}通り。経過時間={1}", AnswerCnt, sw.Elapsed);
    }

    static void DeriveKouhoArr()
    {
        var KouhoList = new List<KouhoInfoDef>();

        for (int A = 0; A <= 9; A++) {
            for (int B = 0; B <= 9; B++) {
                for (int C = 0; C <= 9; C++) {
                    for (int D = 0; D <= 9; D++) {
                        KouhoInfoDef WillAdd;
                        WillAdd.A = A;
                        WillAdd.B = B;
                        WillAdd.C = C;
                        WillAdd.D = D;
                        WillAdd.SumVal = A + B + C + D;
                        KouhoList.Add(WillAdd);
                    }
                }
            }
        }
        //合計値でソートしておく
        mKouhoArr = KouhoList.OrderBy(X => X.SumVal).ToArray();

        //合計値ごとの開始の添字を求めておく
        for (int I = 0; I <= mKouhoArr.GetUpperBound(0); I++) {
            if (mStaIndDict.ContainsKey(mKouhoArr[I].SumVal) == false) {
                mStaIndDict.Add(mKouhoArr[I].SumVal, I);
            }
        }
    }
}

実行結果

解は7130034通り。経過時間=00:00:18.3673578

解説

左上4マス + 左下4マス = 2*定和
と
左下4マス + 右下4マス = 2*定和
が成立することを使ってます。