トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Cマガ電脳クラブ(第105回) 平方小町式

問題

下の式は、左辺が平方数の和、右辺がひとつの平方数となっており、成立している。
 4*4 + 12*12 + 36*36 +87*87 = 95*95
さらによく見ると、この式に登場している平方数の根 (ここでいう4、12、36、87、95) を構成する数字は全部で9個、
しかも1〜9が1個ずつすべて使われている。

このように、「いくつかの平方数の和 (左辺) がひとつの平方数 (右辺) と等しく、
そこに登場する平方数の根は1〜9(0は使わない)の数字をダブりなく1個ずつすべて使っている」
という式を平方小町式と呼ぶことにする。この平方小町式をすべて見つけてほしい。

もちろん、左辺の各項を入れ換えたものは別の解とはしない。また、左辺が4項の和とは限らないことに注意。


ソース

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

class Program
{
    struct KouhoInfoDef
    {
        internal int Val;
        internal int[] NumArr;
    }

    struct JyoutaiDef
    {
        internal int CurrP;
        internal List<int> ValList;
        internal HashSet<int> UsedNumSet;
    }

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

        KouhoInfoDef[] KouhoInfoArr = CreateKouhoInfoArr();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrP = 0;
        WillPush.ValList = new List<int>();
        WillPush.UsedNumSet = new HashSet<int>();
        stk.Push(WillPush);

