Cマガ電脳クラブ(第040回) 小町算で小町数

問題

1から9までが1回ずつ登場する数を小町数、
1から9までを1個ずつ使った計算を小町算と娯楽数学家は呼んでいる。

今回は小町かけ算で小町数を作ってみた。たとえば、
    256384197 = 9×621×45873
がその例である。同じ小町数を別の小町算で表せる例もある。
    173549628 = 378×459126
              = 3×9×84×76521
    413972856 = 72×891×6453
              = 81×792×6453
              = 9×6453×7128
では、ある小町数を4通りの小町算で表せるか。あればそれは何通りあるか、すべてを見つけてほしい。
5通り以上で表せるかも調べてほしい。

ソース

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

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

    static Dictionary<int, List<string>> ResultDict =
        new Dictionary<int, List<string>>();

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

        var KouhoValList = new List<int>();
        //1を使うと、積が9桁にならないので、ループは2から
        for (int I = 2; I <= 98765432; I++) {
            if (IsValidVals(new List<int>() { I }))
                KouhoValList.Add(I);
        }
        int[] KouhoValArr = KouhoValList.ToArray();
        Console.WriteLine("KouhoValArr.Length={0}", KouhoValArr.Length);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (int P = 0; P <= KouhoValArr.GetUpperBound(0); P++) {
            if (KouhoValArr[P] * KouhoValArr[P] > 987654321) break;
            WillPush.CurrP = P;
            WillPush.ValList = new List<int>() { KouhoValArr[P] };
            WillPush.ProdVal = KouhoValArr[P];
            stk.Push(WillPush);
        }

        int CombiCnt = 0;

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

            int KetasuuSum = Popped.ValList.Sum(X => DeriveKetasuu(X));
            if (KetasuuSum == 9) {
                if (DeriveKetasuu(Popped.ProdVal) < 9) continue;
                if (IsValidVals(new List<int>() { Popped.ProdVal }) == false) continue;

                var sb = new System.Text.StringBuilder();
                for (int I = 0; I <= Popped.ValList.Count - 1; I++) {
                    sb.Append(Popped.ValList[I]);
                    if (I < Popped.ValList.Count - 1)
                        sb.Append('*');
                }
                sb.AppendFormat(" = {0}", Popped.ProdVal);

                if (ResultDict.ContainsKey(Popped.ProdVal))
                    ResultDict[Popped.ProdVal].Add(sb.ToString());
                else ResultDict[Popped.ProdVal] = new List<string>() { sb.ToString() };

                if (++CombiCnt % 100 == 1)
                    Console.WriteLine("{0}。{1}個目の小町算と小町数。{2}",
                        sw.Elapsed, CombiCnt, sb.ToString());

                continue;
            }

            for (int P = Popped.CurrP + 1; P <= KouhoValArr.GetUpperBound(0); P++) {
                int KouhoKetasuu = DeriveKetasuu(KouhoValArr[P]);

                //桁数の和で枝切り
                if (KetasuuSum + KouhoKetasuu > 9) break;
                if (KetasuuSum + KouhoKetasuu < 9 && KetasuuSum + 2 * KouhoKetasuu > 9) continue;

                long wkProdLong = (long)(Popped.ProdVal) * KouhoValArr[P];

                if (wkProdLong > 987654321) break; //積の上限を超えたら枝切り
                int wkProdInt = (int)wkProdLong;
                if (wkProdInt % 10 == 0) continue; //1桁目が0なら枝切り

                WillPush.CurrP = P;
                WillPush.ValList = new List<int>(Popped.ValList) { KouhoValArr[P] };
                if (IsValidVals(WillPush.ValList) == false) continue;
                WillPush.ProdVal = wkProdInt;
                stk.Push(WillPush);
            }
        }

        //4通り未満の小町算でしか表せない小町数をRemove
        foreach (int AnyKey in ResultDict.Keys.ToArray())
            if (ResultDict[AnyKey].Count < 4) ResultDict.Remove(AnyKey);

        foreach (var AnyPair in ResultDict.OrderBy(X => X.Key)) {
            Console.WriteLine("{0}通りの小町算で表せる、小町数{1}を発見",
                AnyPair.Value.Count, AnyPair.Key);
            foreach (string AnyStr in AnyPair.Value.OrderBy(X => X))
                Console.WriteLine(AnyStr);
        }
    }

    //有効な数値リストかを判定
    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;
            } while ((CopiedVal /= 10) > 0);
        }
        return true;
    }

    //数値の桁数を返す
    static int DeriveKetasuu(int pVal)
    {
        if (pVal < 10) return 1;
        if (pVal < 100) return 2;
        if (pVal < 1000) return 3;
        if (pVal < 10000) return 4;
        if (pVal < 100000) return 5;
        if (pVal < 1000000) return 6;
        if (pVal < 10000000) return 7;
        if (pVal < 100000000) return 8;
        return 9;
    }
}

実行結果

省略
00:04:54.7255640。2601個目の小町算と小町数。3*71645289 = 214935867
00:04:54.7407977。2701個目の小町算と小町数。3*56427918 = 169283754
00:04:58.8258756。2801個目の小町算と小町数。3*762*85419 = 195267834
4通りの小町算で表せる、小町数127359648を発見
32*459*8671 = 127359648
6*9*754*3128 = 127359648
9*23*754*816 = 127359648
92*754*1836 = 127359648
4通りの小町算で表せる、小町数132759648を発見
4*56*729*813 = 132759648
9*24*756*813 = 132759648
9*54*273168 = 132759648
972*136584 = 132759648
4通りの小町算で表せる、小町数164759832を発見
4*9*86*53217 = 164759832
438*516*729 = 164759832
5913*27864 = 164759832
9*216*84753 = 164759832
4通りの小町算で表せる、小町数169857324を発見
3276*51849 = 169857324
36*4718259 = 169857324
4*91*567*823 = 169857324
6*7*54*91*823 = 169857324
4通りの小町算で表せる、小町数172349856を発見
3*672*85491 = 172349856
46*72*98*531 = 172349856
6*7*84*92*531 = 172349856
8*92*413*567 = 172349856
4通りの小町算で表せる、小町数419527836を発見
51*972*8463 = 419527836
6*93*751842 = 419527836
62*91*74358 = 419527836
63*918*7254 = 419527836

解説

小町数の配列の経路に対する、深さ優先探索の中で
・桁数の和で枝切りが2つ
・積の上限を超えたら枝切り
・積の1桁目が0なら枝切り
といった枝切りをBreak文とContinue文を使い分けて仕掛けてます。