Cマガ電脳クラブ(第092回) 変形魔方陣

問題

Fig.1のように、1〜9の九つの数字を3×3のマスに入れて、魔方陣を作る。

ただし、「縦、横、斜めに並んだ3数の合計がどれも同じになる」という一般的な魔方陣とは違い、
「4か所ある2×2のマスに含まれる4数の合計が、どれも同じになる」というもので、
これを変形魔方陣と呼ぶことにする。

Fig.2のように、例では合計がどれも16 (これを定和という) になっている。

ではここで問題。回転・裏返しを除き、本質的「変形魔方陣」は何種類あるだろうか。
定和が16だけでないことに注意。

     

ソース

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

class Program
{
    const int UB = 3 - 1;

    struct JyoutaiDef
    {
        internal int[,] BanArr;
        internal int CurrX;
        internal int CurrY;
        internal int Teiwa;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new int[UB + 1, UB + 1];
        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.Teiwa = -1;
        stk.Push(WillPush);

        var AnswerList = new List<JyoutaiDef>();
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //X座標の繰上げ処理
            if (Popped.CurrX > UB) {
                Popped.CurrX = 0;
                Popped.CurrY++;
            }

            //最終行を超えた場合
            if (Popped.CurrY > UB) {
                AnswerList.Add(Popped);
                continue;
            }

            int[] UsedNumArr = Popped.BanArr.Cast<int>().Where(X => X > 0).ToArray();

            for (int I = 1; I <= 9; I++) {
                //使用済の数値は不可
                if (UsedNumArr.Contains(I)) continue;

                //対称解の除外で[0,0] < [0,2]とする
                if (Popped.CurrX == 2 && Popped.CurrY == 0) {
                    if (Popped.BanArr[0, 0] > I) continue;
                }

                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.BanArr = (int[,])Popped.BanArr.Clone();
                WillPush.BanArr[Popped.CurrX, Popped.CurrY] = I;

                //定和を設定
                if (Popped.CurrX == 1 && Popped.CurrY == 1) {
                    WillPush.Teiwa =
                        WillPush.BanArr[0, 0] + WillPush.BanArr[1, 0]
                      + WillPush.BanArr[0, 1] + WillPush.BanArr[1, 1];
                }
                else WillPush.Teiwa = Popped.Teiwa;

                //枝切り判定
                if (WillEdakiri(Popped.CurrX, Popped.CurrY, WillPush.BanArr, WillPush.Teiwa))
                    continue;
                stk.Push(WillPush);
            }
        }
        RemoveKaitenKai(AnswerList);
        AnswerList.Sort((A, B) => A.Teiwa.CompareTo(B.Teiwa));
        for (int I = 0; I <= AnswerList.Count - 1; I++) {
            Console.WriteLine("解{0}。定和={1}", I + 1, AnswerList[I].Teiwa);
            PrintAnswer(AnswerList[I].BanArr);
        }
    }

    //枝切り判定
    static bool WillEdakiri(int pCurrX, int pCurrY, int[,] pBanArr, int pTeiwa)
    {
        int[,] wkP = pBanArr;
        if (pCurrX == 2 && pCurrY == 1) {
            if (wkP[1, 0] + wkP[1, 1] + wkP[2, 0] + wkP[2, 1] != pTeiwa)
                return true;
        }
        if (pCurrX == 1 && pCurrY == 2) {
            if (wkP[0, 1] + wkP[0, 2] + wkP[1, 1] + wkP[1, 2] != pTeiwa)
                return true;
        }
        if (pCurrX == 2 && pCurrY == 2) {
            if (wkP[1, 1] + wkP[1, 2] + wkP[2, 1] + wkP[2, 2] != pTeiwa)
                return true;
        }
        return false;
    }

    //回転した解を除外
    static void RemoveKaitenKai(List<JyoutaiDef> pAnswerList)
    {
        Predicate<int> IsExist = (pCurrInd) =>
        {
            for (int I = 0; I <= pCurrInd - 1; I++) {
                bool IsOK1 = false, IsOK2 = false, IsOK3 = false, IsOK4 = false;
                bool IsOK5 = false, IsOK6 = false, IsOK7 = false; //回転1から7

                for (int X = 0; X <= UB; X++) {
                    for (int Y = 0; Y <= UB; Y++) {
                        int CurrVal = pAnswerList[pCurrInd].BanArr[X, Y];
                        if (pAnswerList[I].BanArr[UB - X, Y] != CurrVal) IsOK1 = true;
                        if (pAnswerList[I].BanArr[UB - X, UB - Y] != CurrVal) IsOK2 = true;
                        if (pAnswerList[I].BanArr[X, UB - Y] != CurrVal) IsOK3 = true;
                        if (pAnswerList[I].BanArr[Y, X] != CurrVal) IsOK4 = true;
                        if (pAnswerList[I].BanArr[UB - Y, X] != CurrVal) IsOK5 = true;
                        if (pAnswerList[I].BanArr[UB - Y, UB - X] != CurrVal) IsOK6 = true;
                        if (pAnswerList[I].BanArr[Y, UB - X] != CurrVal) IsOK7 = true;
                    }
                }
                if (IsOK1 == false || IsOK2 == false || IsOK3 == false || IsOK4 == false
                 || IsOK5 == false || IsOK6 == false || IsOK7 == false)
                    return true;
            }
            return false;
        };

        for (int I = pAnswerList.Count - 1; I >= 0; I--) {
            if (IsExist(I)) pAnswerList.RemoveAt(I);
        }
    }

    //解を出力
    static void PrintAnswer(int[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

省略
解45。定和=23
637
594
182

解46。定和=24
435
897
162

解47。定和=24
374
685
192

解説

深さ優先探索でナイーブに解いてます。