Rubyで数独を解く

動機

この記事に触発されて、数独のソルバーを作ってみました。自分はpythonよりもRubyに慣れているので、Rubyで実装してみました。

実装の方針

参考にした記事を元に、再帰を使った深さ優先探索で解を求めるソルバーとして、実装しました。マス目に入れる数字が適切かどうかをチェックするメソッドについては、元の記事のものとほとんど同じものを使用しております。

コード

追記：いただいたコメントをもとに、コードをすっきりさせました。コメントして頂いた方、ありがとうございます。

sudoku.rb

#!/usr/bin/env ruby

class Solver
  def initialize values
    @values = values
  end

  def show
    @values.each_with_index do |row, i|
      puts row.each_slice(3).map{|a| a.join(" ")}.join("|")
      puts "-----+-----+-----" if [2,5].include?(i)
    end
  end

  def solve(x=0,y=0)
    return true if y > 8
    if @values[y][x] != 0 then
      return (x > 8) ? solve(0,y+1) : solve(x+1,y)
    else # 値が決まっていない場合
      for i in 1..9
        next unless check(x,y,i)
        @values[y][x] = i
        retval = (x > 8) ? solve(0, y+1) : solve(x+1, y)
        return true if retval
        @values[y][x] = 0
      end
      false
    end
  end

  def check( x, y, i)
    row(y, i) and column(x, i) and block(x, y, i)
  end

  def row( y, i)
    ! @values[y].include?(i)
  end

  def column( x, i)
    ! @values.map{|row| row[x]}.include?(i)
  end

  def block( x, y, i)
    xbase = (x/3)*3
    ybase = (y/3)*3
    block_values = @values[ybase,3].map{|row| row[xbase,3]}.flatten
    ! block_values.include?(i)
  end
end

def values_from_grid
  filename = "grid.txt"

  File.foreach(filename).
    map {|line| line.scan(/[.0-9]/).map(&:to_i)}. #scanで、指定した文字を取り出してArray化。mapでintegerに変換
    select {|row| row.size == 9} #selectで、数字が9つ格納されているArrayのみ取り出す
end

grid_value = values_from_grid
solver = Solver.new grid_value
solver.show
solver.solve
puts "" # 見やすくするため
solver.show

grid.txt

8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .