Cマガ電脳クラブ(第116回) 三数教室

問題

ここに，それぞれ3個の数からなる組が3組ある。
(12，18，35)
(10，27，28)
(14，15，36)
それぞれの組について，3個の数の和をとるとすべて65になる。
また積は7560となり，やはり同じになっている。

ではこれを4組に拡張し，
「3数づつが4組あり，各組の和をとっても積をとっても同じになる」という数の組み合わせをひとつ見つけてほしい。
ここに登場する数はすべて正の整数で，同じ数は使わない。余裕のある方は5組でも挑戦していただきたい。

ソース

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

class Program
{
    const int Jyougen = 135;

    static void Main()
    {
        Solve(3);
        Solve(4);
        Solve(5);
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal List<int[]> NumArrList;
        internal int SumVal;
        internal int ProdVal;
    }

    //組の数を指定して、解を求める
    static void Solve(int pCombiCnt)
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.NumArrList = new List<int[]>();
        WillPush.SumVal = WillPush.ProdVal = 0;
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.Level == pCombiCnt) {
                Console.WriteLine("{0}組の解を発見。経過時間={1}",
                    pCombiCnt, sw.Elapsed);
                foreach (int[] EachNumArr in Popped.NumArrList) {
                    Array.ForEach(EachNumArr, X => Console.Write("{0},", X));
                    Console.WriteLine();
                }
                break;
            }

            var UsedNumSet = new HashSet<int>();
            Popped.NumArrList.ForEach(X => UsedNumSet.UnionWith(X));

            int[] FirstValArr = Popped.NumArrList.Select(X => X[0]).ToArray();
            bool Calced = (Popped.Level >= 1);

            for (int I = 1; I <= Jyougen; I++) {
                if (Array.Exists(FirstValArr, X => X > I)) continue;
                if (UsedNumSet.Contains(I)) continue;
                if (Calced && Popped.ProdVal % I != 0) continue;
                if (Calced && Popped.SumVal <= I * 3) break;
                if (Calced && Popped.ProdVal <= I * I * I) break;

                for (int J = I + 1; J <= Jyougen; J++) {
                    if (UsedNumSet.Contains(J)) continue;
                    if (Calced && Popped.ProdVal % J != 0) continue;
                    if (Calced && Popped.SumVal <= I + J * 2) break;
                    if (Calced && Popped.ProdVal <= I * J * J) break;
                    for (int K = J + 1; K <= Jyougen; K++) {
                        if (UsedNumSet.Contains(K)) continue;

                        int wkSumVal = I + J + K;
                        int wkProdVal = I * J * K;
                        if (Calced && Popped.SumVal < wkSumVal) break;
                        if (Calced && Popped.ProdVal < wkProdVal) break;
                        if (Calced && Popped.SumVal != wkSumVal) continue;
                        if (Calced && Popped.ProdVal != wkProdVal) continue;

                        WillPush.Level = Popped.Level + 1;
                        WillPush.NumArrList = new List<int[]>(Popped.NumArrList);
                        WillPush.NumArrList.Add(new int[] { I, J, K });
                        WillPush.SumVal = wkSumVal;
                        WillPush.ProdVal = wkProdVal;
                        stk.Push(WillPush);
                    }
                }
            }
        }
    }
}

実行結果

3組の解を発見。経過時間=00:00:01.9579575
104,120,126,
105,117,128,
108,112,130,
4組の解を発見。経過時間=00:00:04.1358141
54,100,112,
56,90,120,
60,80,126,
63,75,128,
5組の解を発見。経過時間=00:00:24.3401239
11,84,90,
12,63,110,
15,44,126,
18,35,132,
22,28,135,

解説

深さ優先探索で小まめに枝切りしてます。