hirax.net::inside out::2010年05月08日

■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]]