數謎解謎器

數謎 (Cryptarithm) 是種算數謎題，謎面是由三個以上的英文單字所寫成的一個算式，其中每個字母都對應到一個自零至九之間的數目字。通常以直式寫出，例如這個經典範例：

  SEND
+ MORE
------
 MONEY

解謎者需要推敲出每個字母所對應的數目字，使算式成立。一個比較簡單的範例是：

  SO
+ SO
----
 TOO

應該不難看出有 S = 5, T = 1, O = 0 這組解。而大部分數謎都是透過讓字母的重複出現，而設計成只有一組解。

如果有個謎面是 AB + CD = EF，每個字母都只用過一次，那就隨意令 AB=12 且 C=3，馬上就可讓謎面簡化成 12 + 3D = 4F 從而得到 D=5 且 F=7。也就是 12 + 35 = 47 這組解。而且再將前面兩個數字對調，成 35 + 12 = 47，又是另一組解。

也就是說如果重複字母很少，讓自由度太高，反而會使題目變得過於簡單。

要手動解這種謎題，可先試著找出明顯的部分解答，將謎面簡化。以 SEND + MORE = MONEY 爲例，慣例上可排除 S=0 與 M=0，因爲數字首位不會是零（不過也有允許首位爲零的玩法）。此外，很明顯的部分解答是 M = 1：因爲兩個相異的個位數字相加，最大可得 17 (= 9 + 8)，就算再加上進位，也只會得到 18。也就是說 M 只有可能是 1 。因此可得到 SEND + 1ORE = 1ONEY 這個稍微簡化一些些的謎面。同時，既然 M 對應到 1，那表示其他所有字母都不可能是 1。

下一步或許是考慮 S + 1 + 進位 = 1O。個位數字中加了 1 就會進位的只有 9。再考慮進位可能爲 1 或 0，則 S 只可能是 9 或 8。在此出現條件分歧，可在假設 S=9 的前提之下，繼續找出其他字母對應。

也就是這個謎題基本上是個搜尋問題。在排除掉一些明顯不對的選項之後，解謎者必須逐個嘗試。配合運算規則所帶來的限制，將衆多選項一一排除，最後無法被排除而留下來的，就是解答了。

這種謎題是個很適合用來以程式做搜尋演算法的題目。搜尋範圍就是謎面中用到的所有字母所對應到的數目字之組合與排列。

對此，我想了個遞迴解：

sub decryptarithm (
    $cryptExpr,
    $letters         = [ distinctLetters $cryptExpr ],
    $isNonZeroLetter = +{ map { $_ => true } firstLetters $cryptExpr },
    $digitFromLetter = +{},
    $digitAssigned   = +{},
) {
    my $unboundLetter = first { !exists $digitFromLetter->{$_} } @$letters;

    # (1)
    unless ( defined($unboundLetter) ) {
        my $plainExpr = plaintextfy( $cryptExpr, $digitFromLetter );
        my $evalExpr  = $plainExpr =~ s/=/==/gr;

        # (2)
        return eval( $evalExpr ) ? $plainExpr : ();
    }

    # (3)
    my @possibleDigits = grep { not $digitAssigned->{$_} } ( ( $isNonZeroLetter->{$unboundLetter} ? 1 : 0 ) .. 9 );

    map {
        decryptarithm(
            $cryptExpr, $letters, $isNonZeroLetter,
            +{ %$digitFromLetter, $unboundLetter, $_ },
            +{ %$digitAssigned,   $_,             true },
        )
    } @possibleDigits;
}

其中 $cryptExpr 就是謎面，以字串形式保存，如 "SEND + MORE = MONEY"。

在 (1) 處先處理終端條件。當 $unboundLetter 爲未定義的時候，也就是所有字母都已經有所對應的時候。這時就是依照 $digitFromLetter 這個對應表，把 $cryptExpr 明文化，得到 $plainExpr，並在 (2) 處，則是明文版本做出來後，簡單以 eval 來判別算式成立與否，如果成立，表示 $plainExpr 是一組解，得傳回，如果不成立，則傳回空的串列。

在 (3) 處，表示在 $unboundLetter 變數中所存的字母是還沒有與任何數字對應的，此時需列舉出能與這個字母對應的所有數目字，逐一遞迴嘗試。

這基本上就是個暴力搜尋的過程，除了通過 $isNonZeroLetter 來排除 0 之外，沒有寫入任何其他排除搜尋路徑的算式。是個很耗時間演算法。如果要做其他種類的排除，就必須先知道 $cryptExpr 內容是做加減乘除的那一項，再依照運算規則推敲出幾種排除規則。想來是需要不少算式才能描述得清楚。

這個解謎函式會找出謎面 $cryptExpr 的所有解答。若要讓它找第一組解後就停，那把最末的 map 改成 first 應該就可以了。