Saturday, July 22, 2006

Programming a Sudoku Solver

I programmed a Sudoku solver the other weekend. I was going to blog as I went, but there were too many interrupts and as the coding gets more interesting I forget to blog. I end up with a blog of the boring parts :-) The key thing is what did I learn about my little exercise?

The first thing I learned was how important discipline is. I started by slicing my problem into small slices with tests driving the code until I got to my first tough part...solving for a cell. I thought "Hey I can code this in no time and get this test to pass". An hour later I was running the debugger and asking myself "How did I get here?" when my wife called to help puts the kids in bed. In disgust, I killed the IDE and didn't return till the following morning. My own hubris caused me to abandon discipline! Once I got back into the habit of slicing the problem and driving the development with tests I was able to get the solver working and in no time I was able to solve all but the "wicked" level of Sudoku's.

The second lesson was the power of TDD. I had not programmed in over a year and the process drove me through to a solution in roughly 8 hours. I honestly believe that when we look back on this time for the history books, TDD will be the first true productivity catalyst since second order languages. If you did it right OO gets you 5-10%, Pair 10-15%, but I think TDD will get you 50-100%.

The third lesson happened when I got into a discussion with a co-worker. He is a fairly smart guy with out any experience in TDD. When I brought the subject up his face literally changes to one of disdain. He thought the idea of writing tests for each line of code was absolutely stupid. He assured me that code coverage tools would lead me to a better use of my testing time; good developers obviously shouldn't be spending too much time writing tests! I then remembered the lesson I learned from my last job...change is evil...even for smart people! People have strong beliefs that have been re-enforced as they live life and develop patterns to deal with this world. Therefore most experienced developers have a long list of things that must be done and things that should be avoided. For this one developer, and probably many like him, one of the things to avoid was writing too many tests. Maybe a programmers ego is threatened by tests. Maybe the thinking is "If I am good then I don't need some stupid test to double check my work and tell me I am doing a good job!" I have to admit, when I was a full-time developer I wrote the least amount of unit test code among my team. I wonder what I would have thought about TDD then? Hmm, whatever the thinking I find it interesting that I think TDD is the best thing to happen since iterative delivery and other equally intelligent people think it is a waste of time.

The fourth lesson revolves around feature splitting. The Sudoku solver feature set was pretty simple. It only allowed for a few methods (load, solve, check solution and print), but 90% of the code revolved around one feature (solve). It required thinking to break it down into its parts - something I call design. Lacking discipline, I chose the simpler method of just trying to code it and then refactor it into a decent design. I realize now that stopping to design and TDD were working in tandem to point me to doing the right thing! Of course you only learn these things by doing the wrong thing :-)

My last lesson has little to do with my coding exercise and more to do with several different posts and blogs I have read about TDD. Many people think they know how to write software. I have learned that we really don't "know", but we are uncovering better ways of doing it. Once we figure it out then we can automate the whole process and put us all out of work. So many people cling to simple minded beliefs that we have actually figured it out and all we need to do is to follow the age old wisdom of define it, design it, write it and test it! SEI seems to collect people with this mindset. In my opinion we must constantly question our preconceived notions about software development because just when you think it's truly a given, technology or some one smart shows you just how wrong you are.