# [QUIZ] Sodoku Solver (#43)

Here is my solution, just uses backtracking and simple algorithm, no
complex strategics.

class Sodoku

def initialize( input )
@ary = Array.new(9) { Array.new(9) } # 9 rows x 9 columns
index = 0
input.to_s.scan(/./) do |c|
case c
when '1'..'9' : @ary[index / 9][index % 9] = c.to_i
when '_' : # skip
else next
end
break if (index += 1) == 9 * 9
end
# raise "Input data incomplete" if index != 9 * 9
end

def solve
9.times do |row|
9.times do |col|
next if @ary[row][col]

# find next possible value for @ary[row][col]
1.upto(9) do |v|
# check on same row/col, no any col/row already used it
next unless 9.times { |i| break if @ary[i][col] == v ||
@ary[row][i] ==v }

# check on 3x3 box, no other cell already used it
next unless 3.times do |i|
break unless 3.times do |j|
break if @ary[i + row / 3 * 3][j + col / 3 * 3] == v
end
end

@ary[row][col] = v

if solve
return true
else
@ary[row][col] = nil # backtracking
end
end

return false
end
end
true
end

def to_s
s = "+-------+-------+-------+\n"
@ary.each_with_index do |row, index|
row = row.map { |e| e ||= '_' } * ' '
row[6,0] = row[12,0] = '| '
s << '| ' << row << " |\n"
s << "+-------+-------+-------+\n" if [2, 5, 8].include?(index)
end
s
end
end

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

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

Hi all,

here is a list of some Sodokus to solve and test
your algorithms (i would like to see which one is
hardest for your script and how long does this take):

···

+-------+-------+-------+

_ 6 _ | 1 _ 4 | _ 5 _ |
_ _ 8 | 3 _ 5 | 6 _ _ |
2 _ _ | _ _ _ | _ _ 1 |

+-------+-------+-------+

8 _ _ | 4 _ 7 | _ _ 6 |
_ _ 6 | _ _ _ | 3 _ _ |
7 _ _ | 9 _ 1 | _ _ 4 |

+-------+-------+-------+

5 _ _ | _ _ _ | _ _ 2 |
_ _ 7 | 2 _ 6 | 9 _ _ |
_ 4 _ | 5 _ 8 | _ 7 _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 2 | _ _ 5 | _ 7 9 |
1 _ 5 | _ _ 3 | _ _ _ |
_ _ _ | _ _ _ | 6 _ _ |

+-------+-------+-------+

_ 1 _ | 4 _ _ | 9 _ _ |
_ 9 _ | _ _ _ | _ 8 _ |
_ _ 4 | _ _ 9 | _ 1 _ |

+-------+-------+-------+

_ _ 9 | _ _ _ | _ _ _ |
_ _ _ | 1 _ _ | 3 _ 6 |
6 8 _ | 3 _ _ | 4 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ 7 _ | 9 4 _ |
_ 7 _ | _ 9 _ | _ _ 5 |
3 _ _ | _ _ 5 | _ 7 _ |

+-------+-------+-------+

_ 8 7 | 4 _ _ | 1 _ _ |
4 6 3 | _ 8 _ | _ _ _ |
_ _ _ | _ _ 7 | _ 8 _ |

+-------+-------+-------+

8 _ _ | 7 _ _ | _ _ _ |
7 _ _ | _ _ _ | _ 2 8 |
_ 5 _ | 2 6 8 | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ _ _ | _ _ _ |
1 2 _ | _ _ _ | _ 3 _ |
_ _ _ | _ 2 4 | _ 5 _ |

+-------+-------+-------+

_ 9 _ | _ _ _ | 6 _ 8 |
_ 3 _ | 5 _ 8 | _ _ _ |
6 7 _ | _ _ _ | 3 _ _ |

+-------+-------+-------+

8 _ _ | _ 1 5 | _ _ _ |
_ 6 _ | 9 _ _ | _ 2 1 |
3 _ _ | _ 4 _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ _ _ | _ _ 1 |
_ _ 4 | _ 1 _ | 6 _ _ |
7 1 _ | _ _ _ | 2 8 _ |

+-------+-------+-------+

_ _ 9 | 3 _ _ | 8 5 _ |
5 _ 8 | 4 _ _ | 7 _ _ |
_ 2 _ | _ 8 5 | _ _ 6 |

+-------+-------+-------+

_ _ _ | _ _ _ | 4 _ _ |
_ 4 6 | _ _ 9 | _ _ _ |
_ _ _ | 7 3 _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ _ _ | _ 6 _ |
9 _ _ | _ _ 3 | _ _ _ |
_ _ _ | _ _ _ | 7 _ 4 |

+-------+-------+-------+

_ _ 6 | _ _ _ | 1 _ 9 |
_ 7 _ | _ 2 _ | 4 3 _ |
_ _ _ | _ _ _ | _ _ 5 |

+-------+-------+-------+

