N-queens問題の制約プログラミングでの解き方

N-queens問題(エイトクイーンズ問題) - 毛の生えたようなもの

トラックバック先のエントリーとは直接関係ないのですが、読んでいて色々思い出したので書きたくなった。

あらかじめ言っておきますが動くものはありません（汗）
「一夜漬け文章教室」宮部 修著 の言う、ダメな傾向の文章であるところの
そのものな書き出しで始まってしまいましたが、あまりにもうろ覚えで書くもので、防衛戦を張らずにはいられない（笑）

社会人になって２年目くらいだろうか、当時勤めていた会社で制約論理型言語というものを扱っていた事があり、N-Queen問題が、このプログラムの練習課題として必ず使われたのを思い出す。

制約論理型言語は、問題の解き方（アルゴリズム）を記述するのではなく、解に求められる制約を静的、宣言的に記述して、コンピュータに探索させて解を求めるというもの。

Wikipediaの制約プログラミング説明、がなかなかいいな。

Rubyを使って擬似的に書くとすると次のようなイメージか。 require 'constraint' num = ARGV[0].to_i # ConstVar.new(0, num-1)は0..num-1の値を取り得る制約変数の生成で行を表す # 配列の要素nを列とみなしn=0の時の格納されている制約変数が0に決まれば、 # チェス盤の(0, 0)にクイーンがあるとする # このモデルで同じ列に置けないという制約が自動的に掛かることになる ans = Array.new(num) do |n| ConstVar.new(0, num-1) end # 制約領域の生成 constraint = Constraint.new # 全ての制約変数は違う値を取らなければならないという制約 # これで同じ行に置けないという制約になる constraint.defferent(ans) # 斜めもダメという制約（ここ、もうちょっと上手くかけなかったか？…） (0..num-1).each do |r1| (0..num-1).each do |r2| constraint.notIn(constraint.sub(ans[r1], ans[r2]), [r1 - r2, r2 - r1]) unless r1 == r2 end end # 解の探索 constraint.solve # 結果の出力 (0..num-1).each do |row| (0..num-1).each do |col| if row == ans[col] print 'Q ' else print ' ' end end puts end ここではConstraintという制約プログラミングのためのライブラリが用意されていると仮定。
このクラスライブラリはConstVarというクラスのインスタンスが制約変数を表し、制約の記述はConstraintインスタンスのメソッドで行うとします。

だめだなぁ、すっかり忘れてしまった。斜めに置けないという制約、もっとエレガントに書けた気がするのだが。おかげでこのエントリーを書くのに、あぁでもない、こうでもないと紙に格子を描きなぐって考え込んでしまったが、自信がない。情けない（死）

でも書いているうちにムクムクと実装したくなってきた。
ConstVarとConstraintを実装するプロトタイプをRubyで書いて、動くようになったらCで書き直して高速化とかだな。ついカっとなってみるテストに最適。

Rubyにはirbがあるので、制約プログラミング処理系を組み込むホスト言語として、かなり使いやすい気がする。