Wednesday, June 13, 2007

Sudoku and TDD

For the last few months, I've been trying on and off to write a program to solve a Sudoku game. The "easy" ones are easy, you just use a rudimentary algorithm:

  • each cell has a list of possible values associated with it

  • start by associating all values 1-9 to each cell

  • repeat until solved:

    • for each cell, remove any values already present in the same line, column, or box

By this process of repeated elimination you can solve a lot of the "easy" tables. However, this algorithm is too limited and it will go into an infinite loop if you have a situation where, for example, two cells in the same row can accept values 1 and 5, but at this point you have no way of knowing which is which.

Now, of course the solution to that problem is simply a recursive backtracking algorithm:

  • save the current state

  • pick one value and try to solve the rest of the table; if it worked, all is good; if not, go back to the saved state and try the next value

The devil, however, is in the details. I would go into some weird state where suddenly I had a row with two cells having the same value... which of course ruined everything else. And debugging something which is five recursion levels deep and goes through 81 cells each time... I wasn't willing to spend all that effort for a stupid problem, especially with the number of programs already available solving it.

That was the case until one night when I was really bored and wanted to program something for fun :) But I had also just read yet another article on Test-Driven Design and decided to try it. It took me a few hours that night, and a few more hours the next morning, but I managed to make it work. Hehe. That's a cool feeling, especially since, while I have tried TDD before, this was the first time I actually felt it helped.

That's code I'd take to an interview :)

No comments: