This is an entry for a little competition that is happening at my company. The aim is to produce an example set of code to demonstrate good TDD in producing a solution that will solve a sudoku puzzle grid.
I choose to use this as an opportunity to try out a few things I've been meaning to for a little while. As a result, it became less about creating a winning entry and more about exploration of techniques.
- I used the SpecFlow BDD framework as an experiment into how it works. I have tried to drive my tests via a Specification by Example process, and wanted to compare how it works in contrast to using NBehave. SpecFlow is not perfect because it generates code at Editing time from the feature files, so you must edit the features within visual studio in order to change them. It does have good support from other tools integrating with ReSharper, Gallio, and Testdriven.Net.
- I tried to follow Keith Braithwaites TDD as if you mean it process, so the algorithm is less designed and more evolved. However I will admit I was pragmatic about it rather than strict, possibly as a result of using Specification by Example instead of pure Unit testing. However as this code does not yet have an executable or UI to run it, it has not been refactored to address any release concerns, and as such test code is mixed into the same assembly as functional code.
I developed the code by building my features on top of each other.
- Cell.feature - First the features of a cell, and how it handles possible solutions
- Region.feature - next defining a region (row, column, or 3x3 grid) and how that cells canot share the same values.
- GridBuilder.feature - building grids so that cells are shared correctly across regions for 2x2, 3x3, 4x4 and 9x9 grids
- Grid.feature - where we start to check that regions work in tandem to reduce possible solutions down to a single outcome
- ExampleSolves.feature - where I started applying some real grids to prove that the algorithm really works
I have discovered that my algorithm doesn't work for 17-cell puzzles (see http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php). I assume that this is because the grid reaches a state where there is more than one possible solution for a cell and each possible grid needs to be evaluated to determine whether that grid is valid. I have not included further development where I clone the grid into multiple candidate solutions and solve each one as I do not believe that helps in meeting the original goal, which was to demonstrate good testing, not an amazing algorithm.
TDDCompetitionBDD.zip (10.90 mb)