_ _ 3 | _ _ 5 | _ _ 1 |
_ 4 _ | 1 _ _ | 6 _ _ |
_ 6 9 | 4 7 _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ _ _ | 9 _ 7 |
_ _ _ | _ _ 1 | 8 5 _ |
_ _ _ | _ _ _ | 2 3 _ |

+-------+-------+-------+

2 3 _ | _ 6 _ | _ _ _ |
_ 6 9 | 3 8 _ | _ 4 _ |
_ 8 1 | _ _ 5 | 6 _ _ |

+-------+-------+-------+

_ 9 _ | 6 _ _ | _ _ _ |
1 _ 2 | _ _ 7 | _ _ _ |
_ 5 _ | _ _ _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ _ 2 | 7 _ _ |
4 _ _ | 5 8 _ | _ 1 _ |
3 _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

6 _ 7 | _ 5 _ | _ _ _ |
2 1 _ | _ _ _ | 9 _ 3 |
_ _ _ | _ 7 _ | _ _ _ |

+-------+-------+-------+

_ 2 _ | 4 _ _ | _ _ 9 |
_ _ 1 | _ _ 6 | _ _ _ |
_ _ _ | 8 _ _ | 4 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ 1 _ | 7 8 _ |
5 _ _ | _ _ 9 | _ _ _ |
_ _ _ | _ _ _ | _ 4 _ |

+-------+-------+-------+

_ 2 6 | _ _ _ | _ _ _ |
_ _ _ | 6 _ _ | _ _ 3 |
_ 7 4 | _ 8 _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ 3 | _ _ 2 |
_ 8 _ | _ 4 _ | _ 1 _ |
6 _ _ | 5 _ _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ 3 _ | _ _ _ |
9 3 _ | _ 6 _ | 8 _ _ |
5 6 _ | _ _ _ | _ _ 4 |

+-------+-------+-------+

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

+-------+-------+-------+

7 _ _ | _ _ _ | 2 1 _ |
_ _ _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ 5 9 |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ 3 _ | _ _ _ |
9 3 _ | _ 6 _ | 8 _ _ |
5 6 _ | _ _ _ | _ _ 4 |

+-------+-------+-------+

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

+-------+-------+-------+

7 _ _ | _ _ _ | 2 1 _ |
_ _ _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ 5 9 |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ 7 _ | _ _ _ |
3 4 9 | _ _ _ | _ 7 _ |
_ _ 6 | 5 _ _ | 8 4 _ |

+-------+-------+-------+

_ _ 3 | _ 8 6 | _ _ 9 |
2 _ _ | _ _ _ | _ _ _ |
_ _ 5 | 9 _ _ | _ _ _ |

+-------+-------+-------+

5 _ _ | _ 2 _ | _ _ 1 |
9 _ _ | _ _ _ | _ _ 7 |
_ _ 8 | _ _ 1 | 6 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ 7 _ | _ 9 _ |
_ _ _ | _ _ 8 | _ _ 4 |
_ 4 2 | _ _ 1 | _ 7 _ |

+-------+-------+-------+

_ _ 4 | _ _ _ | _ _ 8 |
8 _ _ | 2 _ 5 | _ _ 9 |
5 _ _ | _ _ _ | 7 _ _ |

+-------+-------+-------+

_ 7 _ | 6 _ _ | 1 3 _ |
2 _ _ | 8 _ _ | _ _ _ |
_ 6 _ | _ 3 _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | _ 7 _ | 9 4 _ |
_ 7 _ | _ 9 _ | _ _ 5 |
3 _ _ | _ _ 5 | _ 7 _ |

+-------+-------+-------+

_ 8 7 | 4 _ _ | 1 _ _ |
4 6 3 | _ 8 _ | _ _ _ |
_ _ _ | _ _ 7 | _ 8 _ |

+-------+-------+-------+

8 _ _ | 7 _ _ | _ _ _ |
7 _ _ | _ _ _ | _ 2 8 |
_ 5 _ | 2 6 8 | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | 1 _ _ | 7 _ _ |
_ 2 _ | 6 9 _ | _ _ _ |
9 _ _ | _ _ 3 | _ 8 2 |

+-------+-------+-------+

_ _ _ | _ _ _ | 4 6 _ |
6 4 _ | _ _ _ | _ 5 7 |
_ 5 8 | _ _ _ | _ _ _ |

+-------+-------+-------+

2 1 _ | 8 _ _ | _ _ 9 |
_ _ _ | _ 1 6 | _ 7 _ |
_ _ 4 | _ _ 2 | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | 7 _ _ | _ _ 1 |
_ 8 _ | _ _ _ | 3 2 _ |
_ 1 9 | _ 2 _ | _ _ _ |

+-------+-------+-------+

_ _ 1 | _ 7 3 | _ _ _ |
_ _ _ | 6 _ _ | 1 _ 7 |
9 _ _ | _ 8 _ | _ _ _ |

+-------+-------+-------+

_ 2 4 | 9 _ _ | _ 5 6 |
_ 5 _ | _ 1 _ | 9 _ 2 |
_ _ 6 | _ 5 _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ _ | 9 _ _ | 8 _ 7 |
_ _ _ | _ _ 7 | _ _ _ |
_ _ 3 | _ _ _ | _ _ 2 |

