class Sudoku
  def initialize(puzzle)
    @puzzle = puzzle
    9.times do |x|
      9.times do |y|
        @puzzle[x][y] = Set.new(1..9) if @puzzle[x][y] == 0
      end
    end
  end

  def react(x, y, val=nil)
    if @puzzle[x][y].is_a?(Set)
      @puzzle[x][y].delete(val)
      if @puzzle[x][y].length == 1
        @puzzle[x][y] = @puzzle[x][y].to_a[0]
        9.times do |i|
          react(x, i, @puzzle[x][y])
          react(i, y, @puzzle[x][y])
          react((x / 3 ) * 3 + i % 3, (y / 3 ) * 3 + i / 3, @puzzle[x][y])
        end
      end
    end
  end

  def solve
    9.times do |x|
      9.times do |y|
        if @puzzle[x][y].is_a?(Integer)
          9.times do |i|
            react(x, i, @puzzle[x][y])
            react(i, y, @puzzle[x][y])
            react((x / 3 ) * 3 + i % 3, (y / 3 ) * 3 + i / 3, @puzzle[x][y])
          end
        end
      end
    end
    self
  end

  def puzzle
    @puzzle
  end
end

def sudoku(puzzle)
  Sudoku.new(puzzle).solve.puzzle
end