A couple of weeks ago the
UH Code Dojo embarked on the
fantastic voyage that is writing
a program to solve Sudoku puzzles, in Ruby. This week, we
continued that journey.
Though we still haven't completed the problem (we'll be meeting again tenatively on October 15, 2007 to
do that), we did construct what we think is a viable plan for getting there, and began to implement some
of it.
The idea was based around this algorithm (or something close to it):
while (!puzzle.solved)
{
find the most constrained row, column, or submatrix
for each open square in the most constrained space,
find intersection of valid numbers to fill the square
starting with the most constrained,
begin filling in open squares with available numbers
}
With that in mind, we started again with
TDD.
I'm not going to explain the rationale behind each peice of code, since the idea was presented above.
However, please feel free to ask any questions if you are confused, or even if you'd just like
to challenge our ideas.
Here are the tests we added:
def test_find_most_constrained_row_column_or_submatrix
assert_equal "4 c", @solver.get_most_constrained
end
def test_get_available_numbers
most_constrained = @solver.get_most_constrained
assert_equal [3,4,5], @solver.get_available_numbers(most_constrained).sort
end
def test_get_first_empty_cell_from_most_constrained
most_constrained = @solver.get_most_constrained
indices = @solver.get_first_empty_cell(most_constrained)
assert_equal [2,4], indices
end
def test_get_first_empty_cell_in_submatrix
indices = @solver.get_first_empty_cell("0 m")
assert_equal [0,2], indices
end
And here is the code to make the tests pass:
def get_most_constrained
min_open = 10
min_index = 0
@board.each_index do |i|
this_open = @board[i].length - @board[i].reject{|x| x==0}.length
min_open, min_index = this_open, i.to_s + " r" if this_open < min_open
end
#min_row = @board[min_index.split(" ")]
@board.transpose.each_index do |i|
this_open = @board.transpose[i].length - @board.transpose[i].reject{|x| x==0}.length
min_open, min_index = this_open, i.to_s + " c" if this_open < min_open
end
(0..8).each do |index|
flat_subm = @board.get_submatrix_by_index(index).flatten
this_open = flat_subm.length - flat_subm.reject{|x| x==0}.length
min_open, min_index = this_open, index.to_s + " m" if this_open < min_open
end
return min_index
end
def get_available_numbers(most_constrained)
index, flag = most_constrained.split(" ")[0].to_i,most_constrained.split(" ")[1]
avail = [1,2,3,4,5,6,7,8,9] - @board[index] if flag == "r"
avail = [1,2,3,4,5,6,7,8,9] - @board.transpose[index] if flag == "c"
avail = [1,2,3,4,5,6,7,8,9] - @board.get_submatrix_by_index(index).flatten if flag == "m"
return avail
end
def get_first_empty_cell(most_constrained)
index, flag = most_constrained.split(" ")[0].to_i,most_constrained.split(" ")[1]
result = index, @board[index].index(0) if flag == "r"
result = @board.transpose[index].index(0), index if flag == "c"
result = index%3*3,index*3+@board.get_submatrix_by_index(index).flatten.index(0) if flag == "m"
return result
end
Obviously we need to clean out that commented-out line, and
I feel kind of uncomfortable with the small amount of tests we have compared to code. That unease was
compounded when we noticed a call to
get_submatrix instead of
get_submatrix_by_index.
Everything passed because we were only testing the first most constrained column. Of course, it will
get tested eventually when we have
test_solve, but it was good that the pair-room-programming
caught the defect.
I'm also not entirely convinced I like passing around the index of the most constrained
whatever along
with a flag denoting what type it is. I
really think we can come up with a better way to do that, so
I'm hoping that will change before we rely too much on it, and it becomes impossible to change without
cascading.
Finally, we also set up a repository for this and all of our future code. It's not yet open to the public
as of this writing (though I expect that
to change soon). In any case, if you'd like to get the full source code to this, you can find our Google Code
site
at
http://code.google.com/p/uhcodedojo/.
If you'd like to aid me in my quest to be an idea vacuum (cleaner!), or just have a question, please feel
free to contribute with a comment.
Hey! Why don't you make your life easier and subscribe to the full post
or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate
wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!
Leave a comment
There are no comments for this entry yet.
Leave a comment
