前回まででなんとか制約プログラミングで実験できるところまでこぎ着けたので公式サイトのExamplesをやっていきたいと思います。

send+more=money

有名な論理パズルです。

   send
 + more
 ------
  money

与えられたこの式は、ひとつのアルファベットがひとつの数字に割り当てられます。別のアルファベットが同じ数字になってはいけません。単語の最初の文字は0以外でなければいけません（つまりsとmは0以外）。これらの制約を満たす数字を探す問題です。

制約を分かりやすくリストにすると

1. 0 <= s,e,n,d,m,o,r,y <= 9 の整数
2. s,e,n,d,m,o,r,yは全て違う数字
3. s != 0
4. m != 0
5. (s*1000+e*100+n*10+d) + (m*1000+o*100+r*10+e) = (m*10000+o*1000+n*100+e*10+y)

となります。

プログラム例

サンプルプログラムを見てみましょう。

サイトのコードではequation_rowがGecode.solveのブロック内に定義されていますが、最後の検算にも使いたかったのでトップレベルに出してあります。（Rubyの楽なとこですねduck typing！）

実行

制約を考えないと8変数でそれぞれが10の値を取り得るので単純計算すると10**10で10000000000通りになるんでしょうか。どのくらい実行時間はかかるのでしょう。早速実行してみます。

$ time ruby send-more-money.rb 
s e n d m o r y
9 5 6 7 1 0 8 2
send + more = 10652
money = 10652

real    0m0.392s
user    0m0.096s
sys 0m0.031s

あっさりと約0.4sで解が求まりました。いいですね！

仕事も始まったので今日からは少し短めでこの辺にしておきます。

次回はこのsend+more=moneyプログラムの細部を解説していきたいと思います。