2003年10月1日更新

　Alphametic と言うパズルがあります。これは，数字に文字を当てはめ，その文字を使った計算式から，その数字を当てると言うパズルです。例えば，

を満たす，０～９の数字を S，E，N，D，M，O，R，Yに当てはめ，式が成立するようにするものです。ここで，違う文字には違う数字，数の先頭（今の場合，S，M）はゼロでないものとします。

　上の問題は，H. E. Dudeney が 1924年に発表した古典的な覆面算で，解は１通りしかありません。

　似たような問題は数多く知られていて，日本語のものも数多くあります。Alphametic は Cryptarithmetic とも言われ，日本語的に翻訳すると「いろは算」と言った感じです。このAlphametic は基本的に意味を持つ言葉を使います。これに対して，空白文字などを使って，表すパズルもあります。日本では虫食い算と言われています。例えば，

が成り立つように四角に数字を当てはめるといったものです。（この問題は簡単に解けます。）この問題は，掛け算ですが，この種理類の問題は，割り算に興味深い問題があり，割り算についてのこのようなものは，Skelton Division と呼ばれています。

　この虫食い算や Alphametic を総称して覆面算と言うこともあります。

　パズルをコンピュータを使って解くのはある意味でルール違反ですが，プログラム勉強するものにとって，プログラムで解いてみようと言う誘惑にかられます。しかし，パズルの解答を求めるプログラムを作るのは簡単なことではありません。

　しかし，覆面算である種のもの特に Alphametic は，計算機を使って強引に解くことも可能なものです。解く方法は

という極めて単純なものです。この解き方ではパズルを解く楽しみは全くありませんが，プログラムを作る側からすると，取り尽くす効率を工夫する楽しみがあります。一般に面白い問題は，素朴にすべての場合を検査すると，膨大な場合数になり，高速な計算機を使っても瞬時に答えが出るというものではありません。

　最初に挙げた，Dudeneyの問題の場合，使う文字数は８個で，使う数の種類は１０種類（０～９）ありますから，これらのすべての場合の数は，

10*9*8*7*6*5*4*3=1814400

種類あります。このくらいの場合の数は，現在の計算機の能力からすると十分処理可能な個数ですが，どのくらい時間がかかるかはそのプログラムの作り方に依存する微妙な数です。

　現在，普通の計算機での Tiny Basic の計算能力からすると，For 文での100万回の繰り返し計算が約１秒で可能です。ですから，１回の検査にどの程度の計算ステップが必要かによってその時間が大きく異なります。

　今の問題は順列を効率的に列挙するという問題に帰着されます。これについては順列の列挙で考えました。それを使って実際に解を求めるためのプログラムFukumen.tbtを作りました。このプログラムは問題の設定をプログラムに実際に書き込むもので，多少慎重に書かなければいけませんが，そこを注意すれば，基本的に Alphametic  はすべて解けます。

　以下その設定の仕方を，２つの例で説明します。

　最初に次の問題を考えます。

の四角の中に１から９までの数字を１つづつ入れて等式を成立させるようにする。

　９個の数字を使って上の等式が成立するようにするのですから，１～９の順列をすべて生成しそれを検査します。検査するために，箱に配列 T(1) ～ T(9) を割り振ります。つまり，

とします。この等式の成立・不成立を検査するための関数 IsTrue(T()) を使います。分数式は計算誤差が出る可能性があるため，この式を，整数式に書き換えます。それは両辺の分母を払うだけです。上の式の分母をそれぞれ，a，b，c とすると，

と表されますから，上の式は

T(1)*b*c + T(4)*a*c + T(7)*a*b = a*b*c

となります。この式を使って，IsTrue(T())を書くと，

となります。このほか，使う文字の個数を（今の場合９個）を

と設定し，０を使わないことを示すために，

と設定します。このようにしてプログラムを動かすと，数十秒後（計算機の能力に依存します）に６種類の解が表示されます。これらの解は分数の順序を入れ替えたもののみで，

実質的にはただ１つの解が得られます。

次に，

を解きましょう。S，E，N，D，M，O，R，E，Y にそれぞれ，T(1)～T(8) を割り当てます。このようにすると，IsTrue(T())は

となります。このほか，使う文字の個数を（今の場合８個）を

と設定し，０を使うことを示すために，

と設定します。このようにしてプログラムを動かすと，１，２分後（計算機の能力に依存します）に２５種類の解が表示されます。これらの解はT(5)=M=0の解が，２４個含まれていて，M ≠0 の解は，残りで，

ただ１つの解が得られます。

　どのようなAlphametic の問題でも，上のように IsTrue(T()) を設定すれば，数分以内にすべての解を求めることができます。このように解を求まってしまうと，パズルとして興味は少し少なくはなりますが，解法の載っていない解答作成プログラムと思って利用すれば，意味はあるかも知れません。

　Fukumen.tbt はここにあります。