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:
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:
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 :)
- 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 :)
Comments