[QUIZ] Sodoku Solver (#43)

ruby-talk
1

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

2

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

3

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 :wink:

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

4

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

5

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

6

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

7

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