Cマガ電脳クラブ(第042回) 平方数の和

問題

1から9までの数字を1字ずつ使って､たとえば157326849という数字を作る｡
これは12543の2乗､つまり平方数である｡

さて、35721と8649というふたつの数を作っても、これまたどちらも平方数である。
では1から9までの数字を1字ずつ使って平方数を作ったとき､できた平方数の総和を得点と定義する｡
上記の35721と8649の場合､44370点である｡
この場合は､ふたつの平方数に分けたが､もっと多くの個数にすることもできる｡
では最小得点になるものを探してほしい。

ソース

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

class Program
{
    //得点の上限
    static int TokutenJyougen = 9999;

    //候補の平方数リスト
    static List<int> HeihouSuuList = new List<int>();

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

    static void Main()
    {
        Console.WriteLine("得点の上限を{0}として検証します。",TokutenJyougen);
        Console.WriteLine();

        for (int I = 1; I * I <= TokutenJyougen; I++)
            HeihouSuuList.Add(I * I);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (int P = 0; P <= HeihouSuuList.Count - 1; P++) {
            WillPush.CurrP = P;
            WillPush.ValList = new List<int>() { HeihouSuuList[P] };
            stk.Push(WillPush);
        }

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

            int StrLengthSum = Popped.ValList.Sum(X => X.ToString().Length);

            if (StrLengthSum == 9) {
                int Tokuten = Popped.ValList.Sum();
                if (TokutenJyougen < Tokuten) continue;
                TokutenJyougen = Tokuten;

                PrintAnswer(Popped.ValList);
                continue;
            }

            for (int P = Popped.CurrP + 1; P <= HeihouSuuList.Count - 1; P++) {
                WillPush.CurrP = P;
                WillPush.ValList = new List<int>(Popped.ValList) { HeihouSuuList[P] };
                if (IsValidVals(WillPush.ValList))
                    stk.Push(WillPush);
            }

        }
    }

    //有効な数値リストかを判定
    static bool IsValidVals(List<int> pValList)
    {
        bool[] IsAppearedArr = new bool[10];

        foreach (int AnyInt in pValList) {
            int CopiedVal = AnyInt;
            do {
                int ModVal = CopiedVal % 10;

                //0を含んだらNG
                if (ModVal == 0) return false;

                //同じ数字を2個以上含んだらNG
                if (IsAppearedArr[ModVal]) return false;
                IsAppearedArr[ModVal] = true;

                CopiedVal /= 10;
            } while (CopiedVal > 0);
        }
        return true;
    }

    //解を表示
    static void PrintAnswer(List<int> pValList)
    {
        //平方根を求める
        Func<int, int> GetHeihouKon = (pVal) =>
        {
            return (int)Math.Sqrt(pVal);
        };

        Console.WriteLine("得点が{0}の解を発見", pValList.Sum());
        pValList.ForEach(X =>
            Console.Write("{0}({1}の2乗) , ", X, GetHeihouKon(X)));
        Console.WriteLine();
    }
}

実行結果

得点の上限を9999として検証します。

得点が1674の解を発見
361(19の2乗) , 529(23の2乗) , 784(28の2乗) ,
得点が990の解を発見
9(3の2乗) , 81(9の2乗) , 324(18の2乗) , 576(24の2乗) ,
得点が855の解を発見
1(1の2乗) , 9(3の2乗) , 25(5の2乗) , 36(6の2乗) , 784(28の2乗) ,

解説

得点の上限を仮決めしてから、平方数を列挙して、深さ優先探索してます。
深さ優先探索中に、パンデジタル数になりうるかを条件として、枝切りしてます。