こんなページを見つけてしまいました。ヒャッハー！

• Constraint Programming in Ruby

昔この手のプロダクトに一時期関わってたことがあって、離れてからも使いたいな〜というシチュエーションがたまにあったのだけど、手に入る処理系に手軽なのがなくて諦めてたんですよ。

最近覚えているのでは「8チームによるホーム＆アウェイのリーグ戦で、これこれこういう条件を満たす組み合わせが欲しい」というものでした。仕事が忙しかったし、解こうとするまえに友人何人かが人力（Excel表）で解いてしまったので忘れてましたが、そういうのです。

制約プログラミング(Constraint Programming)とは

どういうものかというと、このページの下に載っている例が簡単で分かりやすいかも。

次の等式を満たすx,y,zを求めよ

• x + y = z
• x = y - 3

ただし、x,y,zは0~9の整数。

変数が３つあって、等式が２つなので方程式を解くことによっては解は一意に決まらない。しかし、それぞれの変数は0-9の範囲内と決まっているので順番に試していけば探索で求めることができます。

x=0, y=0, z=0の場合

0 + 0 = 0 # OK
0 = 0 - 3 # NG!

x=0, y=0, z=1の場合

0 + 0 = 1 # NG!

:

x=0, y=3, z=3の場合

0 + 3 = 3 # OK
3 = 3 - 3 # OK

順番に探していけば運が良ければそこそこ早く、運が悪くても可能性を全部試せば解が存在するか否かは分かります。

制約プログラミングはこの探索を効率的に行うことができます。あらかじめ制約を式としてシステムに与えておいて、ひとつの変数を決めるたびに制約式から他の変数の可能性を能動的に削っていき、探索空間を狭めたり速く失敗させたりすることによって探索を速く行います。

例えば、こんな制約プログラミング環境があったとしたらステキな気がします。

Gecode/R

Gecode/Rは制約プログラミング環境GecodeのRubyのためのインターフェースです。Gecodeは汎用的な環境ではありますが、デフォルトの言語インターフェースはC++ですので、いささか取っつきにくいです。

Gecode/Rで先ほどの問題を解くプログラムは下記のように書けます。 ＃WEBページそのものですが

少々冗長にはなりますが、架空のステキなプログラミング環境に近い感じでイイ！ヽ(´ー｀)ノ

さてここで問題。上記のように動くはずなのですが、このプログラムをコピペして実行すると

NoMethodError: undefined method `to_i' for :==:Symbol
    from /Users/iwazawa/.rvm/gems/ruby-1.9.3-p327/gems/gecoder-with-gecode-1.1.0/lib/gecoder/interface/constraints/int_var_constraints.rb:137:in `block in singletonclass'

と言って落ちる orz

諦めるのは非常に残念なので、がんばって追いかけることにします！が今日はここまで。

というわけで連載の予定