I am sorry to post too many my solutions.
(Someone maybe already sick to see my posts)
I only try to improve myself, everytime, I try to make it better (
clean / elegant / performance ).

I was excited to see my solutions for the same problem from 15 sec
down to 6 sec and now down to ~ 1 sec ...

Here is my other solution:

class Sudoku
  attr_reader :solutions
  
  def initialize( input )
    @cells = Array.new(81)
    @possibilities = {}
    @solutions = 0
    index = 0
    input.to_s.scan(/./) do |c|
      case c
        when '1'..'9' : @possibilities[index] = [ @cells[index] = c.to_i ]
        when '_'      : @possibilities[index] = (1..9).to_a 
        else next
      end
      break if (index += 1) == 81
    end
    # raise "Input data incomplete" if index != 81
  end

  def solve
    return false unless reduce_possibilities(@possibilities)
    return _solve(@possibilities)
  end

  # to_s borrow from Simon ...
  def to_s
    "+-------+-------+-------+\n| " +
    Array.new(3) do |br|
      Array.new(3) do |r|
        Array.new(3) do |bc|
          Array.new(3) do |c|
            @cells[br*27 + r * 9 + bc * 3 + c] || "_"
          end.join(" ")
        end.join(" | ")
      end.join(" |\n| ")
    end.join(" |\n+-------+-------+-------+\n| ") +
    " |\n+-------+-------+-------+\n"
  end 

  private
  
  # The cell's neighborhoods are cells need to check to be sure no duplicate
  # value with the cell. It has exactly 20 cells neighborhoods per cell.
  NEIGHBORHOODS = Array.new(81) do |index| 
    row, col = index / 9, index % 9
    r, c = row / 3 * 3, col / 3 * 3
    ary = []
    9.times do |i| 
      ary << (i * 9 + col)               # add cells at the same column 
      ary << (row * 9 + i)               # add cells at the same row
      ary << ((i/3) + r) * 9 + (i%3) + c # add cells at the same 3x3 box
    end
    ary.uniq - [index]
  end
  
  def reduce_possibilities(possibilities)
    index = number = nil
    while possibilities.find { |index, number| number.size == 1 }
      @cells[index] = number[0]
      possibilities.delete(index)
      neighborhoods = NEIGHBORHOODS[index]
      possibilities.each do |key, value|
        next unless neighborhoods.include?(key)
        value -= number
        if value.size == 0
          return false
        else
          possibilities[key] = value
        end
      end
    end
    true
  end
    
  def _solve(possibilities)
    return true if possibilities.empty?
    key, values = possibilities.shift    
    values.each do |v|
      pos = possibilities.dup
      pos[key] = [v]
      next unless reduce_possibilities(pos)
      return true if _solve(pos)
    end
    false
  end

end


if __FILE__ == $0
  input = ''
  while line = gets
    input << line
  end

  sudoku = Sudoku.new(input)
  puts sudoku.solve ? sudoku : "This puzzle has no solution!"
end