C++で解く覆面算パズル ― SEND＋MORE＝MONEYをバックトラッキングで攻略

覆面算パズルとは？

覆面算（ふくめんざん）とは、数式内の数字をアルファベットなどの記号に置き換えたパズルです。ここでは、等式の左辺を複数の単語（文字列）、右辺を結果の単語として表現したとき、その等式が以下のルールのもとで成立するかどうかを判定する問題を扱います。

• 文字と数字の対応： 各文字は 0〜9 のいずれか1桁の数字に割り当てられる。
• 一意性： 異なる文字には必ず異なる数字が割り当てられる。
• 先頭ゼロの禁止： words[i] および result を数値として読み取る際、先頭に 0 が来てはならない。
• 等式の成立： 左辺の数値の総和が右辺の数値と一致すること。
• 判定： 以上の条件を満たす割り当てが存在するかどうかを求める。

例えば、入力が words = ["SEND", "MORE"]、result = "MONEY" だった場合、出力は True になります。各文字を次のように対応させると、「SEND」＋「MORE」＝「MONEY」が 9567 ＋ 1085 ＝ 10652 として成立するためです。

S→9、E→5、N→6、D→7、M→1、O→0、R→8、Y→2

解法の考え方：バックトラッキング

この問題はバックトラッキング（探索と巻き戻し）で効率的に解けます。基本戦略は、一の位から順に各けたごとの総和を計算しながら、未割り当ての文字に対して使える数字を順番に試していくことです。途中で矛盾が生じたら直前の割り当てを解除し、別の数字を試します。

使用するデータ構造

• i2c[10]：数字（0〜9）→ 文字 への対応表（未割り当ては -1）
• c2i[26]：文字（A〜Z）→ 数字 への対応表（未割り当ては -1）
• w：左辺の単語リスト、r：右辺の結果文字列（どちらも反転し、一の位から処理）

再帰関数 solve(idx, l, sum) の流れ

1. 終了条件： l が r の長さに達したら、sum が 0（繰り上がりなし）の場合に true を返す。
2. 結果側の処理： idx が w のサイズに達したら、r[l] に対応する数字を確認する。
   • すでに割り当て済みなら、その値が sum % 10 と一致するときだけ次のけたへ進む。
   • 未割り当てなら、sum % 10 が未使用の数字であれば割り当てて再帰呼び出しを行い、失敗したら元に戻す。ただし最上位けたが 0 になる場合は false。
3. 短い単語のスキップ： l が w[idx] の長さ以上なら、次の単語へ進む。
4. 割り当て済みの文字： w[idx][l] に対応する数字が決まっていれば、それを sum に加算して次の単語へ。ただし先頭（最上位けた）が 0 の場合は false。
5. 未割り当ての文字： 0〜9 のうち未使用の数字を順に試し、割り当てて再帰呼び出し。成功すれば true を返し、失敗したら割り当てを解除して次の候補へ。

メイン処理の流れ

1. i2c と c2i をすべて -1 で初期化する。
2. result と各 words[i] を反転させ、一の位から処理できるようにする。
3. どれかの単語が result より長ければ、その時点で false を返す（繰り上がりでけた数が増えることはないため）。
4. solve(0, 0, 0) を呼び出して結果を返す。

それでは、実際の実装を見てみましょう。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    char i2c[10];
    int c2i[26];
    vector<string> w;
    string r;
    bool solve(int idx, int l, int sum){
       if (l == r.size()) {
          return sum == 0;
       }
       if (idx == w.size()) {
          if (c2i[r[l] - 'A'] != -1) {
             if (c2i[r[l] - 'A'] == sum % 10) {
                return solve(0, l + 1, sum / 10);
             }
          }
          else if (i2c[sum % 10] == -1) {
             if (l == r.size() - 1 && sum % 10 == 0)
             return false;
             c2i[r[l] - 'A'] = sum % 10;
             i2c[sum % 10] = r[l] - 'A';
             bool temp = solve(0, l + 1, sum / 10);
             c2i[r[l] - 'A'] = -1;
             i2c[sum % 10] = -1;
             return temp;
          }
          return false;
       }
       if (l >= w[idx].size()) {
          return solve(idx + 1, l, sum);
       }
       if (c2i[w[idx][l] - 'A'] != -1) {
          if (l == w[idx].size() - 1 && c2i[w[idx][l] - 'A'] == 0){
             return false;
          }
          return solve(idx + 1, l, sum + c2i[w[idx][l] - 'A']);
       }
       for (int i = 0; i < 10; i++) {
          if (i2c[i] != -1)
          continue;
          if (i == 0 && l == w[idx].size() - 1)
          continue;
          i2c[i] = w[idx][l] - 'A';
          c2i[w[idx][l] - 'A'] = i;
          bool temp = solve(idx + 1, l, sum + i);
          i2c[i] = -1;
          c2i[w[idx][l] - 'A'] = -1;
          if (temp)
          return true;
       }
       return false;
   }
    bool isSolvable(vector<string>& words, string result){
       memset(i2c, -1, sizeof(i2c));
       memset(c2i, -1, sizeof(c2i));
       reverse(result.begin(), result.end());
       for (int i = 0; i < words.size(); i++) {
          if (words[i].size() > result.size())
          return false;
          reverse(words[i].begin(), words[i].end());
       }
       r = result;
       w = words;
       return solve(0, 0, 0);
   }
};
main(){
    Solution ob;
    vector<string> v = {"SEND","MORE"};
    cout << (ob.isSolvable(v, "MONEY"));
}

入力

{"SEND","MORE"}, "MONEY"

出力

1

このコードでは、SEND ＋ MORE ＝ MONEY が解を持つため、出力として 1（true）が表示されます。単語を反転して一の位から処理することで、けたごとの繰り上がりを自然に扱える点が、この実装のポイントです。