solve sudoku

sudoku.rb

class Sudoku
  attr_accessor :table

  def initialize(table)
    @n, @k = 9, 3 # n=k^2
    @table = table
  end
  
  def solve
    def ok(i, x) # 場所iに数字xを置けるか
      r, c = i / @n, i % @n
      return false if @table[(r * @n)...((r + 1) * @n)].include?(x) # 行
      return false if (0...@n).select { |_r| @table[_r * @n + c] == x }.size > 0 # 列
      ((r / @k * @k)...((r / @k + 1) * @k)).each do |_r|
        ((c / @k * @k)...((c / @k + 1) * @k)).each do |_c|
          return false if @table[_r * @n + _c] == x # ブロック
        end
      end
      return true
    end

    def dfs(i)
      return true if i == @n * @n
      return dfs(i + 1) if @table[i] > 0
      (1..@n).each do |x|
        if ok(i, x)
          @table[i] = x
          return true if dfs(i + 1)
          @table[i] = 0
        end
      end
      return false
    end

    return dfs(0)
  end
end

quiz = [
  [0, 0, 4, 3, 0, 0, 2, 0, 9],
  [0, 0, 5, 0, 0, 9, 0, 0, 1],
  [0, 7, 0, 0, 6, 0, 0, 4, 3],
  [0, 0, 6, 0, 0, 2, 0, 8, 7],
  [1, 9, 0, 0, 0, 7, 4, 0, 0],
  [0, 5, 0, 0, 8, 3, 0, 0, 0],
  [6, 0, 0, 0, 0, 0, 1, 0, 5],
  [0, 0, 3, 5, 0, 8, 6, 9, 0],
  [0, 4, 2, 9, 1, 0, 3, 0, 0],
].flatten
solution = [
  [8, 6, 4, 3, 7, 1, 2, 5, 9],
  [3, 2, 5, 8, 4, 9, 7, 6, 1],
  [9, 7, 1, 2, 6, 5, 8, 4, 3],
  [4, 3, 6, 1, 9, 2, 5, 8, 7],
  [1, 9, 8, 6, 5, 7, 4, 3, 2],
  [2, 5, 7, 4, 8, 3, 9, 1, 6],
  [6, 8, 9, 7, 3, 4, 1, 2, 5],
  [7, 1, 3, 5, 2, 8, 6, 9, 4],
  [5, 4, 2, 9, 1, 6, 3, 7, 8],
].flatten

sudoku = Sudoku.new(quiz)
raise unless sudoku.solve
raise unless sudoku.table == solution