數謎謎面產生器

幾個星期前做了程式解數謎之後，就意識到，其實數謎謎面的製作，似乎也是個同樣程度的難題。出題者必須要找出有意義的單字組合，同時還要讓對應的數式成立。

如果要以程式來產生「有意義的單字的組合」還得靠 NLP 模型（其結果是否有趣則又是另外一個題目）。但如果暫時不考慮這部分，只做一個簡化一些的版本，則容易得多。比方說只考慮這種簡化版：「使用者需先輸入謎底，再由程式找出謎面。謎面需由英語單字構成」。

跟解謎器很類似，基本上是以某種搜尋演算法找出數字與字母的對應關係。但這回的限制條件不是「算式是否成立」，而是「是否有構成英文單字」。

爲了判斷某個字串是否爲英文單字，最簡單的方式就是直接使用現有的字典檔案。好比說 /usr/share/dict/words 這個檔案。

以下是是以 Raku 語言寫成的遞迴搜尋解。其中 cryptarithm-gen 函式的參數 @nums 爲謎底中用到的數字，比方說定謎底爲 49 + 51 = 100，則 @nums 應爲 [49, 51, 100]。參數 @words 則爲英文單字的字串陣列。其中的 gen 函式爲遞迴本體，其他部分爲事前準備步驟：

sub cryptarithm-gen (@nums, @words) {
    # [0]
    my Set $words = @words.Set;
    my @digits = @nums.map({ .comb.Slip }).unique;

    # [1]
    my sub gen (%letter-from-digit) {
        my @solutions;

        # [2]
        return @solutions if @nums.first({
            .comb.map({ %letter-from-digit{$_} }).Array.&{
                .all && .join() ∉ $words
            }});

        my $unbound-digit = @digits.first({ %letter-from-digit{$_}:!exists });

        # [3]
        unless $unbound-digit.defined {
            @solutions.push( %letter-from-digit );
            return @solutions;
        }

        # [4]
        for (("A".."Z") ∖ %letter-from-digit.values).keys.sort -> $c {
            my @s = gen(%( %letter-from-digit, $unbound-digit => $c ));
            @solutions.append(@s) if @s.elems > 0;
        }

        return @solutions.grep(&defined);
    }

    return gen(%());
}

以下是說明。

[0] 爲事前準備。先把字典內容做成集合 (Set)，讓檢查元素是否存在的操作較爲快速。並且準備一個 @digits 整數陣列，內容爲在謎底 @nums 中有出現的數目字。在謎底中沒出現的數目字，就不必納入搜尋範圍內。

[1] 爲遞迴搜尋演算法本體。此演算法會窮舉出所有謎面，放入 @solutions 這個陣列後傳回。謎面的形式爲字母對應表 %letter-from-digit。

[2] 爲遞迴搜尋的第一個終端條件：由產生出來的字母對應表，將 @nums 中的數字轉換爲字母字串。但若是轉換後的結果不屬於 $words 這個集合，那就宣告無解（傳回空陣列）。

[3] 爲遞迴搜尋的第二個終端條件：找出尚未有對應的數目字 $unbound-digit。如果或全部都對應完畢，那表示目前的字母對應表 %letter-from-digit 爲一組有效解答。得放入 @solutions 之後傳回。

[4] 爲搜尋過程：剛剛取得的數目字 $unbound-digit 尚無對應到任何字母，那麼就將其逐一對應到 'A'...'Z' 範圍中所有尚可對應的字母。若某字母已經存在於字母對應表 %letter-from-digit 中的話，則不該再被二次對應。對應完畢後再叫 gen()、將新對應表傳入，並將解答（謎面）併入 @solutions 中。蒐集完所有解答後則可將 @solutions 傳回。

這算是個窮舉搜尋演算法，並沒有用上任何加速或減少搜尋範圍的手段。比方說字典檔中沒有任何單字包含了 kx 這個 bigram，因此在 [4] 處，若直接避免掉這種組合的出現，就可減少很大一部分的搜尋範圍。並且，有很多重複的運算都是可以省下的（像是把 @nums 數字字串轉換成字母字串的這段過程）。這都是一些可以再調整的選項。