数独(Sudoku)ソルバ
Sudoku - Wikipedia, the free encyclopedia
数独といえば知らない人はおそらくいない大人気パズルですが,
そういえばソルバを書いたことがないなと思い立ちまして,Rubyで書いてみました.
いろいろと怪しいところはありますが,自分で考えて書いてみるのは楽しいです.
基本的には,9x9マスの数字列を書いたテキストファイルを入力として,
(0は未確定のマス)
530070000 600195000 098000060 800060003 400803001 700020006 060000280 000419005 000080079
解けた後の9x9マスの数字をコンソールに出力するというものです.
534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
以下,Githubに置いたソースのコピペです.
http://github.com/glass5er/sudoku-solver
solver.rb
#!/usr/bin/env ruby # -- N for stage size # -- only N = 3 available currently : 9x9 sudoku N = 3 STAGE_WH = N ** 2 BLOCK_WH = N # -- exception classes class InvalidInputFormatException < Exception; end class NumNotFoundException < Exception; end class Block attr_reader :value attr_reader :cands def initialize(val = 0) @value = val @cands = (1..STAGE_WH).to_a @cands = [val] if val > 0 end def update() raise NumNotFoundException if @cands.size <= 0 && @value <= 0 flag = false if @cands.size == 1 then @value = @cands[0] flag = true end return @value, flag end def exclude(n) @cands.delete(n) #update() end end class Stage def initialize(filename="") @rows = STAGE_WH @cols = STAGE_WH @field = Array.new(@rows) @rows.times {|y| @field[y] = Array.new(@cols) } begin read(filename) rescue InvalidInputFormatException => e # -- InvalidInputFormatException : add error message raise e, "Input txt file should be #{STAGE_WH}x#{STAGE_WH} matrix format." # -- FileNotFoundException : send to default error handler end end def read(filename) File.open(filename) {|f| y = 0 while line = f.gets do x = 0 line.chomp.chars { |c| @field[y][x] = Block.new(c.to_i) x += 1 } raise InvalidInputFormatException if x != STAGE_WH y += 1 break if y >= STAGE_WH end } end def solve() begin updated = false @rows.times {|y| @cols.times {|x| # -- n = @field[y][x].value # -- flag = @field[y][x].updted? n, flag = @field[y][x].update() if flag then # -- exclude n from candidate # -- h-line, v-line @rows.times {|cy| @field[cy][x].exclude(n) } @cols.times {|cx| @field[y][cx].exclude(n) } # -- square-block area_x = x / BLOCK_WH area_y = y / BLOCK_WH BLOCK_WH.times {|ay| BLOCK_WH.times {|ax| @field[area_y * BLOCK_WH + ay][area_x * BLOCK_WH + ax].exclude(n) } } updated = true else puts "(#{y},#{x}) => #{n} : #{@field[y][x].cands}" if $DEBUG end } } end while updated # -- can finish anyway when impossible questions return check() end def check() @rows.times {|y| @cols.times {|x| # -- simple check (not perfect...) return false if @field[y][x].value == 0 } } true end def to_s() str = "" @rows.times {|y| @cols.times {|x| str += @field[y][x].value.to_s } str += "\n" } str end end
main.rb
#!/usr/bin/env ruby require "./solver.rb" def test() hoge = Block.new(3) p hoge.value p hoge.cands fuga = Block.new(0) p fuga.value p fuga.cands fuga.setValue(4) p fuga.value p fuga.cands # -- @DEBUG : shoud raise exception #fuga.setValue(5) #p fuga.value #p fuga.cands stage = Stage.new("./dataset/question001.txt") print stage end if __FILE__ == $0 stage = Stage.new(ARGV[0]) puts "Question is :" if $DEBUG puts stage if $DEBUG solved = stage.solve puts (solved ? "Answer is :" : "Not solved ... :") if $DEBUG print stage end