| David Brady 2005-08-28, 6:59 pm |
| 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?
|