+-------+-------+-------+

_ _ 9 | _ _ 4 | _ _ _ |
_ _ 1 | _ 6 _ | _ _ _ |
_ 6 _ | _ _ 3 | _ _ 1 |

+-------+-------+-------+

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

+-------+-------+-------+

+-------+-------+-------+

_ _ 1 | _ 8 _ | 6 _ 4 |
_ 3 7 | 6 _ _ | _ _ _ |
5 _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ 5 | _ _ _ |
_ _ 6 | _ 1 _ | 8 _ _ |
_ _ _ | 4 _ _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ _ | _ _ 3 |
_ _ _ | _ _ 7 | 5 2 _ |
8 _ 2 | _ 9 _ | 7 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 1 | 2 _ _ | _ 6 _ |
_ _ 9 | _ _ 8 | _ 4 _ |
_ 5 _ | _ 4 _ | 9 _ _ |

+-------+-------+-------+

7 3 _ | _ 8 _ | _ _ _ |
_ _ 5 | _ 3 _ | 1 _ _ |
_ _ _ | _ 6 _ | _ 3 4 |

+-------+-------+-------+

_ _ 3 | _ 2 _ | _ 9 _ |
_ 2 _ | 8 _ _ | 5 _ _ |
_ 9 _ | _ _ 1 | 4 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 1 | 4 3 _ | _ _ 5 |
8 _ 5 | _ _ _ | _ _ _ |
_ 7 _ | 6 _ _ | _ 1 _ |

+-------+-------+-------+

_ _ _ | _ 7 _ | _ _ 9 |
_ _ _ | 2 _ 3 | 4 _ _ |
1 _ _ | _ 8 _ | _ _ _ |

+-------+-------+-------+

_ 2 _ | _ _ 9 | _ _ _ |
9 _ _ | 8 _ _ | 5 2 3 |
3 _ 4 | _ _ _ | 9 7 _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 2 | _ 9 _ | 1 _ 7 |
_ 3 8 | 6 _ _ | _ _ _ |
4 _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ 5 | _ _ _ |
_ _ 9 | _ 1 _ | 3 _ _ |
_ _ _ | 4 _ _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ _ | _ _ 4 |
_ _ _ | _ _ 7 | 9 2 _ |
8 _ 6 | _ 3 _ | 7 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 2 | 6 _ _ | _ _ _ |
_ 9 _ | _ _ _ | 4 _ _ |
_ 1 _ | _ _ 9 | _ _ 7 |

+-------+-------+-------+

_ _ _ | _ 4 6 | _ _ 5 |
_ _ 4 | _ 9 _ | _ 8 _ |
_ _ _ | 7 1 _ | 3 _ 4 |

+-------+-------+-------+

8 _ _ | _ 3 1 | _ _ _ |
3 _ _ | 9 8 _ | _ _ _ |
_ _ _ | 4 _ _ | _ 3 2 |

+-------+-------+-------+

+-------+-------+-------+

_ _ 3 | _ 5 _ | 4 _ _ |
7 _ _ | _ 6 _ | _ _ _ |
_ 5 _ | 8 _ _ | _ 6 _ |

+-------+-------+-------+

5 _ _ | _ _ 3 | _ _ 4 |
_ 1 _ | _ 7 _ | _ 8 _ |
2 _ _ | 4 _ _ | _ _ 7 |

+-------+-------+-------+

_ 4 _ | _ _ 8 | _ 5 _ |
_ _ _ | _ 4 _ | _ _ 9 |
_ _ 6 | _ 1 _ | 2 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 3 | _ 5 _ | 4 _ 7 |
_ _ _ | _ _ _ | _ 9 _ |
4 2 _ | _ _ _ | 5 _ _ |

+-------+-------+-------+

_ _ _ | _ 4 1 | 2 8 _ |
_ _ _ | _ 8 9 | _ 4 _ |
_ _ 1 | _ _ _ | 7 3 _ |

+-------+-------+-------+

_ _ _ | 9 _ _ | _ _ _ |
_ _ 6 | _ _ _ | _ 5 _ |
_ 3 7 | 2 _ _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 3 | 6 2 _ | 4 _ _ |
_ _ _ | _ _ 1 | 5 7 _ |
_ _ _ | _ 7 _ | 9 _ _ |

+-------+-------+-------+

4 _ _ | _ _ _ | 6 9 _ |
_ _ _ | 1 6 _ | 8 _ _ |
2 _ _ | _ _ _ | 1 _ _ |

+-------+-------+-------+

9 _ _ | _ 8 _ | 3 _ _ |
_ 6 8 | 2 _ 4 | _ _ _ |
_ _ _ | _ _ 6 | _ _ 8 |

+-------+-------+-------+

+-------+-------+-------+

_ _ 5 | 4 _ _ | 7 _ _ |
_ _ _ | 5 2 _ | 4 9 6 |
_ _ 4 | _ _ _ | _ 5 _ |

+-------+-------+-------+