        var AnswerValArrList = new List<int[]>();
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.UsedNumSet.Count == 9) {
                int LeftVal = 0;
                for (int I = 0; I <= Popped.ValList.Count - 2; I++) {
                    LeftVal += Popped.ValList[I] * Popped.ValList[I];
                }
                int RightVal = Popped.ValList.Last() * Popped.ValList.Last();
                if (LeftVal == RightVal) {
                    AnswerValArrList.Add(Popped.ValList.ToArray());
                }
                continue;
            }

            for (int I = Popped.CurrP; I <= KouhoInfoArr.GetUpperBound(0); I++) {
                if (Popped.UsedNumSet.Count + DeriveKetasuu(KouhoInfoArr[I].Val) > 9) break;

                //最初に4桁以上は不適
                if (Popped.ValList.Count == 0 && DeriveKetasuu(KouhoInfoArr[I].Val) >= 4) break;

                //2番目に5桁以上は不適
                if (Popped.ValList.Count == 1 && DeriveKetasuu(KouhoInfoArr[I].Val) >= 5) break;

                //最初が3桁で次に4桁以上は不適
                if (Popped.ValList.Count == 1) {
                    if (DeriveKetasuu(Popped.ValList[0]) == 3
                     && DeriveKetasuu(KouhoInfoArr[I].Val) >= 4) break;
                }

                //左辺が2桁 + 3桁は不適
                if (Popped.ValList.Count == 1) {
                    if (DeriveKetasuu(Popped.ValList[0]) == 2
                     && DeriveKetasuu(KouhoInfoArr[I].Val) == 3)
                        break;
                }

                //3桁,3桁の場合
                if (Popped.ValList.Count == 1) {
                    if (DeriveKetasuu(Popped.ValList[0]) == 3
                     && DeriveKetasuu(KouhoInfoArr[I].Val) == 3) {
                        int wkSum = Popped.ValList[0] * Popped.ValList[0];
                        wkSum += KouhoInfoArr[I].Val * KouhoInfoArr[I].Val;
                        if (Array.Exists(KouhoInfoArr, A => A.Val == wkSum) == false)
                            continue;
                    }
                }

                //2桁,2桁,2桁の場合
                if (Popped.ValList.Count == 2) {
                    if (DeriveKetasuu(Popped.ValList[0]) == 2
                     && DeriveKetasuu(KouhoInfoArr[1].Val) == 2
                     && DeriveKetasuu(KouhoInfoArr[I].Val) == 2) {
                        int wkSum = Popped.ValList[0] * Popped.ValList[0];
                        wkSum += KouhoInfoArr[1].Val * KouhoInfoArr[1].Val;
                        wkSum += KouhoInfoArr[I].Val * KouhoInfoArr[I].Val;
                        if (Array.Exists(KouhoInfoArr, A => A.Val == wkSum) == false)
                            continue;
                    }
                }

                //1桁,4桁の場合
                if (Popped.ValList.Count == 1) {
                    if (DeriveKetasuu(Popped.ValList[0]) == 1
                     && DeriveKetasuu(KouhoInfoArr[I].Val) == 4) {
                        int wkSum = Popped.ValList[0] * Popped.ValList[0];
                        wkSum += KouhoInfoArr[I].Val * KouhoInfoArr[I].Val;
                        if (Array.Exists(KouhoInfoArr, A => A.Val == wkSum) == false)
                            continue;
                    }
                }

                //同じ数字は使用不可
                if (Popped.UsedNumSet.Overlaps(KouhoInfoArr[I].NumArr)) {
                    continue;
                }
                WillPush.CurrP = I + 1;
                WillPush.ValList = new List<int>(Popped.ValList) { KouhoInfoArr[I].Val };
                WillPush.UsedNumSet = new HashSet<int>(Popped.UsedNumSet);
                WillPush.UsedNumSet.UnionWith(KouhoInfoArr[I].NumArr);

                //桁数が広義の単調増加でなかったら枝切り
                int RestNumCnt = 9 - WillPush.UsedNumSet.Count;
                if (RestNumCnt > 0) {
                    if (RestNumCnt < DeriveKetasuu(WillPush.ValList.Last())) break;
                }
                stk.Push(WillPush);
            }
        }

        //辞書順でソート
        AnswerValArrList.Sort((A, B) =>
        {
            int UB_A = A.GetUpperBound(0);
            int UB_B = B.GetUpperBound(0);

            for (int I = 0; I <= Math.Min(UB_A, UB_B); I++) {
                if (A[I] < B[I]) return -1;
                if (A[I] > B[I]) return 1;
            }
            return UB_A.CompareTo(UB_B);
        });

        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= AnswerValArrList.Count - 1; I++) {
            sb.AppendFormat("解{0} ", I + 1);
            int UB = AnswerValArrList[I].GetUpperBound(0);
            for (int J = 0; J <= UB; J++) {
                sb.AppendFormat("{0}*{0}", AnswerValArrList[I][J]);
                if (J <= UB - 2) sb.Append(" + ");
                if (J == UB - 1) sb.Append(" = ");
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //各項の候補を作成
    static KouhoInfoDef[] CreateKouhoInfoArr()
    {
        var WillReturn = new List<KouhoInfoDef>();
        for (int I = 1; I <= 98765; I++) {
            var NumSet = new HashSet<int>();
            bool IsValid;
            DeriveNumList(I, out  NumSet, out IsValid);
            if (IsValid)
                WillReturn.Add(new KouhoInfoDef() { Val = I, NumArr = NumSet.ToArray() });
        }
        return WillReturn.ToArray();
    }

    //数字のリストを作成
    static void DeriveNumList(int pTargetVal, out HashSet<int> pNumSet, out bool pIsValid)
    {
        pNumSet = new HashSet<int>();
        pIsValid = false;

        int CopiedVal = pTargetVal;
        do {
            int ModVal = CopiedVal % 10;
            if (ModVal == 0) return;
            if (pNumSet.Add(ModVal) == false) return;
            CopiedVal /= 10;
        } while (CopiedVal > 0);
        pIsValid = true;
    }

    //桁数を求める
    static int DeriveKetasuu(int pTargetNum)
    {
        if (pTargetNum < 10) return 1;
        if (pTargetNum < 100) return 2;
        if (pTargetNum < 1000) return 3;
        if (pTargetNum < 10000) return 4;
        if (pTargetNum < 100000) return 5;
        return 6;
    }
}


実行結果

解1 2*2 + 7*7 + 9*9 + 41*41 + 53*53 = 68*68
解2 4*4 + 12*12 + 36*36 + 87*87 = 95*95
解3 5*5 + 19*19 + 43*43 + 67*67 = 82*82
解4 8*8 + 14*14 + 39*39 + 62*62 = 75*75

経過時間=00:00:45.3535840


解説

計算量を減らすのに、必要条件での絞込みや、枝切りを使ってます。

左辺に5桁以上の数を含むと
10000*10000 >= 9876*9876 なので
左辺の数は全て、4桁以下

右辺が8桁で左辺の最大値を考えると、
9*9 = 81
右辺が7桁で左辺の最大値を考えると、
9*9+9*9 = 162
99*99 = 9801
右辺が6桁で左辺の最大値を考えると、
9*9+9*9+9*9 = 243
9*9+99*99 = 9882
999*999 = 998001
右辺の最小値は、100000*100000= 100億
よって、各項は全て5桁以下

左辺が2桁 + 3桁 で 右辺が4桁の場合を考えると、
左辺の最大値は、98*98+987*987 = 983773
右辺の最小値は、1234*1234 = 1522756
なので、左辺が2桁 + 3桁は不適