Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ


Choose your language

InfoQ Homepage News Solving Sudoku with TDD

Solving Sudoku with TDD

Last year, Ron Jeffries wrote a series of articles in which he demonstrated test-driven development in practice, attempting to create a Sudoku solver in Ruby. Ravi Mohan recently discovered these articles and contrasted them with a similar effort by Peter Norvig, implying the weakness of TDD as a design method. The crux of the argument compares the elegant solution of Dr. Norvig:
In this essay I tackle the problem of solving every Sudoku puzzle. It turns out to be quite easy (about 100 lines of [Python] code) using two ideas: constraint propagation and search.
...with the meanderings of Mr. Jeffries:
I could start, I suppose, with a simple Sudoku game and try to TDD its solution. I don't feel that I could do that... So, instead, I'm going to set up a game with an assumed internal data structure, and then TDD some methods that I expect to need... Arguably this is a violation of YAGNI, but since I don't really know how to start or how to know when I'm done, writing some Spike code in TDD style seems to me to be a good way to get my feet wet.

I'm not saying this is good, or what you should do, or anything of the kind. I'm displaying what I do, faced with this problem, and how I explore what the computer and I can do in moving toward a Suduko solution.

In other words, Norvig's essay presents a logical progression of ideas towards a compact, elegant solution ("science as it's shown"), whereas Jeffries' series of articles give insight into the actual discovery process ("science as it's done"). Unimpressed with Ron's efforts, the crew at devgrind had this to say about TDD:
“If your only tool is a hammer, every problem looks like a nail.” And it supports my impression that in these days too many people in the development world focus on the methodological aspects of software development and underestimate the importance of fundamentals such as algorithm design.
Vladimir Levin elaborated on this in a defense of TDD, pointing out the distinction between creating algorithms and building software:
Trying to offer TDD as an algorithm generator is dopey and it's just going to make it easy for people not to take TDD seriously as a valid design technique. So what is the purpose of TDD then? The goal of TDD is to reduce the need to determine ahead of time which classes and methods you're going to implement for an entire story.
In other words, while TDD may not be the best tool for inventing new algorithms, it may very well be the best tool for applying those algorithms to the problem at hand. An additional point: Peter Norvig is Director of Research at Google, author of the leading textbook on artificial intelligence, and may be one of the better programmers alive. While mere mortals may aspire to emulate his thought processes, it is also helpful to see how one might actually go about approaching a difficult problem.

Rate this Article