C++で覆面算パズルを解く方法｜バックトラッキングによる全探索アルゴリズムを徹底解説

覆面算（暗号算術）パズルとは？

覆面算（Crypt-Arithmetic Problem）とは、単語を構成する各アルファベットに0〜9の数字を割り当て、算式が正しく成立するようにするパズルです。異なる文字には必ず異なる数字が対応し、10進法の数字は0〜9の10種類しかないため、使用できる文字は最大10種類という制約があります。

典型的な例として、「BASE」と「BALL」という2つの単語が与えられ、その足し算の答えとして「GAMES」が与えられるケースがあります。各文字に適切な数字を割り当てれば、BASE＋BALL＝GAMES という等式が実際に成立します。

入力と出力

入力

このアルゴリズムでは、3つの単語（被加数・加数・答え）を受け取ります。

出力

どの文字が0〜9のどの数字に対応するかを出力します。BASE＋BALL＝GAMES の場合、解答は以下の通りです。

この対応を数値に置き換えると、2461（BASE）＋2455（BALL）＝4916（GAMES）となり、等式がきちんと成立していることが確認できます。

アルゴリズムの概要

この問題では、文字とそれに対応する値を保持するノードを定義します。解法の核となるのは、全ての数字の組み合わせを試す「バックトラッキング（全探索）」です。処理は主に2つの関数に分かれます。

isValid(nodeList, count, word1, word2, word3)

入力：ノードのリスト、リスト内の要素数、3つの単語
出力：word1とword2の値の合計がword3の値と一致すれば true

各単語を右端（1の位）から左へ向かって走査し、桁の重み（1、10、100…）を掛けながら数値を組み立てます。最後に val1 ＋ val2 ＝ val3 が成り立つかどうかを判定します。

Begin
    m := 1
    for each letter i from right to left of word1, do
        ch := word1[i]
        for all elements j in the nodeList, do
            if nodeList[j].letter = ch, then
                break
        done
        val1 := val1 + (m * nodeList[j].value)
        m := m * 10
    done
    （word2、word3 についても同様に処理）
    if val3 = (val1 + val2), then
        return true
    return false
End

permutation(nodeList, count, n, word1, word2, word3)

入力：ノードのリスト、リスト内の要素数、割り当て済みの文字数、3つの単語
出力：全ての文字に正しく値を割り当てて等式が成立した場合に true

まだ使われていない数字を順番に試し、再帰的に次の文字へと進みます。途中で失敗したらバックトラックして別の数字を試す、いわゆる深さ優先探索＋枝刈りの手法です。

Begin
    if n letters are assigned, then
        for all digits i from 0 to 9, do
            if digit i is not used, then
                nodeList[n].value := i
                if isValid(nodeList, count, word1, word2, word3) = true
                    for all items j in the nodeList, do
                        show the letter and corresponding values.
                    done
                    return true
        done
        return false
    for all digits i from 0 to 9, do
        if digit i is not used, then
            nodeList[n].value := i
            mark as i is used
            if permutation(nodeList, count, n+1, word1, word2, word3),
                return true
            otherwise mark i as not used
    done
    return false
End

C++での実装例

以下が実際のC++コードです。まず3つの単語に含まれる一意な文字を抽出し、それぞれの文字に対して未使用の数字を再帰的に割り当てていきます。

#include <iostream>
#include <vector>
using namespace std;

vector<int> use(10); // 数字が既に割り当てられていたら1にセット

struct node {
    char letter;  // 文字
    int value;    // 割り当てられた数字
};