_ 1 _ | _ 6 _ | _ _ _ |
_ _ _ | 8 _ _ | _ 4 _ |
2 7 _ | _ _ _ | 8 _ _ |

+-------+-------+-------+

_ _ _ | 2 1 9 | _ _ _ |
1 _ _ | 6 _ _ | _ _ 9 |
_ 8 2 | _ 7 _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 7 | _ _ 4 | _ _ _ |
_ _ 2 | _ _ _ | 9 1 _ |
_ 6 _ | _ 5 _ | _ _ 4 |

+-------+-------+-------+

_ 3 _ | 6 2 _ | 1 _ _ |
6 _ _ | _ 7 _ | _ _ 2 |
_ _ 1 | _ 8 5 | _ 6 _ |

+-------+-------+-------+

2 _ _ | _ 1 _ | _ 4 _ |
_ 1 8 | _ _ _ | 6 _ _ |
_ _ _ | 7 _ _ | 3 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ _ 9 | _ _ 1 | _ 8 7 |
_ _ _ | _ _ _ | 4 _ _ |
_ _ 1 | _ 8 _ | _ 6 _ |

+-------+-------+-------+

_ _ _ | 8 3 6 | _ 2 _ |
_ _ 6 | _ _ _ | _ _ _ |
4 5 _ | _ _ 7 | _ _ 6 |

+-------+-------+-------+

5 _ _ | _ _ 8 | _ _ 9 |
_ 1 _ | _ 6 _ | _ _ 2 |
_ _ _ | 4 2 _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ 2 _ | _ _ _ | _ _ _ |
_ _ _ | 6 _ _ | _ _ 3 |
_ 7 4 | _ 8 _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ 3 | _ _ 2 |
_ 8 _ | _ 4 _ | _ 1 _ |
6 _ _ | 5 _ _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ 1 _ | 7 8 _ |
5 _ _ | _ _ 9 | _ _ _ |
_ _ _ | _ _ _ | _ 4 _ |

+-------+-------+-------+

+-------+-------+-------+

_ 2 _ | _ _ 1 | _ 9 _ |
_ _ 1 | _ 6 5 | 2 _ _ |
_ _ 6 | _ _ _ | _ _ _ |

+-------+-------+-------+

2 8 _ | 4 _ _ | 3 _ _ |
9 _ 7 | _ _ 2 | _ _ 6 |
_ _ 3 | _ _ _ | _ 2 _ |

+-------+-------+-------+

_ 3 _ | _ _ _ | _ _ 5 |
_ 7 _ | _ _ _ | 1 _ 2 |
_ _ 2 | _ 3 _ | 8 _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ 4 _ | _ _ _ | 9 _ _ |
_ _ 3 | 2 _ _ | 8 _ _ |
_ 6 _ | 4 _ _ | _ _ 2 |

+-------+-------+-------+

6 _ _ | 1 5 2 | _ _ _ |
7 5 _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ 5 1 |

+-------+-------+-------+

_ _ 6 | 9 2 _ | _ _ 8 |
_ _ 8 | _ _ 4 | 3 _ _ |
_ 9 7 | 6 _ 8 | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ 4 _ | 8 9 _ | 3 5 _ |
_ _ _ | _ 4 _ | _ _ _ |
_ _ _ | _ _ 5 | 6 _ _ |

+-------+-------+-------+

2 _ _ | _ _ _ | _ 8 _ |
5 _ 3 | 1 8 _ | 9 _ _ |
_ _ 9 | 7 _ _ | 1 _ _ |

+-------+-------+-------+

_ _ _ | _ 5 _ | _ 2 _ |
_ 3 _ | _ _ _ | _ _ 1 |
_ _ 2 | _ _ _ | _ 6 _ |

+-------+-------+-------+

+-------+-------+-------+

_ 5 _ | _ _ _ | 2 _ _ |
_ _ _ | _ _ _ | _ 7 _ |
_ _ _ | _ 6 8 | 3 _ 9 |

+-------+-------+-------+

_ 8 _ | _ 5 4 | 9 _ _ |
6 _ _ | _ _ 2 | 1 _ _ |
_ _ _ | 6 _ 7 | _ _ _ |

+-------+-------+-------+

1 4 _ | 3 _ _ | _ 2 _ |
5 _ _ | _ 7 6 | 8 1 _ |
7 _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

_ 7 _ | _ _ _ | _ _ _ |
6 _ _ | 5 4 _ | _ _ 3 |
_ _ 1 | _ _ 2 | 4 _ _ |

+-------+-------+-------+

_ _ 7 | _ _ 8 | _ _ _ |
_ _ _ | 2 9 _ | _ _ _ |
_ 4 9 | _ _ 3 | _ _ 8 |

+-------+-------+-------+

_ _ 3 | _ _ _ | 7 _ _ |
2 _ _ | 7 3 4 | _ _ 9 |
_ _ _ | _ _ _ | _ 6 _ |

+-------+-------+-------+

+-------+-------+-------+

