SQL
2007年09月24日
SQLでお絵かきロジックを解く
SQLで数独を解くという記事に触発されてやってみました。
残念ながら全部SQLではできなかった。問題設定から得られる条件をSQLに変換するところでRubyの助けが必要なのが現状である。なんとかしたいんだけどなあ。ここらへんがSQLの知識不足なところである。
問題の方針としては Bool値をカラムに持つテーブルの升目文の直積を作って where に条件を書くというものである。
たとえば5x5の升目だとする。すると "SELECT * FROM boolean AS b_0_0 CROSS JOIN boolean AS b_0_1 CROSS JOIN ... CROSS JOIN booean AS b_4_4"が答になるべきものである。ちなみにこんなものを直接実行すると二度と帰ってこないのでやめましょう。で次は条件を書くわけだが…。
条件が2,1とあったら OOXXO OOXOX XOOXO の3通がある。たとえば一つ目をSQLで書くと "b_0_0.bool = true AND b_0_1.bool = true AND b_0_2.bool = false AND b_0_3.bool = false AND b_0_4 = true"となる。ちなみに booelanというのは "CREATE TABLE boolean (bool bool)"である。 3通をORで結び、各行についての条件をANDで結ぶ。これをwhereに書く。
が、この条件文を作るのはもちろん自動化する。これはどうやるかというと 0か4までの数列(seq)の入ったテーブルの条件個の直積を作る。で where に "seq1 + 個数 < seq2" をANDで結ぶ。 2,1 なら seq1 + 2 < seq2 AND seq2 + 1 <= 5 となる。そこからテーブルのwhereに変換するのはRubyで書いてしまった。ここが問題か。
結構遅い。8x8で1秒ぐらい。15x15だと帰ってきません。
苦労したのが適当に作ったらX軸とY軸がごっちゃになってしまったこと。きちんとやりましょう。それからもっと頭のいい方法を考えないと。
