Hi,

here is my solution. The algorithm is well described by Horndude77,
but this implementation also features the brute force part to solve
them all. (which may need some more seconds)

This one is hardest for my algorithm (from the list i posted):

+-------+-------+-------+
| 7 _ _ | _ _ _ | _ 1 9 |
| 4 6 _ | 1 9 _ | _ _ _ |
| _ _ _ | 6 8 2 | 7 _ 4 |
+-------+-------+-------+
| _ 9 _ | _ _ _ | _ _ 7 |
| _ _ _ | 3 _ _ | 4 _ 5 |
| _ _ 6 | 7 _ _ | _ _ _ |
+-------+-------+-------+
| _ _ 1 | _ _ _ | _ _ _ |
| 2 _ _ | _ 7 4 | _ _ _ |
| _ _ _ | 2 _ _ | 3 _ _ |
+-------+-------+-------+

it took 18.6s to solve:
+-------+-------+-------+
| 7 8 2 | 4 5 3 | 6 1 9 |
| 4 6 5 | 1 9 7 | 8 2 3 |
| 3 1 9 | 6 8 2 | 7 5 4 |
+-------+-------+-------+
| 5 9 3 | 8 4 1 | 2 6 7 |
| 1 2 7 | 3 6 9 | 4 8 5 |
| 8 4 6 | 7 2 5 | 9 3 1 |
+-------+-------+-------+
| 6 7 1 | 9 3 8 | 5 4 2 |
| 2 3 8 | 5 7 4 | 1 9 6 |
| 9 5 4 | 2 1 6 | 3 7 8 |
+-------+-------+-------+

here is the code:
----------------------------------------------------------------------
require 'Set'
require 'Benchmark'

class Board
   @@col = Array.new(9) {|o| Array.new(9){|i| o + i*9}}
   @@row = Array.new(9) {|o| Array.new(9){|i| o*9 + i}}
   @@box = Array.new(9) {|o| Array.new(9){|i|
     (o / 3) * 27 + (o % 3) * 3 + ((i % 3) + (i / 3) * 9)}}

   @@neighbourhoods = Array.new(81) {|i|
     [[], @@row[i /9], @@col[i % 9],  @@box[(i / 27) * 3 + (i % 9) / 3]]}

   attr_reader :cells, :possibilities

   def initialize cells
     @possibilities = Array.new(81) {(1..9).to_set}
     @cells = Array.new(81){0}
     81.times{|i|set_cell(i, cells[i]) if cells[i] != 0}
   end

   def set_cell c, v
     @@neighbourhoods[c].flatten.each{|i|
       possibilities[i]-=[v] unless c==i}
     @cells[c], @possibilities[c] = v, [v]
   end

   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].nonzero? || "_"
           end.join(" ")
         end.join(" | ")
       end.join(" |\n| ")
     end.join(" |\n+-------+-------+-------+\n| ") +
     " |\n+-------+-------+-------+\n"
   end

   def solve_with_logic!
     count, changed = 0, 0
     begin
       next if @cells[i = count % 81] != 0
       p = possibilities[i]
       @@neighbourhoods[i].each do |neighbours|
         pn = neighbours.inject(p){|r, j|(j != i)?r-possibilities[j]:r}
         if pn.size == 1
           pn.each{|c| set_cell(i, c)}
           changed = count
           break
         end
       end
     end until ((count += 1) - changed) > 81
     self
   end

   def solve_with_logic
     Board.new(@cells).solve_with_logic!
   end

   def solve
     board = solve_with_logic
     return nil if (0..80).find{|i| board.possibilities[i].size == 0}
     return board unless board.cells.find{|c| c==0}

     #we have to guess
     (2..9).each do |c|
       81.times do |i|
         if (p = board.possibilities[i]).size == c
           p.each do |j|
             board.set_cell(i,j)
             b = board.solve
             return b if b
           end
           return nil
         end
       end
     end
   end

end

# main
count, $stdout.sync = 0, true
Benchmark.bm 20 do |bm|
   loop do
     cells = []
     while cells.size < 81 do
       exit 0 if ARGF.eof
       ARGF.gets.scan(/[0-9_.]/).each{|c| cells << c.to_i}
     end
     board = Board.new(cells)
     bm.report "solving nr #{count+=1}" do
       board = board.solve
     end
     puts board.to_s + "\n\n"
   end
end
----------------------------------------------------------------------

cheers

Simon