GecodeでC++と制約プログラミング(1)

ガウディ本を読んだのでOz以外の言語で制約プログラミングをやってみたくなりました。

すると、(私的には)意外なことにC++Javaでもライブラリとして提供しているものがあるようです。いつものごとくですが、情報元はWikipedia

その中でも一番使うだけなら気楽にできそうなMITライセンスのGecodeというものを選んでみました。(他にとくに理由というものはありません)。

まだインストールしたばかりで使い方はさっぱりですが、まずは制約プログラミングのサンプルとしてよく題材にされるSend-More-Money(日本語では覆面算というようです)のサンプルプログラムがあるのでそれをビルドして、実行してみました。コードとしてはこのページの"send-more-money.cpp"を参照してください。

ちなみに知っている人も多いかもしれませんが、「Send-More-Money」とはアルファベットにそれぞれ0〜9の数字をあてはめて「send + more = money」の計算が成り立つようにアルファベットに数字を入れるゲームです。
これにはルールがあって、まず別のアルファベット同士が同じ値を持つことはできず、また先頭の文字s,mは0でないというものです。

サンプルプログラムでは(おそらくですが)、s,e,n,d,m,o,r,yが0〜9の値であること、s, m が0でないこと、全てのアルファベットにおいて数字がバラバラであること、そして「send + more = money」が成り立つことが制約されています。(最後に探索木(の分岐)の形を決定しているようです)

結果としては

{9, 5, 6, 7, 1, 0, 8, 2}


のようになります。{s,e,n,d,m,o,r,y}に対応する数字が並んでいます。
計算してみると「send + more = money」(9567 + 1085 = 10652)となっており、確かに制約プログラミングで答えが導けているようです。

どのように使うかはこれから勉強していくつもりですが、おそらくただ単に制約プログラミングをしたいだけならPrologを使った方がいいと思います(きっと文法的に分かりやすい)。

広告を非表示にする