```Speed up my program ...

It seems difficult and low performace to backtracting possibilities data set ...
I did try to duplicate possibilities data and each guess to reduce the
possibilities data set.
But it is slow then just using brute force.
( Time is wasted on recursive process on the possiblilities data set
maintenance/creation )

This version will just reduce the possibilities data set only once
then using brute force.
It is much faster than my previous program ( of course, it is slower
than others good program ... )
--------------------------------------------

class Sodoku
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  # reduce only once then
return _solve(0)                          # brute force to solve it
end

def show_all_solutions
return unless reduce_possibilities  # reduce only once then
_solve_all(0)                       # brute force to solve all solutions
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
index = number = nil
while @possibilities.find { |index, number| number.size == 1 }
@possibilities.delete(index)
neighborhoods = NEIGHBORHOODS[index]
@possibilities.each do |key, value|
next unless neighborhoods.include?(key)
value -= number
if value.size == 0
return false  # invalid input data
else
@possibilities[key] = value
end
end
end
true
end

def _solve(start)
start.upto(80) do |index|
next if @cells[index]
@possibilities[index].each do |value|
next if NEIGHBORHOODS[index].any? { |i| @cells[i] == value }
@cells[index] = value
_solve(index + 1) ? (return true) : @cells[index] = nil
end
return false
end
true
end

def _solve_all(start)
start.upto(80) do |index|
next if @cells[index]
@possibilities[index].each do |value|
next if NEIGHBORHOODS[index].any? { |i| @cells[i] == value }
@cells[index] = value
_solve_all(index + 1)
@cells[index] = nil
end
return
end
@solutions += 1
puts self
end
end

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

sodoku = Sodoku.new(input)
puts sodoku.solve ? sodoku : "No solution"

# sodoku = Sodoku.new(input)
# sodoku.show_all_solutions
# puts "Total #{sodoku.solutions} solutions."
end

```