_ 7 _ | _ _ _ | 3 2 _ |
_ _ _ | _ _ _ | _ 6 _ |
_ _ 8 | 6 _ _ | _ _ 1 |

+-------+-------+-------+

_ _ _ | _ _ _ | 6 3 _ |
7 _ 4 | _ _ _ | _ _ _ |
_ 3 _ | 9 _ 1 | 7 _ 2 |

+-------+-------+-------+

9 2 _ | 8 3 _ | _ _ _ |
5 _ 7 | _ 2 _ | _ _ _ |
_ 6 _ | _ 5 _ | 2 1 _ |

+-------+-------+-------+

+-------+-------+-------+

_ 8 7 | _ 5 _ | 6 _ _ |
4 _ _ | _ _ _ | _ _ 3 |
_ _ _ | 1 _ _ | _ 8 _ |

+-------+-------+-------+

_ _ _ | _ _ 3 | _ _ 4 |
_ 7 _ | 8 _ _ | _ _ _ |
6 _ _ | _ _ _ | _ 5 8 |

+-------+-------+-------+

_ _ _ | _ _ _ | _ 9 2 |
_ _ 2 | _ _ 5 | 3 _ _ |
_ 9 _ | 6 _ _ | 5 1 _ |

+-------+-------+-------+

+-------+-------+-------+

_ 9 _ | _ _ 4 | _ _ _ |
_ _ 4 | _ _ 1 | _ _ 3 |
_ _ _ | 6 9 _ | _ _ 5 |

+-------+-------+-------+

8 _ _ | _ 5 _ | 3 _ 9 |
_ 3 _ | _ _ 7 | 6 _ 2 |
_ _ _ | _ 3 8 | _ _ _ |

+-------+-------+-------+

_ _ _ | _ 7 _ | _ _ _ |
5 _ 1 | _ _ _ | _ _ _ |
_ 6 3 | _ _ _ | 8 _ _ |

+-------+-------+-------+

+-------+-------+-------+

2 _ _ | _ 8 _ | _ _ 6 |
_ 1 _ | _ _ _ | _ 7 _ |
_ _ 9 | _ _ _ | 5 _ _ |

+-------+-------+-------+

_ _ _ | 9 _ 5 | _ _ _ |
3 _ _ | _ 1 _ | _ _ 7 |
_ _ _ | 2 _ 3 | _ _ _ |

+-------+-------+-------+

_ _ 5 | _ _ _ | 4 _ _ |
_ 7 _ | _ _ _ | _ 9 _ |
8 _ _ | _ 4 _ | _ _ 3 |

+-------+-------+-------+

+-------+-------+-------+

3 _ _ | _ 6 _ | _ _ 5 |
_ 2 _ | _ _ _ | _ 4 _ |
_ _ 7 | _ _ _ | 2 _ _ |

+-------+-------+-------+

_ _ _ | 6 _ 7 | _ _ _ |
9 _ _ | _ 8 _ | _ _ 6 |
_ _ _ | 9 _ 1 | _ _ _ |

+-------+-------+-------+

_ _ 2 | _ _ _ | 7 _ _ |
_ 4 _ | _ _ _ | _ 1 _ |
6 _ _ | _ 5 _ | _ _ 9 |

+-------+-------+-------+

+-------+-------+-------+

3 1 _ | 6 _ _ | _ _ _ |
_ _ 2 | _ _ _ | _ _ _ |
_ 5 _ | _ 9 _ | 7 8 _ |

+-------+-------+-------+

_ _ _ | _ _ 5 | _ _ _ |
_ 9 _ | _ 1 _ | _ 6 _ |
_ _ _ | 4 _ _ | _ _ _ |

+-------+-------+-------+

_ 7 5 | _ 6 _ | _ 3 _ |
_ _ _ | _ _ _ | 4 _ _ |
_ _ _ | _ _ 7 | _ 9 2 |

+-------+-------+-------+

+-------+-------+-------+

4 _ _ | _ 1 _ | _ _ 8 |
_ 5 _ | _ _ _ | _ 2 _ |
_ _ 6 | _ _ _ | 9 _ _ |

+-------+-------+-------+

_ _ _ | 9 _ 2 | _ _ _ |
8 _ _ | _ 5 _ | _ _ 3 |
_ _ _ | 1 _ 8 | _ _ _ |

+-------+-------+-------+

_ _ 9 | _ _ _ | 6 _ _ |
_ 2 _ | _ _ _ | _ 5 _ |
1 _ _ | _ 7 _ | _ _ 4 |

+-------+-------+-------+

+-------+-------+-------+

5 _ _ | _ _ 3 | _ _ _ |
_ _ _ | 1 4 _ | _ 9 _ |
9 1 _ | _ 2 6 | 4 _ _ |

+-------+-------+-------+

_ 6 _ | 9 _ _ | _ 5 _ |
_ _ _ | _ _ 5 | 7 _ _ |
_ _ _ | _ 8 _ | _ _ 4 |

+-------+-------+-------+

1 2 _ | _ _ _ | _ 7 3 |
8 _ _ | _ 1 _ | _ 6 _ |
_ _ 6 | _ _ _ | _ _ 1 |

