コンピュータパズルへの招待 1問目 小町虫食算

問題

Fig.1の□に1〜9をひとつづつ配置して、
3つの3桁の数が全て素数となるようにしたら、和が3桁になった。
このような素数の組み合わせは何通りあるか？

Fig.1 小町虫食い算

ソース

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

class Program
{
    const int Jyougen = 999;
    static int[] SosuuArr = new int[Jyougen + 1];

    //エラトステネスの篩
    static void Eratosthenes()
    {
        for (int I = 2; I <= SosuuArr.GetUpperBound(0); I++) {
            SosuuArr[I] = I;
        }
        for (int I = 2; I * I <= SosuuArr.GetUpperBound(0); I++) {
            if (I != 2 && I % 2 == 0) continue;

            if (SosuuArr[I] != 0) {
                for (int J = I * 2; J <= SosuuArr.GetUpperBound(0); J += I) {
                    SosuuArr[J] = 0;
                }
            }
        }

        SosuuArr = SosuuArr.Where(X => X != 0).ToArray();
        SosuuArr = SosuuArr.Where(X => 100 <= X).ToArray();
        SosuuArr = SosuuArr.Where(X => IsValidVals(new List<int>() { X })).ToArray();
    }

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

    static void Main()
    {
        Eratosthenes();

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

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

            if (Popped.ValList.Count == 3) {
                int SumVal = Popped.ValList.Sum();

                //和が3桁だったら
                if (100 <= SumVal && SumVal <= 999) {
                    Console.WriteLine("解{0}を発見", ++AnswerCnt);
                    PrintAnswer(Popped.ValList);
                }
                continue;
            }

            for (int P = Popped.CurrP + 1; P <= SosuuArr.GetUpperBound(0); P++) {
                WillPush.CurrP = P;
                WillPush.ValList = new List<int>(Popped.ValList) { SosuuArr[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;
            } while ((CopiedVal /= 10) > 0);
        }
        return true;
    }

    //解を表示
    static void PrintAnswer(List<int> pValList)
    {
        for (int I = 0; I <= pValList.Count - 1; I++) {
            Console.Write("{0}", pValList[I]);
            if (I < pValList.Count - 1) Console.Write('+');
        }
        Console.WriteLine("={0}", pValList.Sum());
    }
}

実行結果

解1を発見
149+263+587=999

解説

エラトステネスの篩で3桁の素数を列挙しておいてから、
深さ優先探索で検証してます。