Esoteric Dissertations from a One-Track Mind

May 22, 2007

Sudoku Solver, Part 2

Filed under: programming — codesmithy @ 5:59 am

The one design philosophy embodied in the sudoku solver is “Design for Testability.” According to a study by DeMarco and Lister, professional programmers average 1.2 bugs for every 200 lines of code. Now, the smallest block of code that you can test via a computer is a function. There are ways to test smaller blocks of code manually via a debugger, by manually setting variables and skipping instructions, but since testing is something we’d like the computer to help us with if possible, it is important to have testable functions. Since the program was 277 lines, as it turns out, I did introduce a bug when writing it that required debugging.

The most significant artifact of the “Design for Testablility” are the following function prototypes
bool IsCorrect(void) const;
private:
bool CheckRow(int i) const;
bool CheckColumn(int i) const;
bool CheckSquare(int i) const;

IsCorrect would be a large function without CheckRow, CheckColumn, and CheckSquare. Notice, that each function produces a meaningful result that can be interpreted.  If we have a problem with a column, then we only need to set that one column, instead of all 81 entries of the Sudoku board.  As it turns out, there was a bug in the IsCorrect logic. When I first entered a sudoku puzzle, none of the squares were correct. This narrowed the bug down to IsCorrect or CheckSquare. So, I wrote a test for CheckSquare, figuring that was most likely where the bug would be found.


void Test(void)
{
Sudoku s;
s.Set(0,0,1);
s.Set(0,1,2);
s.Set(0,1,3);
s.Set(1,0,4);
s.Set(1,1,5);
s.Set(1,2,6);
s.Set(2,0,7);
s.Set(2,1,8);
s.Set(2,2,1);
bool result = s.CheckSquare(0);
assert(!result);
}

After, exposing the CheckSquare function as public. Interestingly enough, when I ran the test, the function didn’t assert. When I looked harder at my IsCorrect function I found the error.


// Check Squares
for(int i = 0; result && i < DIMENSION; ++i)
{
result = CheckColumn(i);
}

Oops, that should be CheckSquare(i). After I fixed that problem, the program gave the correct solution.

I feel that there is an attitude in academic Computer Science that programs are like equations, in that view the proper way to ensure quality is by rigor and errors can be avoided. In my opinion, bugs cannot be avoided, they happen, and the best thing that you can do plan for when they do occur, that you’ve given some thought on how you can track them down quickly. If you write a function that is over 200 lines, it is almost certain that it has a bug, and that it exists anywhere in the 200 lines of code. Functions that are less than 20 lines are likely to be 95% bug free.  Being able to track the bug down to 1 or 2 functions, culling 80% of the code automatically, as we did here, was invaluable to quickly getting the program done and working.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: