虫食い算【第1回】


はじめに

今回から4回に渡り、「虫食い算」というパズルのソルバー・問題自動生成アルゴリズムについて解説する。
「虫食い算」とは数式が成立するように空欄を埋めるパズルで、詳しくは次の章で解説する。
「ソルバー」とはパズル問題を解くプログラムのことだ。
どうしても解けない問題があってイライラしたときにソルバーは救世主になるし、
問題を無尽蔵に解きたい人にとって問題自動生成プログラムは大いに役立つはずだ。
本稿のソースコード全体は以下にアップロードしているので、実行・修正などを行って試してみることができる。
https://github.com/vivisuke/Mushikuizan

筆者が虫食い算プログラムを開発してみようと思ったきっかけは、以下の書籍を読んだことだ。
数字の空欄が2万個もある問題を作った話など興味深い話がいろいろ載っているので、読んでみることをお勧めする。
参考文献:安福良直著「世界最大の虫食い算」https://www.amazon.co.jp/dp/4166606697/

虫食い算

虫食い算とは、「□2+3□=46」の様な数式の空欄に0~9の数字を入れて数式を完成させるパズルだ。
ただし、複数桁の最上位桁に0は入れてはいけない。
例えば、「□+1=□□」の場合、答えの2桁目は0は入らないので、9+1=10 が解となる。

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

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

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

以下に、加算、乗算、除算問題の例を示す。解けるかな?
虫食い算【第1回】

ソルバー

一般人向け虫食い算の探索空間は狭いので、全探索を行えば解を得ることができる。
最近のCPUであれば、探索する木の末端数が 10^6 程度であれば1秒未満で全探索することができる。
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++が標準で用意している関数だ。

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

次に、文字列配列 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 {
        //  解けなかった旨表示
    }

関連記事

虫食い算【第4回】

問題自動生成(承前) 除算問題自動生成 除算問題自動生成のアルゴリズムは乗算問題のそれと同じ流れだ。 ランダムに解答を生成し、できるだけ消去可能な数字を消去する。 数字を消去して、解が無い、または解が複数ある場合は消去不 […]
コメントなし

虫食い算【第3回】

承前 問題自動生成 一般的に、数独などの制約充足問題は、以下の手順で問題自動生成することができる。 1) 解をランダムに生成 2) 要素を消し解がユニーク(唯一)かどうかをチェック 3) 可能な限り 2) を繰り返す 可 […]
コメントなし

虫食い算【第2回】

ソルバー(承前) 乗算ソルバー 乗算問題も加算ソルバーと同じ様に空欄に ‘0’-‘9’ の数字を入れながら深さ優先探索を行えばよい。 乗算問題の場合は上図の様に空欄の数が多 […]
コメントなし

虫食い算【第1回】

はじめに 虫食い算 虫食い算とは、「□2+3□=46」の様な数式の空欄に0~9の数字を入れて数式を完成させるパズルだ。 ただし、複数桁の最上位桁に0は入れてはいけない。 例えば、「□+1=□□」の場合、答えの2桁目は0は […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP