Solving Sudoku with TDD

Posted by Kurt Christensen on May 07, 2007

Community

Agile

Topics

Agile Techniques

Tags

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.

1. Back to top

   What's the point?

   May 9, 2007 2:51 PM by Dean Schulze

   Kurt,
   
   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.

   Reply

2. Back to top

   Re: What's the point?

   May 11, 2007 1:16 AM by Kurt Christensen

   I'm glad you enjoyed this. I think the point is that TDD is a tool, like any tool, and we can always find scenarios where the tool (at least by itself) isn't quite up to the task.
   
   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?

   Reply

3. Back to top

   Re: What's the point?

   May 13, 2007 10:15 AM by Vladimirl Levin

   I think Peter's solution would probably not be useful as a real software product intended for people who wanted hints while solving hard puzzles. It's just a demonstration that the puzzle can be solved quickly enough by a computer. It's interesting to be sure, but I've found some Web sites where the computer uses more human strategies to solve Sudoku puzzles, and that seems much more useful since it presumably provides hints that are meaningful to a human being. A computer that provides a hint "set this value here next because I've run through a large tree of possibilities and this just happens to work" isn't really being especially helpful if you ask me. I'm also not sure whether Peter's code would be helpful in *generating* Sudoku puzzles. Again, here we need to assign difficulty values to the puzzles as well as making sure they are solvable. If I had to write Sudoku software in the real world, I'd probably interview people who are really good at Sudoku and find out how they solve puzzles, and try to integrate that wisdom into my program - which is much more representative of how most real-world business programming is done.

   Reply

4. Back to top

   Agile blasphemy...

   May 14, 2007 10:11 PM by Amr Elssamadisy

   Ok, so here goes.... I never really bought into the 'no design and let design emerge' argument. Before there was TDD as defined by Kent's TDD book, there were those of us who wrote tests first and kept things simple using YAGNI, but still designed rigorously.
   
   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...

   Reply

• Older >