覆面算パズルを解くアルゴリズム｜BASE＋BALL＝GAMESを例に解説

覆面算（クリプト算術）とは

覆面算（Crypt-arithmetic problem）とは、アルファベットの各文字に異なる数字（0～9）を割り当て、算式が正しく成立するようにするパズルです。使用できる文字は最大10種類までで、それぞれの文字には0から9までのいずれかの数字が一意に対応します。

典型的な問題では、2つの単語が与えられ、この2つの単語の和として表される3つ目の単語が答えになります。例えば「BASE」と「BALL」という2つの単語に対し、それぞれの文字に割り当てた数字で足し算を行うと、答えが「GAMES」になるような組み合わせを求めます。

注意： 使用できる文字は必ず10種類以内である必要があります。11種類以上になると、10個の数字では対応付けが不可能なため、問題を解けません。

入力と出力

入力：
このアルゴリズムでは3つの単語を受け取ります。
　　　　B A S E
　　　　B A L L
　　　　----------
　　　　G A M E S

出力：
各文字が0～9のどの数字に対応するかを表示します。
本ケースの場合、以下のようになります。
　　　　B A S E　　　　　　　　　　　　　2 4 6 1
　　　　B A L L　　　　　　　　　　　　 2 4 5 5
　　　　---------　　　　　　　　　　　 ---------
　　　　G A M E S　　　　　　　　　　 0 4 9 1 6

アルゴリズム

この問題では、文字とそれに対応する値を保持する「ノード」を定義します。探索にはバックトラッキング（深さ優先探索）を用い、すべての数字の割り当てパターンを順に試していきます。

isValid 関数

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

入力： ノードのリスト、リスト内の要素数、および3つの単語。

出力： word1 と word2 の値の合計が word3 の値と一致する場合に True を返します。

Begin
    m := 1
    word1 の各文字 i を右から左へ処理する
        ch := word1[i]
        nodeList 内のすべての要素 j について
            if nodeList[j].letter = ch ならば
                ループを抜ける
        val1 := val1 + (m * nodeList[j].value)
        m := m * 10

    m := 1
    word2 の各文字 i を右から左へ処理する
        ch := word2[i]
        nodeList 内のすべての要素 j について
            if nodeList[j].letter = ch ならば
                ループを抜ける
        val2 := val2 + (m * nodeList[j].value)
        m := m * 10

    m := 1
    word3 の各文字 i を右から左へ処理する
        ch := word3[i]
        nodeList 内のすべての要素 j について
            if nodeList[j].letter = ch ならば
                ループを抜ける
        val3 := val3 + (m * nodeList[j].value)
        m := m * 10

    if val3 = (val1 + val2) ならば
        return true
    return false
End

permutation 関数

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

入力： ノードのリスト、リスト内の要素数、割り当て済みの文字数、および3つの単語。

出力： すべての文字に正しく値が割り当てられ、算式が成立した場合に True を返します。

Begin
    n 文字すべてに値が割り当てられたら
        0 ～ 9 の各数字 i について
            if 数字 i が未使用ならば
                nodeList[n].value := i
                if isValid(nodeList, count, word1, word2, word3) = true
                    nodeList 内の全項目 j について
                        文字と対応する値を表示する
                    return true
    return false

    0 ～ 9 の各数字 i について
        if 数字 i が未使用ならば
            nodeList[n].value := i
            i を使用済みとしてマークする
            if permutation(nodeList, count, n+1, word1, word2, word3) ならば
                return true
            そうでなければ i を未使用に戻す（バックトラック）
    return false
End

C++による実装例

#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;

   for (i = s1.length() - 1; i >= 0; i--) {     // 1つ目の文字列に対応する数値を求める
      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;
   for (i = s2.length() - 1; i >= 0; i--) {     // 2つ目の文字列に対応する数値を求める
      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;
   for (i = s3.length() - 1; i >= 0; i--) {     // 3つ目の文字列に対応する数値を求める
      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 0;
   }

   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

この結果より、BASE ＝ 2461、BALL ＝ 2455、GAMES ＝ 04916（＝4916）となり、2461 ＋ 2455 ＝ 4916 で算式が正しく成立していることが確認できます。

まとめ

覆面算の求解は、バックトラッキングによる全探索が基本アプローチとなります。使用されていない数字を順番に文字へ割り当てながら再帰的に探索し、条件を満たさなくなった時点で前の状態に戻って別の候補を試します。一意な文字が10種類以内という制約があるため、最悪計算量は O(10!) 程度ですが、枝刈りや制約伝播などの工夫によってさらに高速化することも可能です。