はじめに
みなさん、中学生？の頃に算数パズルに夢中になったことはありませんでしょうか？ 最近、算数パズルの一つである覆面算が、ルールエンジンを利用して解くことができて、 人が解答を見つける方法と似ていて面白かったので、記事にしてみました。
覆面算とは
みなさまは、覆面算（ふくめんざん、Verbal arithmetic）をご存知でしょうか？覆面算は算数パズルの一種です。
問題としてアルファベット等の文字を含んだ計算式が与えられます。 各文字に0から9の数字を割り当てて計算式を満足する文字と数字の組み合わせを答えるものです。 数字の割り当てには、制約があり、次のようなものです。
-
制約#1 : 同じ文字には同じ数字を割り当てる
-
制約#2 : 違う文字には違う数字を割り当てる
-
制約#3 : 最上位の桁には、数字の0を割り当てていけない
覆面算の例として有名な問題は、以下があります。 SEND + MORE = MONEY (=もっとお金を送ってくれ!)
計算式 : SEND + MORE = MONEY
解答: M=1、S=9、O=0、E=5、N=6、D=7、R=8、N=6、Y=2、9567 + 1085 = 10652
人が解答を見つける
さて、人が覆面算の解答をどのような手順を見つけるのでしょうか？前で記述した SEND+MORE=MONEY の 覆面算を見つける思考をたどってみます。
人が解答をみつける手順（一部）
- 4桁同士の足し合わせて5桁になっている。制約#3より最上位は0でない。5桁になるために は、4桁から5桁へ繰り上がりしていることがわかり、MONEY の M は 1 となる。
- M=1がわかったので、制約#2から MORE の M も同様に 1 になる。
- 4桁から5桁へ繰り上がりをしているため、、S=8またはS=9となる。
- S=8とすると、3桁から4桁への繰り上がりしている必要があり、M=1であるため、MONEY の O=0(ゼロ)になる。MOREのOも0(ゼロ)になる(制約#2)ために、3桁から4桁への繰り上がりがなく、 S=9しかない。
- ...
人が解答をみつける手順(一般化)
- 数の加減乗除の性質から文字と数字の組み合わせを絞り込む
- 絞り込んだ中でしらみつぶしに検証して、文字と数字の組み合わせを決定する
- 決定した文字と数字の組み合わせを前提に、次の文字と数字の組み合わせを検討
- 答えがもとまるまで、1-3を繰り返す。
コンピューターで解答を見つける
コンピュータで回答を見つけるためには、いくつかの方法があります。
- 力まかせ探索（英字と数の組み合わせを全検索する）
- ルールエンジンを使う（規則をルール化してパターンマッチング）
ここでは、「はじめに」で説明したように、ルールエンジンを利用して、 問題を解いていきます。
ルールエンジンとは
ルールエンジンとは、与えられた情報とルールをもとに、判定や計算を実行する仕組みのことです。 個々のルールをもとに、仕組みを作成することで、再利用性やメンテナンス性を高めることを目的にしています。
ビジネス領域でもカードの発行基準の自動判定、複雑な料金計算、入居審査契約の審査基準等のなどでルールエンジンを 適用することがあるそうです。ルールの組み合わせでアプリケーションが構築できれば、メンテナンス性を高めることができそうです。
ルールエンジンは、80年代の第二次AIブームで研究されたエキスパートシステムを構成する推論エンジン・知識ベースのそのものであり、 歴史を感じさせます。今回のパズルのようにルール化が容易な対象については、解法までの手順を明示するよりは、簡単コードは書けます。
ルールエンジンの仕組み
ルールエンジンには、ルールと呼ばれる知識、知識を適用するためのデータ(ファクトという)、 データとルールがマッチングした実行候補が入るアジェンダがあります。
ルールエンジンは、ルールとファクトはマッチングを繰り返して、アジェンダにマッチング結果を追加します。 マッチング結果をもとに、ファクトが追加され、追加されたファクトをもとに、さらにマッチングが実行されます。
CLIPSの説明
CLIPS(C Language Integrated Production System)は、エキスパートシステム・ツールであり、 最近のルールエンジンとは異なり、LISP(List Processor)の様な"かっこ"を使い、ファクトとルールを記述します。
CLIPSの実行環境の作成
実行環境を作成するためには、github のソース（https://github.com/noxdafox/clips )をもとにコンパイルをします。
$ git clone https://github.com/noxdafox/clips
$ cd clips/core
$ make
$ ./clips
CLIPS (Cypher Beta 8/21/18)
CLIPS> (exit)
覆面算のコードと実行結果
覆面算を解く、CLIPSのコードを以下で示します。 ザクっと解説をすると、以下の通りになります。
-
(defrule startup ...) の中にある (assert ... ) がファクトを追加している部分です。 number という数字の候補と、letter という 覆面算で利用されている文字をファクトとして追加しています。
-
(defrule generate-combinations ...) では、ファクトから 数字 と 文字 を取り出して、 新しい ファクト (combination 数字 文字) を追加します。
-
(defrule find-solution ....) では、oファクト (combination 数字 文字) が 覆面算のルールを満足することを確認しています。 覆面算の計算が合致した場合は、結果を出力しています。
; 開始する (defrule startup => (printout t crlf "The problem is" crlf crlf) (printout t " SEND" crlf) (printout t " + MORE" crlf) (printout t " ------" crlf) (printout t " = MONEY" crlf crlf) (assert (number 0) (number 1) (number 2) (number 3) (number 4) (number 5) (number 6) (number 7) (number 8) (number 9) (letter D) (letter E) (letter Y) (letter N) (letter R) (letter O) (letter S) (letter M))) ; 候補を生成する (defrule generate-combinations (number ?x) (letter ?a) => (assert (combination ?a ?x))) ; 候補が条件を満足することを確認する (defrule find-solution (combination D ?d) (combination E ?e&~?d) (combination Y ?y&~?d&~?e) (test (= (mod (+ ?d ?e) 10) ?y)) (combination N ?n&~?d&~?e&~?y) (combination R ?r&~?d&~?e&~?y&~?n) (test (= (mod (+ ?d ?e (* 10 ?n) (* 10 ?r)) 100) (+ (* 10 ?e) ?y))) (combination O ?o&~?d&~?e&~?y&~?n&~?r) (test (= (mod (+ ?d ?e (* 10 ?n) (* 10 ?r) (* 100 ?e) (* 100 ?o)) 1000) (+ (* 100 ?n) (* 10 ?e) ?y))) (combination S ?s&~?d&~?e&~?y&~?n&~?r&~?o) (combination M ?m&~?d&~?e&~?y&~?n&~?r&~?o&~?s&~0) (test (= (+ ?d ?e (* 10 ?n) (* 10 ?r) (* 100 ?e) (* 100 ?o) (* 1000 ?s) (* 1000 ?m)) (+ (* 10000 ?m) (* 1000 ?o) (* 100 ?n) (* 10 ?e) ?y))) => (printout t "A Solution is:" crlf crlf) (printout t " S = " ?s crlf) (printout t " E = " ?e crlf) (printout t " N = " ?n crlf) (printout t " D = " ?d crlf) (printout t " M = " ?m crlf) (printout t " O = " ?o crlf) (printout t " R = " ?r crlf) (printout t " Y = " ?y crlf) (printout t crlf) (printout t " " ?s ?e ?n ?d crlf) (printout t " + " ?m ?o ?r ?e crlf) (printout t " " "------" crlf) (printout t " = " ?m ?o ?n ?e ?y crlf crlf))$ ./clips CLIPS> (load "sample/send-more-money.clp") CLIPS> (run) The problem is SEND + MORE ------ = MONEY A Solution is: S = 9 E = 5 N = 6 D = 7 M = 1 O = 0 R = 8 Y = 2 9567 + 1085 ------ = 10652
終わりに
以下、感じたことは以下の通りです。
- 人間がパズルを解くときの、与えられた情報とルールから、適用しやすいルールをマッチングするのは、ルールエンジンにおけるコードと似ている。
- 解決手順をコード化するのではなく、ルールをコード化する考え方は面白い。
- 適用に適した領域もあり、知っておくのも有効
参考情報
本家ホームページ http://www.clipsrules.net/
ソースコード https://github.com/noxdafox/clips
How to build an Expert System with CLIPS https://blog.learningdollars.com/2020/04/26/how-to-build-an-expert-system-with-clips/
Wikipedia https://ja.wikipedia.org/wiki/CLIPS