+-------+-------+-------+

+-------+-------+-------+

5 _ _ | _ 8 _ | _ _ _ |
_ _ _ | 3 _ _ | 9 _ _ |
3 _ _ | _ 2 4 | _ _ 5 |

+-------+-------+-------+

_ _ _ | _ 6 8 | _ 1 _ |
_ _ 3 | _ _ 2 | _ _ _ |
8 _ _ | _ _ _ | _ 7 _ |

+-------+-------+-------+

_ _ _ | _ 4 _ | _ 5 9 |
_ _ 6 | 9 3 _ | _ _ 8 |
_ 5 2 | _ _ _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

5 _ 2 | 3 _ _ | 4 7 _ |
_ _ 1 | _ 7 _ | _ _ 9 |
_ _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ _ | _ 5 _ |
_ 3 _ | _ _ 4 | _ _ 6 |
7 _ _ | 5 _ _ | _ 9 _ |

+-------+-------+-------+

_ _ _ | _ 5 _ | _ 1 _ |
_ _ _ | _ _ 3 | 8 _ 7 |
_ 8 _ | 4 _ 9 | _ 3 _ |

+-------+-------+-------+

+-------+-------+-------+

5 3 _ | _ _ _ | _ 7 _ |
_ 9 _ | 3 1 _ | _ 8 _ |
6 _ _ | 9 _ _ | _ _ 1 |

+-------+-------+-------+

_ _ 4 | _ _ _ | _ _ _ |
_ _ 5 | _ 2 4 | _ _ _ |
_ 8 _ | _ _ 6 | _ 1 _ |

+-------+-------+-------+

_ _ _ | 8 _ _ | _ _ 7 |
_ _ _ | _ _ _ | 8 9 _ |
_ _ 6 | _ _ 9 | _ 5 2 |

+-------+-------+-------+

+-------+-------+-------+

6 _ _ | _ 4 _ | _ _ 3 |
_ 1 _ | _ _ _ | _ 7 _ |
_ _ 5 | _ _ _ | 8 _ _ |

+-------+-------+-------+

_ _ _ | 5 _ 2 | _ _ _ |
3 _ _ | _ 9 _ | _ _ 2 |
_ _ _ | 1 _ 3 | _ _ _ |

+-------+-------+-------+

_ _ 8 | _ _ _ | 9 _ _ |
_ 7 _ | _ _ _ | _ 5 _ |
2 _ _ | _ 3 _ | _ _ 4 |

+-------+-------+-------+

+-------+-------+-------+

6 _ _ | _ 7 _ | _ _ 9 |
_ 1 _ | _ _ _ | _ 2 _ |
_ _ 5 | _ _ _ | 4 _ _ |

+-------+-------+-------+

_ _ _ | 1 _ 2 | _ _ _ |
9 _ _ | _ 8 _ | _ _ 6 |
_ _ _ | 6 _ 9 | _ _ _ |

+-------+-------+-------+

_ _ 1 | _ _ _ | 2 _ _ |
_ 3 _ | _ _ _ | _ 4 _ |
7 _ _ | _ 5 _ | _ _ 8 |

+-------+-------+-------+

+-------+-------+-------+

6 _ 5 | _ _ _ | _ _ _ |
2 _ _ | 4 _ _ | _ 7 _ |
_ 1 _ | _ 7 _ | 6 _ 9 |

+-------+-------+-------+

4 _ _ | _ _ _ | 7 _ _ |
1 9 _ | _ 3 _ | 8 _ _ |
_ _ 3 | _ _ 9 | _ _ 2 |

+-------+-------+-------+

_ 6 _ | 3 _ 8 | 9 _ _ |
_ 4 _ | _ _ 7 | _ _ _ |
_ _ _ | 1 _ _ | 2 _ _ |

+-------+-------+-------+

+-------+-------+-------+

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 _ _ |

+-------+-------+-------+

+-------+-------+-------+

7 _ _ | _ 2 _ | _ _ 4 |
_ 5 _ | _ _ _ | _ 8 _ |
_ _ 1 | _ _ _ | 6 _ _ |

+-------+-------+-------+

_ _ _ | 3 _ 7 | _ _ _ |
1 _ _ | _ 6 _ | _ _ 9 |
_ _ _ | 5 _ 8 | _ _ _ |

+-------+-------+-------+

_ _ 6 | _ _ _ | 5 _ _ |
_ 8 _ | _ _ _ | _ 4 _ |
9 _ _ | _ 4 _ | _ _ 1 |

+-------+-------+-------+

+-------+-------+-------+

7 _ _ | 2 _ _ | 5 _ 9 |
2 _ _ | _ _ 3 | _ 7 8 |
_ 6 _ | _ _ _ | _ 2 _ |

+-------+-------+-------+

_ 2 _ | _ _ _ | _ _ 7 |
6 _ 9 | _ _ 5 | _ _ _ |
_ 1 _ | _ 4 6 | _ _ _ |

+-------+-------+-------+

