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


Comments
Leave a comment

There are no comments for this entry yet.

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 Cplusplus (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