2010-05-08[n年前へ]
■Rubyで数独ソルバを書く(が、動かない…)
数独で見るRuby(と Mathematica)のパワーと表現力を参考に、Rubyで数独ソルバを書いたのですが、まともに動作してくれません…。もちろん、「書いた通りに動作している」わけですから、書き方が悪いわけですが、どうにもこうにも上手く書くことができません。そこで、Rubyコードをここに貼り付け、とりあえず「わかる」ようになるまで、放置しておこうと思います。
require 'pp' class Array def replaceAtXY x,y,v a=self.dup;a[y][x]=v;a; end end def search b (!b.flatten.include?(0)&&!pp(b)&&exit)||(deepen b) end def deepen b l=b.flatten.index 0; x=l%9; y=(l/9).floor candidates(b,x,y).each{|v| search b.replaceAtXY(x,y,v) } end def candidates b,x,y cand=Range.new(1,9).to_a ym=3*(y/3).round;xm=3*(x/3).round; (ym..ym+2).each {|i| (xm..xm+2).each {|j| cand.delete b[i][j]} } b[y].each{|v| cand.delete v} # (0..8).each {|i| cand.delete b[i][x] } cand end
search [[0,0,0,0,0,7,0,9,0], [0,3,0,0,2,0,0,0,8], [0,0,9,6,0,0,5,0,0], [0,0,5,3,0,0,9,0,0], [0,1,0,0,8,0,0,0,2], [6,0,0,0,0,4,0,0,0], [3,0,0,0,0,0,0,1,0], [0,4,0,0,0,0,0,0,7], [0,0,7,0,0,0,3,0,0]]
[[1, 2, 4, 5, 8, 7, 6, 9, 3], [5, 3, 6, 1, 2, 9, 7, 4, 8], [7, 8, 9, 6, 3, 4, 5, 1, 2], [2, 4, 5, 3, 1, 6, 9, 7, 8], [3, 1, 7, 5, 8, 9, 4, 6, 2], [6, 8, 9, 2, 7, 4, 1, 3, 5], [3, 2, 5, 4, 6, 7, 8, 1, 9], [1, 4, 6, 3, 9, 9, 5, 2, 7], [8, 9, 7, 1, 2, 5, 3, 4, 6]]