// 等式が成立しているかを検証する関数
int isValid(node* nodeList, const int count, string s1, string s2, string s3) {
    int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i;

    // 1つ目の文字列に対応する数値を求める
    for (i = s1.length() - 1; i >= 0; i--) {
        char ch = s1[i];
        for (j = 0; j < count; j++)
            if (nodeList[j].letter == ch) // 文字が見つかったらループを抜ける
                break;
        val1 += m * nodeList[j].value;
        m *= 10;
    }

    m = 1;
    // 2つ目の文字列に対応する数値を求める
    for (i = s2.length() - 1; i >= 0; i--) {
        char ch = s2[i];
        for (j = 0; j < count; j++)
            if (nodeList[j].letter == ch)
                break;
        val2 += m * nodeList[j].value;
        m *= 10;
    }

    m = 1;
    // 3つ目の文字列（答え）に対応する数値を求める
    for (i = s3.length() - 1; i >= 0; i--) {
        char ch = s3[i];
        for (j = 0; j < count; j++)
            if (nodeList[j].letter == ch)
                break;
        val3 += m * nodeList[j].value;
        m *= 10;
    }

    if (val3 == (val1 + val2)) // 合計が3つ目の文字列の値と一致するか確認
        return 1;
    return 0;
}

// バックトラッキングによる順列生成
bool permutation(int count, node* nodeList, int n, string s1, string s2, string s3) {
    if (n == count - 1) { // 全ての文字に値を割り当て終えた場合
        for (int i = 0; i < 10; i++) {
            if (use[i] == 0) { // 未使用の数字について
                nodeList[n].value = i; // 値iを割り当てる
                if (isValid(nodeList, count, s1, s2, s3) == 1) { // 検証
                    cout << "Solution found: ";
                    for (int j = 0; j < count; j++) // 割り当てた文字と値を出力
                        cout << " " << nodeList[j].letter << " = "
                             << nodeList[j].value;
                    return true;
                }
            }
        }
        return false;
    }
    for (int i = 0; i < 10; i++) {
        if (use[i] == 0) { // 未使用の数字について
            nodeList[n].value = i; // 値iを割り当て、以後使えないようマーク
            use[i] = 1;
            if (permutation(count, nodeList, n + 1, s1, s2, s3)) // 次の文字へ
                return true;
            use[i] = 0; // バックトラック時には再度使用可能に戻す
        }
    }
    return false;
}

bool solvePuzzle(string s1, string s2, string s3) {
    int uniqueChar = 0; // 一意な文字の数
    int len1 = s1.length();
    int len2 = s2.length();
    int len3 = s3.length();

    vector<int> freq(26); // アルファベットは26種類
    for (int i = 0; i < len1; i++)
        ++freq[s1[i] - 'A'];
    for (int i = 0; i < len2; i++)
        ++freq[s2[i] - 'A'];
    for (int i = 0; i < len3; i++)
        ++freq[s3[i] - 'A'];

    for (int i = 0; i < 26; i++)
        if (freq[i] > 0) // 出現頻度が0より大きい文字が存在する
            uniqueChar++;

    if (uniqueChar > 10) { // 10進法では数字が10種類しかないため
        cout << "Invalid strings";
        return false;
    }

    node nodeList[uniqueChar];
    for (int i = 0, j = 0; i < 26; i++) { // 3つの文字列に含まれる全文字を登録
        if (freq[i] > 0) {
            nodeList[j].letter = char(i + 'A');
            j++;
        }
    }

    return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
}

int main() {
    string s1 = "BASE";
    string s2 = "BALL";
    string s3 = "GAMES";
    if (solvePuzzle(s1, s2, s3) == false)
        cout << "No solution";
}

実行結果

Solution found: A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6

まとめと注意点

このプログラムは、文字の総数が10以下であることを確認した上で、未使用の数字を1つずつ割り当てながら再帰的に探索を行い、等式が成立した時点で解答を出力します。

• 文字が11種類以上ある場合は、数字が足りなくなるため解なしとして扱われます。
• 最大10文字に対して最大10!（約362万）通りの割り当てが考えられますが、枝刈りによって実際の探索範囲は大きく削減されます。
• より厳密にするなら、「各単語の先頭の文字には0を割り当てない」という制約を追加するのが一般的です（先頭が0になると桁数が変わってしまうため）。