_ _ 6 | 3 _ _ | _ 8 4 |
_ _ _ | _ _ _ | 7 _ _ |
_ _ _ | 8 9 _ | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

8 _ 2 | _ _ _ | _ _ 4 |
_ 9 _ | _ _ _ | _ _ 7 |
_ _ 5 | _ _ 1 | 3 9 _ |

+-------+-------+-------+

_ 8 _ | _ 1 7 | _ _ _ |
_ _ _ | 5 _ 2 | _ _ 1 |
_ _ _ | _ _ 8 | _ 3 6 |

+-------+-------+-------+

_ _ 7 | 1 _ _ | _ _ _ |
4 _ _ | _ 7 _ | _ _ _ |
3 2 _ | _ _ 5 | _ _ _ |

+-------+-------+-------+

+-------+-------+-------+

9 _ _ | _ _ _ | 1 _ _ |
_ 8 _ | _ 7 _ | _ _ _ |
3 _ _ | 9 _ _ | 8 _ _ |

+-------+-------+-------+

_ 2 1 | 6 8 _ | _ _ _ |
_ _ 9 | _ _ _ | _ _ _ |
8 _ _ | _ 9 _ | _ 2 _ |

+-------+-------+-------+

7 _ 6 | 4 _ _ | _ _ 2 |
_ _ 5 | _ _ _ | _ 3 _ |
_ _ 8 | 7 2 _ | _ _ 5 |

+-------+-------+-------+

+-------+-------+-------+

9 _ _ | _ 7 _ | _ _ 4 |
_ 1 _ | _ _ _ | _ 5 _ |
_ _ 8 | _ _ _ | 2 _ _ |

+-------+-------+-------+

_ _ _ | 8 _ 9 | _ _ _ |
7 _ _ | _ 4 _ | _ _ 6 |
_ _ _ | 2 _ 7 | _ _ _ |

+-------+-------+-------+

_ _ 3 | _ _ _ | 1 _ _ |
_ 2 _ | _ _ _ | _ 8 _ |
6 _ _ | _ 9 _ | _ _ 7 |

+-------+-------+-------+

cheers

Simon

The "official" Sudoku ( http://www.sudoku.com/ ) (not sodoku) should
have only one unique solution per puzzle.
I simply slightly modified my previous quiz solution to show all
possible solutions.
Added show_all_solutions ( almost the same as solve method )

class Sodoku
attr_reader :solutions

def initialize( input )
@ary = Array.new(9) { Array.new(9) } # 9 rows x 9 columns
@solutions = 0
index = 0
input.to_s.scan(/./) do |c|
case c
when '1'..'9' : @ary[index / 9][index % 9] = c.to_i
when '_' : # skip
else next
end
break if (index += 1) == 9 * 9
end
# raise "Input data incomplete" if index != 9 * 9
end

def solve
9.times do |row|
9.times do |col|
next if @ary[row][col]

# find next possible value for @ary[row][col]
1.upto(9) do |v|
# check on same row/col, no any col/row already used it
next unless 9.times { |i| break if @ary[i][col] == v ||
@ary[row][i] ==v }

# check on 3x3 box, no other cell already used it
next unless 3.times do |i|
break unless 3.times do |j|
break if @ary[i + row / 3 * 3][j + col / 3 * 3] == v
end
end

@ary[row][col] = v

if solve
return true
else
@ary[row][col] = nil # backtracking
end
end

return false
end
end
true
end

def show_all_solutions
9.times do |row|
9.times do |col|
next if @ary[row][col]

shift_row = row / 3 * 3
shift_col = col / 3 * 3

# find next possible value for @ary[row][col]
1.upto(9) do |v|
# check on same row/col, no any col/row already used it
next unless 9.times { |i| break if @ary[i][col] == v ||
@ary[row][i] ==v }

# check on 3x3 box, no other cell already used it
next unless 3.times do |i|
break unless 3.times do |j|
break if @ary[i + shift_row][j + shift_col] == v
end
end

@ary[row][col] = v
show_all_solutions
@ary[row][col] = nil # backtracking
end

return
end
end
@solutions += 1
puts to_s
end

def to_s
s = "+-------+-------+-------+\n"
@ary.each_with_index do |row, index|
row = row.map { |e| e ||= '_' } * ' '
row[6,0] = row[12,0] = '| '
s << '| ' << row << " |\n"
s << "+-------+-------+-------+\n" if [2, 5, 8].include?(index)
end
s
end
end

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

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

if your input is like:

···

+-------+-------+-------+

_ _ _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ _ _ |
_ _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

It will show you all 6,670,903,752,021,072,936,960 solutions.
( This number is equivalent to 9! × 722 × 27 × 27,704,267,971 )
How long it takes? I don't know, and I do not like try it

Back to the quiz, the puzzle is
+-------+-------+-------+

_ 6 _ | 1 _ 4 | _ 5 _ |
_ _ 8 | 3 _ 5 | 6 _ _ |
2 _ _ | _ _ _ | _ _ 1 |

+-------+-------+-------+

8 _ _ | 4 _ 7 | _ _ 6 |
_ _ 6 | _ _ _ | 3 _ _ |
7 _ _ | 9 _ 1 | _ _ 4 |

+-------+-------+-------+

5 _ _ | _ _ _ | _ _ 2 |
_ _ 7 | 2 _ 6 | 9 _ _ |
_ 4 _ | 5 _ 8 | _ 7 _ |

+-------+-------+-------+

my show_all_solutions takes only ~ 0.515 seconds (on my machine)
to find it has only one unique solution.

And later I try the only 17 cells numbers
( Currently it is the minimum cell numbers puzzle and still has unique
solution )
+-------+-------+-------+

_ _ 6 | 9 _ _ | _ 7 _ |
_ _ _ | _ 1 _ | _ _ 2 |
8 _ _ | _ _ _ | _ _ _ |

+-------+-------+-------+

_ 2 _ | _ _ _ | _ _ 4 |
_ _ _ | _ _ _ | _ _ 1 |
_ _ 5 | _ _ 6 | _ _ _ |

+-------+-------+-------+

_ _ _ | _ _ _ | _ 6 _ |
_ _ _ | _ _ 2 | _ 5 _ |
_ 1 _ | _ 4 3 | _ _ _ |

+-------+-------+-------+

This time, it takes ~ 3116.285 seconds to make sure it has only one
unique solution.

However, my program is kind of translate from my java program.
My origin Java program is something like:

static void SolvePuzzle() {
ShowAllAns();
}

static void ShowAllAns() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (puzzle[i][j] <= 0) {
next_value: for (int value = 1; value <= 9; value++) {
// On the same column, make sure no any row already used it
// On the same row, make sure no any column already used it
for (int k = 0; k < 9; k++) {
if ((puzzle[k][j] == value) || (puzzle[i][k] == value)) {
continue next_value;
}
}
// On the 3x3 box, make sure no other cell already used it
int p = (i / 3) * 3;
int q = (j / 3) * 3;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (puzzle[p+x][q+y] == value) {
continue next_value;
}
}
}

puzzle[i][j] = value;
ShowAllAns();
puzzle[i][j] = 0;
}
return; // tried all possible value, just return
}
}
}
PrintPuzzle();
}

