def read_matrix(data)
  lines = data.lines
  9.times.collect { |i| 9.times.collect { |j| lines[i][j].to_i } }
end

def permissible(matrix, i, j)
  ok = [nil, *1..9]
  check = ->(x,y) { ok[matrix[x][y]] = nil  if matrix[x][y].nonzero? }
  
  9.times { |x| check[x, j] }
  
  9.times { |y| check[i, y] }
  
  xary = [ *(x = (i / 3) * 3) .. x + 2 ]        
  yary = [ *(y = (j / 3) * 3) .. y + 2 ]
  xary.product(yary).each { |x, y| check[x, y] }
  
  ok.compact
end

def deep_copy_sudoku(matrix)
  matrix.collect { |row| row.dup }
end

def solve_sudoku(matrix)
  loop do
    options = []
    9.times do |i|
      9.times do |j|
        next if matrix[i][j].nonzero?
        p = permissible(matrix, i, j)
        
        return if p.empty?              
        options << [i, j, p]
      end
    end
    
    return matrix if options.empty?

    i, j, permissible = options.min_by { |x| x.last.length }

    
    if permissible.length == 1
      matrix[i][j] = permissible[0]
      next
    end

    
    permissible.each do |v|
      mtmp = deep_copy_sudoku(matrix)
      mtmp[i][j] = v
      ret = solve_sudoku(mtmp)
      return ret if ret
    end

    
    return
  end
end

def print_matrix(matrix)
  puts  or return  unless matrix

  border = 
  9.times do |i|
    puts border if i%3 == 0
    9.times do |j|
      print j%3 == 0? : 
      print matrix[i][j] == 0? : matrix[i][j]
    end
    puts 
  end
  puts border
end

data = <<EOS
394__267_
___3__4__
5__69__2_
_45___9__
6_______7
__7___58_
_1__67__8
__9__8___
_264__735
EOS

matrix = read_matrix(data)
print_matrix(matrix)
puts
print_matrix(solve_sudoku(matrix))