My Secret Life as a Spaghetti Coder
home | about | contact | privacy statement
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!


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

Leave a comment

Leave this field empty
Your Name
Email (not displayed, more info?)
Website

Comment:

Subcribe to this comment thread
Remember my details
Google
Web CodeOdor.com

Me
Picture of me

Topics
.NET (19)
AI/Machine Learning (14)
Answers To 100 Interview Questions (10)
Bioinformatics (2)
Business (1)
C and C++ (6)
cfrails (22)
ColdFusion (78)
Customer Relations (15)
Databases (3)
DRY (18)
DSLs (11)
Future Tech (5)
Games (5)
Groovy/Grails (8)
Hardware (1)
IDEs (9)
Java (38)
JavaScript (4)
Linux (2)
Lisp (1)
Mac OS (4)
Management (15)
MediaServerX (1)
Miscellany (76)
OOAD (37)
Productivity (11)
Programming (168)
Programming Quotables (9)
Rails (31)
Ruby (67)
Save Your Job (58)
scriptaGulous (4)
Software Development Process (23)
TDD (41)
TDDing xorblog (6)
Tools (5)
Web Development (8)
Windows (1)
With (1)
YAGNI (10)

Resources
Agile Manifesto & Principles
Principles Of OOD
ColdFusion
CFUnit
Ruby
Ruby on Rails
JUnit



RSS 2.0: Full Post | Short Blurb
Subscribe by email:

Delivered by FeedBurner