And the java program solves the 17 cell numbers puzzle takes only ~ 10969 ms.

So for the same "algorithm", for the same problem ( 17 cell numbers,
find and make sure unique solution ),
the java one takes ~ 11 seconds and the ruby one takes ~ 1 hour.

I may need to refactor my ruby program ...

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

The way I translate the Java's continue label is not "ruby way".

The java's continue label is like:

static void ShowAllAns() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (puzzle[i][j] <= 0) {
next_value: for (int value = 1; value <= 9; value++) {
// On the same column, make sure no any row already used it
// On the same row, make sure no any column already used it
for (int k = 0; k < 9; k++) {
if ((puzzle[k][j] == value) || (puzzle[i][k] == value)) {
continue next_value; // continue with label
}
}
// On the 3x3 box, make sure no other cell already used it
int p = (i / 3) * 3;
int q = (j / 3) * 3;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (puzzle[p+x][q+y] == value) {
continue next_value; // continue with label
}
}
}

puzzle[i][j] = value;
ShowAllAns();
puzzle[i][j] = 0;
}
return; // tried all possible value, just return
}
}
}
PrintPuzzle();
}

···

----------------------------
I translated like :

def solve
9.times do |row|
9.times do |col|
next if @ary[row][col]

# find next possible value for @ary[row][col]
1.upto(9) do |v|
# check on same row/col, no any col/row already used it
next unless 9.times { |i| break if @ary[i][col] == v ||
@ary[row][i] ==v }

# check on 3x3 box, no other cell already used it
next unless 3.times do |i|
break unless 3.times do |j|
break if @ary[i + row / 3 * 3][j + col / 3 * 3] == v
end
end

@ary[row][col] = v

if solve
return true
else
@ary[row][col] = nil # backtracking
end
end

return false
end
end
true
end

-------------------------------
Using too many breaks to simulate Java's continue label...
I almost forget Ruby's throw-catch.
I think translate Java's continue label the "Ruby" way maybe like this:

def solve
9.times do |row|
9.times do |col|
next if @ary[row][col]

# find next possible value for @ary[row][col]
1.upto(9) do |v|
catch :next do
# check on same row/col, no any col/row already used it
9.times { |i| throw :next if @ary[i][col] == v || @ary[row][i] ==v }

# check on 3x3 box, no other cell already used it
3.times do |i|
3.times do |j|
throw :next if @ary[i + row / 3 * 3][j + col / 3 * 3] == v
end
end

@ary[row][col] = v

if solve
return true
else
@ary[row][col] = nil # backtracking
end
end
end
return false
end
end
true
end

Slightly modified, during the reduce once,
the while loop may reduce some cells to unique possibility number,
so set back to the cells data to reduce brute force steps.

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 }
@cells[index] = number[0] # add this line compare to previous program
@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

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