```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]]}

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

```