Posted by Sam on Sep 19, 2007 at 01:37 PM UTC - 5 hrs
A couple of days ago the UH Code Dojo met once again (we took the summer off). I had come in wanting to
figure out five different ways to implement binary search.
The first two - iteratively and recursively - are easy to come up with. But what about three
other implementations? I felt it would be a good exercise in creative thinking, and pehaps it
would teach us new ways to look at problems. I still want to do that at some point, but
the group decided it might be more fun to tackle to problem of solving any Sudoku board,
and that was fine with me.
Remembering the trouble
Ron Jeffries had in
trying to
TDD a solution
to Sudoku, I was a bit
weary of following that path, thinking instead we might try
Peter Norvig's approach. (Note: I haven't looked
at Norvig's solution yet, so don't spoil it for me!)
Instead, we agreed that certainly there are some aspects that are testable, although
the actual search algorithm that finds solutions is likely to be a unit in itself, and therefore
isn't likely to be testable outside of presenting it a board and testing that its outputted solution
is a known solution to the test board.
On that note, our first test was:
require 'test/unit'
require 'sudokusolver'
class TestSudoku < Test::Unit::TestCase
def setup
@board = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4 ,1 ,9 ,0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
@solution =[[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4 ,1 ,9 ,6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]]
@solver = SudokuSolver.new
end
def test_solve
our_solution = @solver.solve(@board)
assert_equal(@solution, our_solution)
end
end
We promptly commented out the test though, since we'd never get it to pass until we were done. That
doesn't sound very helpful at this point. Instead, we started writing tests for testing the validity
of rows, columns, and blocks (blocks are what we called the 3x3 submatrices in a Sudoku board).
Our idea was that a row, column, or block is in a valid state
if it contains no duplicates of the digits 1 through 9. Zeroes (open cells) are acceptable in
a valid board. Obviously, they are not acceptable in a solved board.
To get there, we realized we needed to make initialize take the initial game board
as an argument (so you'll need to change that in the TestSudokuSolver#setup method and
SudokuSolver#solve, if you created it), and then we added the following tests (iteratively!):
def test_valid_row
assert @solver.valid_row?(0)
end
def test_valid_allrows
(0..8).each do |row|
assert @solver.valid_row?(row)
end
end
The implementation wasn't difficult, of course. We just need to reject all zeroes from the row, then run
uniq! on the resulting array. Since uniq! returns nil if each
element in the array is unique, and nil evaluates to false, we have:
class SudokuSolver
def initialize(board)
@board = board
end
def valid_row?(row_num)
@board[row_num].reject{|x| x==0}.uniq! == nil
end
end
At this point, we moved on to the columns. The test is essentially the same as for rows:
def test_valid_column
assert @solver.valid_column?(0)
end
def test_valid_allcolumns
(0..8).each do |column|
assert @solver.valid_column?(column)
end
end
The test failed, so we had to make it pass. Basically, this method is also the same for columns as it was
for rows. We just need to call Array#transpose# on the board, and follow along. The
valid_column? one-liner was @board.transpose[col_num].reject{|x| x==0}.uniq! == nil.
We added that first, made sure the test passed, and then refactored SudokuSolver
to remove the duplication:
class SudokuSolver
def initialize(board)
@board = board
end
def valid_row?(row_num)
valid?(@board[row_num])
end
def valid_column?(col_num)
valid?(@board.transpose[col_num])
end
def valid?(array)
array.reject{|x| x==0}.uniq! == nil
end
end
All the tests were green, so we moved on to testing blocks. We first tried slicing in two dimensions, but
that didn't work: @board[0..2][0..2]. We were also surprised Ruby didn't have something
like an Array#extract_submatrix method, which assumes it it passed an array of arrays (hey,
it had a transpose method). Instead, we created our own. I came up with some nasty, convoluted code,
which I thought was rather neat until I rewrote it today.
Ordinarily, I'd love to show it as a fine example of how much prettier it could have become. However, due
to a temporary lapse into idiocy on my part: we were editing in 2 editors, and I accidentally saved the
earlier version after the working version instead of telling it not to save. Because of that,
I'm having to re-implement this.
Now that that sorry excuse is out of the way, here is our test for, and implementation of extract_submatrix:
def test_extract_submatrix
assert_equal [[1,2,3],[4,5,6],[7,8,9]].extract_submatrix(1..2,1..2) , [[5,6],[8,9]]
end
class Array
def extract_submatrix(row_range, col_range)
self[row_range].transpose[col_range].transpose
end
end
Unfortunately, that's where we ran out of time, so we didn't even get to the interesting problems Sudoku
could present. On the other hand, we did agree to meet again two weeks from that meeting (instead of a month),
so we'll continue to explore again on that day.
Thoughts? (Especially about idiomatic Ruby for Array#extract_submatrix)
Update: Changed the misspelled title from SudokoSolver to SudokuSolver.
Update 2: SudokuSolver Part 2 is now available.
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!
Last modified on Oct 04, 2007 at 04:05 PM UTC - 5 hrs
Comments
Leave a comment
You're meetings sound way cool. I like hands-on projects.
Posted by Ben Nadel
on Sep 19, 2007 at 03:36 PM UTC - 5 hrs
Thanks Ben - they absolutely are. We try to mix up languages (although we've only used Java and Ruby to this point) and talk about design goals and see it done it action. Though we've mostly worked on algorithms, I'd like to do some simple sample apps to show the design process and whatnot. We share the keyboard with whoever wants to type, and generally the entire group discusses ways to proceed in solving the problem. It moves a little slower that way, but I think it is worth it in the amount of opinion and discussion it generates. It's also great to hear all the different ideas on how to solve a problem coming from people with diverse backgrounds. I learn something new, or remember some strategy that I haven't thought of in a while in each meeting. One of these days I'd like to open up the codedojo.org site to allow other dojos to host pages there as well. I've just been lazy on that front. =) Anyway, when will we see you start the NYC Code Dojo? =)
Posted by Sam
on Sep 20, 2007 at 07:21 AM UTC - 5 hrs
You're using 0 for unsolved squares. Just thinking ill-formed thoughts out loud: if you used nil instead, you could hold the partial solutions in a tuplespace, and use the partial solution to test for the existence of a more refined solution before each DRb client attempts to solve it further, try something else, etc, because Rinda uses nil as a wildcard.
Posted by hgs
on Sep 21, 2007 at 05:27 AM UTC - 5 hrs
@hgs - It's funny you mention that, because we did discuss attempting to solve it concurrently. We also started with nil instead of zeroes, but because readability problems caused by unaligned cells, decided to change it to zeroes. Of course, we can use a simple search and replace to get them back to nil, so readability isn't a concern now that we have the boards in place. Thanks for the thoughts to consider - I'll bring them up when we meet again. And feel free to keep them coming!
Posted by Sam
on Sep 21, 2007 at 06:36 AM UTC - 5 hrs
Code Dojo in NY :) Good idea!
Posted by Ben Nadel
on Sep 21, 2007 at 07:21 AM UTC - 5 hrs
|
Me
|
