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

問題

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

Fig.1 小町虫食い算

ソース

<?php error_reporting(E_ALL);

const Jyougen = 999;
$SosuuArr = array();

Solve();

//エラトステネスの篩
function Eratosthenes()
{
GLOBAL $SosuuArr;
    for ($I = 2 ; $I <= Jyougen ; $I++){
        $SosuuArr[$I] = $I;
    }
    for ($I = 2; $I * $I <= Jyougen; $I++) {
        if ($I != 2 && $I % 2 == 0) continue;

        if ($SosuuArr[$I] != 0) {
            for ($J = $I * 2; $J <= Jyougen; $J += $I) {
                $SosuuArr[$J] = 0;
            }
        }
    }
    $SosuuArr = array_filter($SosuuArr,
                             function($pVal){
                                 return $pVal != 0
                                     && $pVal >= 100
                                     && IsValidVals(array($pVal));
                             });
    $SosuuArr = array_values($SosuuArr);
}

class JyoutaiDef
{
    public $CurrP;
    public $ValList;
}

function Solve()
{
GLOBAL $SosuuArr;
    Eratosthenes();

    $Stk = new SplStack();

    for ( $P = 0 ; $P <= count($SosuuArr) - 1 ; $P++){
        if ($SosuuArr[$P] * 3 > 999) break;
        $WillPush = new JyoutaiDef();
        $WillPush->CurrP = $P;
        $WillPush->ValList = array($SosuuArr[$P]);
        $Stk->push($WillPush);
    }

    $AnswerCnt = 0;
    while($Stk->isEmpty() == false){
        $Popped = $Stk->pop();

        if (count($Popped->ValList) == 3){
            $SumVal = array_sum($Popped->ValList);

            //和が3桁だったら
            if (100 <= $SumVal && $SumVal <= 999) {
                printf('解%dを発見' . PHP_EOL , ++$AnswerCnt);
                PrintAnswer($Popped->ValList);
            }
            continue;
        }

        for ($P = $Popped->CurrP + 1; $P <= count($SosuuArr) - 1 ; $P++) {
            $WillPush = new JyoutaiDef();
            $WillPush->CurrP = $P;
            $WillPush->ValList = array_merge($Popped->ValList , array($SosuuArr[$P]));
            if (IsValidVals($WillPush->ValList))
                $Stk->push($WillPush);
        }
    }
}

//有効な数値リストかを判定
function IsValidVals($pValList)
{
    $IsAppearedArr = array();

    foreach($pValList as $AnyInt){
        $CopiedVal = $AnyInt;
        do {
            $ModVal = $CopiedVal % 10;

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

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

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

//解を表示
function PrintAnswer($pValList)
{
    for ( $I = 0; $I <= count($pValList) - 1; $I++) {
        echo $pValList[$I];
        if ($I < count($pValList) - 1) echo '+';
    }
    printf('=%d' , array_sum($pValList));
}

実行結果

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

解説

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

C#で解いたもの