最近、心持ちに余裕ができてきたのと、仕事でプログラムを書いていることがあり、さらに、知り合いが数独をやっているというのを聞いたので、なんとなく書いてみた。
rubyでやってみたら案外あっさりできて、入出力は最低限にして、解く部分だけで80行くらい。
工夫した点は、いきなり上から数字を全通り試さずに、
1.自明なマスはすべて埋めてから。
2.2択になっているところから順に総当たり。
という点。
総当たりで、解けなかったら置いたところまで戻る、、というのはやっぱり再帰で書くのが簡単なので、そうした。
#!/usr/bin/env ruby require 'yaml' Q=YAML.load_file("quiz.yaml") class Sudoku def initialize(a=Q[0],flag_one=true) @quiz=a.map{|arr|arr.freeze}.freeze @ans=copy(@quiz) @flag_one=flag_one @store=[] self.solve end def solve rec unless solved? @store rescue => err p err,@ans end def solved? (0..8).each{|i|(0..8).each{|j| return false if @ans[i][j]==0 }} return true end private # 行、列からブロックへ変換。逆変換も同じ。 def ij2kl(i,j) k=j/3 + (i/3)*3 l=j%3 + (i%3)*3 return k,l end # メインの再帰関数。 def rec(i=0,j=-1, thr=0) while true raise "unsolvable!" if thr > 9 if j==8 thr+=1 if i==8 i=(i+1)%9 end j=(j+1)%9 next unless @ans[i][j]==0 # ここからi,jマスの処理。 arr=hantei(i,j) case arr.length when 0 then # 解けない! return nil when 1 then @ans[i][j]=arr[0] if solved? p "solved!",@ans @store.push(copy(@ans)) return true else thr = 0 end # 候補が複数残ったところから再帰。 when 2..thr then wk=copy(@ans) arr.each{|v| @ans[i][j]=v rec(i,j) return nil if @flag_one && solved? @ans=copy(wk) } break # 仮定したところを全部試したら無限ループを抜ける。 end end end # i,j マスが決まるかどうかを判定 def hantei(i,j) k,l=ij2kl(i,j) tmp = @ans[i][0..8] (0..8).each{|ii| ki,kj=ij2kl(k,ii) tmp << @ans[ii][j] tmp << @ans[ki][kj] } [1,2,3,4,5,6,7,8,9] - tmp.uniq end def copy(a) Marshal.load(Marshal.dump(a)) end end Sudoku.new(Q[0])
http://apollon.issp.u-tokyo.ac.jp/~watanabe/sample/sudoku/index_j.html
ここで公開されている数独を食わせてみたら、ちょっと止めたくなるくらい時間がかかったので、いろいろと小細工してみたけども、かえって遅くなるばかりだった。。。
次は練習に、pythonとかocamlとかで書いてみようかな。