sudoku.rb

class Sudoku
  def initialize board
    @board = board
  end

  def solve!
    num_index = @board.index('0')
    return true unless num_index
    ('1'..'9').each do |possibility|
      @board[num_index] = possibility
      return @board if (board_valid? num_index) && solve!
    end
    @board[num_index] = '0'
    false
  end

  def board_valid? num_index
    num = @board[num_index]
    return false unless valid_row? num, num_index
    return false unless valid_col? num, num_index
    return false unless valid_box? num, num_index
    true
  end

  def valid_row? num, num_index
    row = num_index / 9
    start = row * 9
    (start..(start + 8)).each do |check_i|
      return false unless valid? check_i, num, num_index
    end
    true
  end

  def valid_col? num, num_index
    col = num_index%9
    start = 0
    (1..9).each do |x|
      check_i = start + col
      return false unless valid? check_i, num, num_index
      start += 9
    end
    true
  end

  def valid_box? num, num_index
    col_start, row_start = (((num_index%9)/3) * 3), ((num_index/27) * 27)
    3.times do
      (col_start..(col_start+2)).each do |col|
        return false unless valid? col + row_start, num, num_index
      end
      row_start += 9
    end
  end

  def valid? index, num, num_index
    return false if index != num_index && num == @board[index]
    true
  end
end

s = Sudoku.new("800000000003600000070090200050007000000045700000100030001000068008500010090000400")
p s.solve!