ホームページ目次前の話次の話

プログラムを書かずにパズルが解ける「制約プログラミング」

2008年6月28日

暇でも、暇でなくても、パズルプログラミングはやるわけだが、 今年はどうしたかことが、この3ヶ月の間、パズルプログラミングがまったく出来なかった。 野暮用がやたらに出来てしまったからであるが、3ヶ月もの間自分でプログラムを思われるもの (自分で納得していないプログラムは何万行書こうとも関係ないので計算には入れない!)を 書かなかったので、プログラムをかなり忘れた気がする。

おかげで、プログラミングの能力が落ちたに違いない。 それに、肩や指の体力も落ちてくるし、頭も働かなくなる。 それに、そろそろ、パズルを觧く解法テクニックを考えるのも面倒になってくるではないか。

考えてみるに、今迄のパズルプログラミングは、自分の頭で解法テクニックを考えて、 それをプログラムしていただけに過ぎない。要するに、コンピュータは何も考えず、 人間様が必死で考え、必死でプログラムしたのを、コンピュータは粛々と処理していたに過ぎない。

古くは人工知能、最近は知識工学、知能工学、などという言葉がある。 いかにもコンピュータが考えてくれているように思えるが、現実には考える部分は人間が全て 行っていたのである。これでは、はっきりいって詐欺である。

そろそろ、パズルならルールだけ、問題だけを記述すれば、後は全部やってくれるものが欲しい。 どうやれば解けるかの解法テクニックなどは一切教えずとも、ちゃんと解いてくれなければ 人工知能ではなくて、人工無能でしかないはずだ。

そういうものは既にできていないだろうか、そろそろそういう勉強も初めておかないとと思って ネットを漁ってみたら、やはりちゃんと出てきました。 パズルのようなものは、だいたいがなんらかの制約条件があって、それを満足(充足)させる 解を見つけることにある。パズルでなくても、現実社会でもそういう問題に帰着できることは 少なからずあるのだが、面倒なのと興味がないので、ここでは一切省略しよう。

さて、もっと具体的な書こう。SEND+MORE=MONEY という覆面算を知っているだろうか。 知っていなければ、どこかで調べるように。

この問題を、

  1. SENDとMOREは4桁で、4桁の2つの数を足した5桁のMONEYの最上位のMは1になる。
  2. Mが1だから、MOREは1000台なのだから、SENDの最初のSは、7以下では足した結果が5桁になるには、 8か9でなければならない。
  3. ...
という風にしながら解いていくのはボケ防止には良いかも知れぬが面倒だ。 創造的でなく、とてもやってられない。

これを、

;            S E N D
;          + M O R E
;        ------------
;          M O N E Y
;
(int S 1 9)
(int E 0 9)
(int N 0 9)
(int D 0 9)
(int M 1 9)
(int O 0 9)
(int R 0 9)
(int Y 0 9)
(alldifferent S E N D M O R Y)
(int SEND 1000 9999)
(int MORE 1000 9999)
(int MONEY 10000 99999)
(= SEND (+ (* (+ (* (+ (* S 10) E) 10) N) 10) D) )
(= MORE (+ (* (+ (* (+ (* M 10) O) 10) R) 10) E) )
(= MONEY (+ (* (+ (* (+ (* (+ (* M 10) O) 10) N) 10) E) 10) Y) )
(= (+ SEND MORE) MONEY)
のように書くだけで解けないだろうかという訳である。 もちろん、この書き方はまだ改良の余地があるが、とりあえず脳味噌を使わずに単純作業としてできる。

これ、"sendmoremoney.cps" というファイルにしておいて、 以下のように、sugarというソフト(頑張らなくても良いという甘い考え方のソフト)を用いると、 不思議なことに、変数の値が決まってしまう。

sugar sendmoremoney.cps
s SATISFIABLE
a S     9
a E     5
a N     6
a D     7
a M     1
a O     0
a R     8
a Y     2
a SEND  9567
a MORE  1085
a MONEY 10652
a

SEND+ MORE = MONEY 程度しか出来ないのだったらつまらないのだが、 実は数々のパズルを解くことができるようなのだ。

パズルをSugar制約ソルバーで解く

パズルを解くのは、制約を書き並べるだけという作業になるのだが、 パズルによっては、この書き並べる作業自体が何だか新たなパズルになっているような気がするが、 それはそれで楽しいではないか。

O'Reilly Japan刊

3/14発売
増刷:第3刷決定♪

オープンソース
Scheme言語処理系
Gaucheの愛好者団体

詳細はブログで


ホームページ目次前の話次の話