Mohit Muthanna wrote:

>I actually worked on this before the Sudoku challenge even came up. I
>think, based on your e-mail, it uses the same recursive algorithm that
>you do, but I haven't verified that yet.
>

Our algorithms are essentially similar.  One optimization I made is that 
instead of attempting to solve the first empty cell seen, I skim over 
all of the empty cells and find the one with the fewest possible 
solutions.  The value of this optimization appears to be a wash; most 
boards I clock under your time by 20-50%, but on the "hard board" you 
clock a 20s against my "more efficient" 37s.  Wild.  Something about 
that puzzle forces any solver to grind deep and hard, and your not 
taking extra time to think about the next move pays off handsomely.

Your calculate_options method seems to do what my settle method does, 
finding unsolved cells with only one option.  One question I had while 
reading your code, what happens if your loop finds a cell with options, 
then finds a cell to settle, and settling it causes the other cell to no 
longer have options (but to be settled)?  have_options is never reset.  
The only valid case this can happen is if calculate_options solves the 
puzzle, so you could probably test for it outside the method.

Hmm, you don't use the return value, so I guess the point is moot.  :-)

Also, I just noticed that the unit tests I uploaded yesterday were 
broken, because I renamed the settle() method.  (It used to be called 
'flatten', but that has some existing semantics from Array#flatten.  
Since they are not similar, I changed the name due to POLS.)

-dB
P.S. James, I made the changes to initialize; they are uploaded now.  
For the list's benefit, here is the new load method:

# ----------------------------------------------------------------------
  def load(str)
    line_num = 0
    str.each_line do |line|
      line.gsub!('_','0')
      line.delete!('+|-')
      line.strip!
      if line.length > 0
        l = line.split /\s+/
        fail "Line length was #{l.length}.  line: #{line}" unless 
l.length == 9
        @board[line_num] = l.collect {|x| x.to_i}
        line_num += 1
      end
    end

    fail "Board is not valid." unless self.valid?
  end
# ----------------------------------------------------------------------

-- 
David Brady
ruby_talk / shinybit.com
I'm feeling really surreal today... OR AM I?