虫食い算【第1回】

はじめに

虫食い算

虫食い算とは、「□２＋３□＝４６」の様な数式の空欄に０～９の数字を入れて数式を完成させるパズルだ。
ただし、複数桁の最上位桁に０は入れてはいけない。
例えば、「□＋１＝□□」の場合、答えの２桁目は０は入らないので、９＋１＝１０ が解となる。

加算だけではなく、乗算・除算問題もある。乗算・除算問題はこの章の最後の問題例の様に、各桁ごとの計算結果も含まれる。
問題の難易度は当然ながら、加算＜乗算＜除算 の順に難しい。

「SEND + MORE = MONEY」のように同じ文字には同じ数字を入れるというタイプもあるが、本稿では取り扱わない。

虫食い算は数学的には「制約充足問題」に分類される。
制約充足問題は、制約条件を満たす状態を見つけるという数学問題で、数独、お絵かき
ロジックなど多くのペンシルパズルがこれにあたる。適当に数字などを入れていき、
空欄を全部埋めると、それが条件を満たしているかどうかは容易に判定できるが、
解を見つけるのは必ずしも容易ではない、という特徴を持つ。
なので、「□＋２＝□□」の様に解が複数ある問題は不適切とされている。

以下に、加算、乗算、除算問題の例を示す。解けるかな？

ソルバー

一般人向け虫食い算の探索空間は狭いので、全探索を行えば解を得ることができる。
最近のCPUであれば、探索する木の末端数が 10^6 程度であれば１秒未満で全探索することができる。
10^9 程度になると、数秒を超える。

空欄には ‘0’～’9′ が入る（ただし最初の桁に ‘0’ は入らない）ので、空欄数を N とすれば、探索数はおおよそ 10^N となる。
乗除算問題はすべての空欄を探索する必要はない。詳しくは後術する。

本稿では問題・解答のデータ構造として、文字列配列：vector を使用する。
vector、string は C++ 標準ライブラリのクラスで、それぞれ動的配列、文字列のクラスである。
各行の数字は ‘0’～’9′ で、空欄は ‘*’ で表す。
本稿最初の問題例は

{“135”, “5**”, “9397”, “*0*90”},
{“**3”, “**”, “*4**”, “****”, “2*45*”},
{“3*”, “**”, “***”, “*5”, “2*”, “**”, “4”}

と表現される。

加算ソルバー

空欄数がそう多くなければ（6個程度まで）、深さ優先探索で解を発見することができる。
以下、加算ソルバーのコードをボトムアップに解説して行く。

まずは文字列と数値が一致しているかどうかを判定する関数：isMatch(string, int) を以下のように定義しておく

bool isMatch(const string &t, int v)        //  計算結果(t) と v がマッチしているか？
{
    return atoi(t.c_str()) == v;        //  数値文字列を数値に変換し、比較
}

atoi(cchar*) は、引数の文字列を数値に変換するC/C++が標準で用意している関数だ。

本体が１行だけなので、わざわざ関数定義してコールせず直接書いてもよいのだが、
意味のある処理はできるだけ関数化しておいた方が、文書性・保守性が向上してよい。

次に、文字列配列 vector 型の変数に入っている式が加算として正しいかを
判定する関数：bool checkAdd(vector &vs) を次の様に定義する。

//      vs[0] + vs[1] + ...vs[vs.size() - 2] が vs[vs.size() - 1] と等しいかチェック
bool checkAdd(vector<string> &vs)
{
    assert( vs.size() >= 3 );
    int sum = 0;
    for (int i = 0; i != vs.size() - 1; ++i) {      //  vs[0] + vs[1] + ...vs[vs.size() - 2] を計算
        sum += atoi(vs[i].c_str());
    }
    return isMatch(vs.back(), sum); //  加算結果が会っているか？
}

以上で準備ができたので、いよいよソルバーを記述して行こう。
bool solveAdd(vector &vs, int row, int col) が実際に探索を行う関数で、
空欄に数字を順に入れつつ、自分自身を再帰的にコールする。
別の選択肢を先に試すのではなく、どんどん末端まで探索するので、深さ優先探索と呼ばれる。
すべての空欄に数字を入れ終わったら（探索している木の末端に達したら）、
先に実装した checkAdd() をコールして計算結果が正しいいかどうかをチェックする。
正しければ、解答を発見したということで、true を返しながら一番最初の呼び出し元まで戻る。

//  加算問題ソルバー
//      row行、col文字目の次から順に数字を決めていく
//      すべての空欄を埋めたら、式が成立しているかチェック
//      解はひとつだけという前提なので、解をひとつ発見したら探索終了
bool solveAdd(vector<string> &vs, int row, int col)
{
    for (;;) {
        auto ch = vs[row][++col];       //  次の桁に移動し、その文字を ch に
        if( ch == '*' ) {   //  '*'（空欄）を見つけたら 0～9 を入れて探索、ただし最上位桁に 0 は入れない
            for (ch = !col ? '1' : '0'; ch <= '9'; ++ch) {
                vs[row][col] = ch;
                if( solveAdd(vs, row, col) )    //  自分自身を再帰コール
                    return true;        //  解をひとつ発見したら終了
            }
            vs[row][col] = '*';     //  元に戻す
            return false;       //  解未発見
        }
        if( ch >= '0' && ch <= '9' ) continue;  //  数字が入っている部分はスキップ
        if( ch == '\0' ) {      //  行末に達した場合
            if( ++row != vs.size() ) {      //  まだ最後に達していない場合
                col = -1;
                continue;
            }
            //  全てが確定した場合
            return checkAdd(vs /*, true*/); //  加算が成立しているかチェック
        }
    }
}

下記の bool solveAdd(std::vector& vs) が実際に問題を解く時に呼び出す関数だ。
先の関数の引数にデフォルト値を指定し、共通化してもよかったのだが、
分けた方がわかりやすいと思ったので分けている。

//  加算問題ソルバー
bool solveAdd(std::vector<std::string>& vs)
{
    return solveAdd(vs, 0, -1);     //  最初の行・桁から探索開始
}

加算問題ソルバーを実際に使用する場合は、下記の様に、問題を文字列配列に設定しsolveAdd(vs1)をコールするだけだ。
解が見つかった場合は true を返すので、必要があれば if 文でチェックするとよい。
なお、printAddQuest(vs) はテキスト配列を加算問題として表示する関数で、
その定義は github を参照していただきたい。

    vector<string>vs = {"135", "5**", "9397", "*0*90"}; //  加算問題
    if( solveAdd(vs) ) {
        printAddQuest(vs);      //  解を表示
    } else {
        //  解けなかった旨表示
    }

筆者：津田伸秀 プロフィール：テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員（主席）。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。