Solving Sudoku with TDD
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.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:
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.
“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.
What's the point?
Thanks for posting this. It's not clear that Ron learned anything from his efforts. Others have pointed out that TDD is not a good approach for algorithm development, but its not clear from Ron's writings that he has even come to that conclusion.
Maybe the point of this is that Agilists oversell their wares by being oblivious to their limitations.
Re: What's the point?
But I enjoyed following Ron's description of his thought process (or lack thereof?) as it was actually happening. We all like the myth of genius - Mozart dictating music from God and such - but the trajectory of any real creative process almost always look like Ron's, regardless of what textbooks and biographies would have us believe.
Now, had this been a real-world programming task for an employer, the first thing one would probably do is search Google to see if there was an existing algorithm or set of strategies which one could apply. Perhaps Ron should have done this, but I don't think we should read too much into it; it seems to me that solving Sudoku was simply a vehicle for illustrating a technique. After all, "Hello, world!" is a rotten vehicle for introducing a programming language, but everyone keeps doing it.
And what if we didn't have Norvig to guide us, and someone wanted us write a Sudoku solver? How would we go about it? Sit around for a long time and think really, really hard, hoping for a brilliant insight? And how would you feel if you were the one signing the check for that activity?
Re: What's the point?
So - maybe emergent design can be seen in two ways:
1) Do not design and let the design emerge purely from removing duplication.
2) Design only enough to pass the tests at hand, and refactor towards a better design when it the current one no longer does.
Finally, TDD is one tool in the toolbox, not the only one. I would venture to guess that when writing sort algorithms we start with something like the Quicksort instead of trudging our way through a Bubble-sort and its variants...