Ravi Mohan's Blog

Tuesday, April 24, 2007

Learning From Sudoku Solvers

Ron Jeffries attempts to create a sudoku solver - here, here, here, here and here. (You really ought to read these articles. They are ummm...{cough} ...err.... enlightening.)
Peter Norvig creates a Sudoku Solver.
Compare. Learn.
Update: Discussion on reddit
somewhat peripherally related but similiar (this about the bowling game) discussion
The devgrind post
Update 2:
(Oct 2009) Peter Norvig spoke about this post in Peter Seibel's book, "Coders at Work". My reaction..
Update 3:
Peter Siebel author of "Coders at Work" weighs in. Some gems there.
"One thing I noticed, reading through Jeffries’s blog posts, was that he got fixated on the problem of how to represent a Sudoku board. He immediately started writing tests of the low-level details of a few functions for manipulating a data structure representing the 9×9 Sudoku board and a few functions for getting at the rows, columns, and boxes of the board. (“Boxes” are what Sudoku players call the 3×3 squares subsquares of the 9×9 board.)
Then he basically wandered around for the rest of his five blog postings fiddling with the representation, making it more “object oriented” and then fixing up the tests to work with the new representation and so on until eventually, it seems, he just got bored and gave up, having made only one minor stab at the problem of actually solving puzzles.
I suspect, having done a small amount of TDD myself, that this is actually a pattern that arises when a programmer tries to apply TDD to a problem they just don’t know how to solve. If I was a high-priced consultant/trainer like Jeffries, I’d probably give this pattern a pithy name like “Going in Circles Means You Don’t Know What You’re Doing”.
.....
(Norvig has) 7 definitions in 12 lines of code and he’s done with data representation. I’m not sure how much code Jeffries ended up with. In his fourth installment he had about 81 lines devoted to providing slightly less functionality than Norvig provided in the code we just looked at. In the fifth (and mercifully final) installment, he started adding classes and subclasses and moving things around but never presented all the code again. Safe to say it ended up quite a lot more than 12 lines; if he’s lucky it stayed under 120.



" Siebel's post is worth reading in its entirety.


Update 4:
Andrew Dalke's Problems with TDD (and the comments, some by eminent TDD proponents) reveal TDD's feet of clay.



33 comments:

Anonymous said...

HPNDUF - Hard problems need design up front!

Anonymous said...

I think it is a little more subtle than "design up front" vs "TDD".

I think what Ravi is trying to illustrate (Ravi, do correct me if I am
wrong)is the difference in the quality of thought between the two programmers.

Ron's thought process (as expressed in his writing) is terribly woolly and sloppy (I shudder to think what that kind of sloppy thinking would result in in my field - Physics). He wanders around for a long period of time, without any deep analysis of the problem, falls into all sorts of pits on the way, and finally solves about a quarter of the problem. Ron is thinking like some kind of mad alchemist, throwing random elements into the pot, stoking the fires and waiting to see if the lab to blow up.

Peter's thought process moves implacably from analysis to design to code and back till the *whole problem* is solved.

The key insight is in his (Peter's) *rejection of standard strategies* (whereas Ron flirts with the idea of implementing strategies obtained from elsewhere)

Peter says,

"What next? We could try to code more sophisticated propagation strategies, as described here. For example, the naked pairs strategy looks for two squares in the same unit that both have the same two possible digits. Suppose both A1 and A4 have the possibilities 2 and 6. We can conclude that 2 and 6 must be in A1 and A4 (although we don't know which is where), and we can therefore eliminate 2 and 6 from every other square in the A row unit. We could code that strategy in a few lines by adding an elif len(values[s]) == 2 test to eliminate.

*****Coding strategies like this is a possible route, but would lead to many lines of code (there are dozens of these strategies), and we'd never be sure if we could solve every puzzle. **** "


emphasis mine.
Peter goes on to say

"The other route is to search for a solution: to systematically try all possibilities until we hit one that works. The code for this is only a few lines, but we run another risk: that it might take forever to find what we're searching for. Consider that in the hard puzzle above, A2 has 4 possibilities (1679) and A3 has 5 possibilities (12679); right there that's 20 possibilities, and if we keep multiplying out, we get 462838344192000000000000000000000000000 (or about 4E38) possibilities for the whole puzzle. Can that be right? Well there are 61 unfilled squares, and it looks like each of these unfilled squares has on average 4 or 5 possibilities. And indeed 461 < 4E38 < 561. Should we give up now? No! We are saved by constraint propagation. We don't have to try all 4E38 possibilities because as soon as we try one we immediately eliminate many other possibilities.

In fact, it turns out that to solve this puzzle we only need to look at only 25 possibilities and we only have to explicitly search through 9 of the 61 unfilled squares; constraint propagation does the rest. For the list of 95 hard puzzles, on average we need to consider 64 possibilites per puzzle, and in no case do we have to search more than 16 squares. "

now compare that to Ron Ron who says things like

"I thought about the problem off and on today, just a little bit. *****I couldn't see any way that this simple solver could be wrong ****"

whoa!!!

he continues,
"
-- but I also know what it means when a programmer says there's no way his program could be wrong.

So I decided to set a trap. I extended the solver part of the code so that after setting each new value, it checks to see if the game is still solvable, using just a very simple test: does there exist a cell in the game such that it's blocked and can contain none of the numbers from 1-9. I ran the problem and it actually failed fairly early ... the matrix was less than half full and it had already blocked.

I looked at the code, looked at the last move it had made, and it all looked OK. So I decided that I would go back to websoduku.com and see whether my solution looked like the solved version of the original puzzle. I figured I'd let the program make one move at a time, and see if websoduke agreed with me."


The difference in quality of thinking is very obvious.

Peter does **analytical systematic thinking**. Ron's process is essentially "try different things and when the tests pass, hopefully the problem is completely solved"

Ron can never be sure that the problem is solved. Peter can.

Of course Ron abandoned the problem
after a few days of working, so his "solution" doesn't really exist in the first place. So there is no comparison at all.

If I wanted some code written and I had the choice of these two programmers, I'd know who to choose.

Anonymous said...

@Joe
"Ron is thinking like some kind of mad alchemist, throwing random elements into the pot, stoking the fires and waiting to see if the lab to blow up."

ROTFL!!!!!

This made my day. Thanks!

Ravi said...

@Joe,
You are right. It is not so much "big design up front" vs "tdd".


As I've mentioned in another blog entry, I find it fascinating, that people who presume to be gurus of "methodologies" and try to tell the rest of us how to code, all the while either writing no code or writing extremely ill designed code.


If Ron Jeffries (who wrote a book emphasizing TDD as a design method) can make such suboptimal progress with TDD, the rest of us should be very skeptical of such a "design method".

Please note that I think having a constantly growing suite of unit tests is a good idea. As is refactoring your code periodically.

"Designing" with TDD is not (unless you restrict the word "design" just to indicate degree of test coverage or structural features like how many lines a method has).

But the latent idea in TDD that the design will "fall out of" constant write_test-write_code-refactor cycles is crap (imo) for any non trivial problem.

I've been accused of being "too harsh" on Agile/lean before, so this time I explicitly avoided adding commentary to the post.(I couldn't resist the "enlightening" comment :-) ). The code (and the thinking process behind the code) says it all.

Fwiw, in my experience this kind of "TDD design" does work (for some values of "work") for the "stich some apis together" kind of enterprise project, the kind that is ripe for outsourcing. Beyond that, its record is very spotty.


Yes i know I am being a bit unfair comparing Peter Norvig to Ron Jeffries. This is like comparing an F22 fighter to a World War 1 biplane. But hey code is code :-)

I am very impressed that a non programmer (you are a scientist IIRC) could get so much insight into the programmers' thought process.

great comment.
Thanks,

keithb said...

Ron Jeffries attempts to create a sudoku solver[...]

Peter Norvig creates a Sudoku Solver.

Compare. Learn.


I don't think the two writeups are neccesarily comparable in any very illuminating way.

In particular Norvig does not seem to show us the process by which he arrived at his solution, he only explains (very well) how it works. What he doesn't do (which Ron does) is show his working. The Norvig piece reads like an excerpt from a texbook, and as tends to be the case with textbook "explanations" if it explains anything it explains how you would go in a straight line from nothing to the textbook solution if you already knew what that was. Very much what Joe above describes: "Peter's thought process moves implacably from analysis to design to code[...]" Well, the account we have here makes it look as if that's what happened. But did it really?

Ron, on the other hand, pretty explicitly presents a stream-of-conciousness record of him killing some time by playing around with the problem in a certain style.

Don't get me wrong, Ron's noodlings are ghastly to behold and give a poor impression of TDD, even more so than those nasty bowling examples. But I don't think the comparison (or the lesson) is quite as clear it it might seem at first glance.

Anonymous said...

@keith,
ok let us ignore the "stream of consiousness" part.

Even then, Peter explicitly does complexity analysis (working out the worst case scenario for search for example). Ron (in his so called"stream of thought") never even attempts to do this, but in turn tries 'ghastly' things to the code.

He *never* addresses the core of the problem even towards the end. (If you check the extreme programming" mailing list on yahoo at the time of Ron's articles you can see a whole bunch of xp- ers suggesting bugfixes and alternatives all the way. Not *one* of them approaches the problem like Dr Norvig does at *any point*.

Even assuming Peter made as many (or more) wrong turns in the path, this level of thinking is well above Ron's.

To see Peter making th3 same "stream of conciousness" style decisions, making mistakes and backing out etc, do compare his "Paradigms of Artificial Intelligence Programming" with Ron's "Adventures in C#".

You'll see the same difference (or an even greater difference) in quality of thinking there.


So I am afraid it still does come down to TDD not being a sufficient design method and/or Ron being a terrible programmer.

If you must, ignore the "stream" look at at the final code. (Though TDD is supposed to make the soc a lot better)

Which one is more robust and can handle the most number of difficult inputs? How many inputs can each piece of code handle?

But of course, as Joe pointed out above he just gives up after a week or so of work and that in itself is enough to damn him and his "teachings". he is simply outclassed and outcoded.

btw the reddit title encompasses the difference very well. Ravi is being diplomatic here(for a change :-D).

Dibs on Muad said...

WOW... long pause!!! My initial reaction to this post was "How can you even compare Norvig and Jeffries?" After reading *all* the links posted in the blog entry, I guess its time to lick the dust off my AIMA book. It would be nice to be able to think like THAT :).

@keithb "...record of him killing some time by playing around with the problem in a certain style."

How do you know Norvig wasn't doing the same?

@Joe - It's always a pleasure to read your comments!!

keithb said...

So, let's not descend to any sort of "my Peter Norvig can beat up your Ron Jeffries any day" slanging match. I think everyone reading this will agree on which is the more impressive contributor to the industry.

And yet...TDD is the wrong approach to take to a sudoku solver exactly because it is a trivial problem, in a very particular sense. Building a soduko solver is a matter of solving the "algorithms + data structures = programs" equation and not much else.

This is not the domain where TDD is primarily applicable. It is the kind of problem whereby someone as smart as Norvig can (probably did) have a flash on insight and then wrote down the solution.

And then there's the kind of software that most of us in the industry make a living at writing. And this isn't by any means the "stich some apis together" end of the market either.

It's the wide open space in the middle where the key abstractions are not yet well understood (in Sudoko they are absolutely understood), it's the space where many people (not one loan genius, but probalby not thousands either) will work on a codebase over months or years and mustn't trip over one another.

Smart as Norvig cerainly is, there will be an upper limit to the size of problem where he can just see the solution in terms of a couple of techniques, as it has been made to look with the Soduko solver. And I assert without proof that this limit is below the size of many, even most, commerically useful software development problems. And above that limit, that's the space where TDD works. Yes, that means that TDD will work differently well for different people in different circumstances. There are not silver bullets, TDD is not one.

And let's not forget that TDD didn't come from nowhere: it comes from the way people write software in Smalltalk, and they learned that from the LISP community and elswhere. And so I'd bet that Peter Norvig has done a hell of a lot of development driven by exemplars and found a lot of designs by refinement, which is all TDD is.

Anonymous said...

It's like comparing guitars by making Jimi Hendrix play one, and the teen next door the other. The comparison is in fact interesting, but the conclusions are all wrong.

Also, try to write a sudoku solver yourself without reading too much on the net. At least Ron Jeffries came up with a working solution, not being a mathematical oracle or anything like that. Only a narrow amount of mathematically-gifted people will be able to solve problems in a way Norvig does, the ordinary ones may benefit more from a step-by-step approach used by Jeffries - assuming they're working all on their own, not copying or "translating" the solution.

Obviously Peter Norvig is the clear winner here, but it is not as black-and-white as you seem to put it.

Anonymous said...

"It's like comparing guitars by making Jimi Hendrix play one, and the teen next door the other. The comparison is in fact interesting, but the conclusions are all wrong."

If you notice Ravi doesn't conclude very much. he just says "look at X. look at Y .learn"

You use a good analogy though. And does your teen next door also go around claiming to a be a guitar God? Does he write books on guitar playing and presume to tell other guitar players how to play? Does he have a "guitar playing method"?




>At least Ron Jeffries came up with a working solution, not being a mathematical oracle or anything like that.

he did? As far as i can see he stopped halfway and wandered off into programming shotgun images or something equally crappy, all the while proclaiming the superiority of agile/tdd?

>Only a narrow amount of mathematically-gifted people will be able to solve problems in a way Norvig does, the ordinary ones may benefit more from a step-by-step approach used by Jeffries - assuming they're working all on their own, not copying or "translating" the solution.

Irrelevant. Since Ron never finished the problem. Holding Ron up as some kind of example to follow is a very --- weak.

Paul Prescod said...

If you read the agile manifesto you'll find it is all about the process of capturing requirements and turning them into software. I don't think that it really has much to say about algorithm development, but all of software engineering is not necessarily algorithm development. One can easily imagine that a person tasked with improving the performance of a relational database would find almost nothing of value in the agile approach. Conversely, someone focused on building business-case driven CRUD web apps will find nothing of value in a textbook about algorithms or AI techniques. That doesn't mean that one set of techniques or the other are valueless, just that they are not universally applicable.

Anonymous said...

Real Programmers - No Bullshit, No Process, Simple Beautiful Code, No big deal...

Crappy Programmers - Total Bullshit, Only Processes, Complex Crappy Code, Would put it on the front page if he could...

Unknown said...

@keithb
"Peter's thought process moves implacably from analysis to design to code[...]" Well, the account we have here makes it look as if that's what happened. But did it really?"

I havent been inside Norvigs head to be sure about this, but im not surprised if he really did it in that way. First, its clear that soduku is a constraint propagation problem. Then, you realize that sometimes the constraints made by the numbers placed are not enough for a solution, so you apply search.

For a guy who is famous for a book that makes all AI problems look like search, that does not sound so strange.

When he reaches the search phase, he considers implementing strategies, but concludes that search will work beucase:
- the space is not so big
- search is complete, while strategies may not be, so its easier.

This questions are of second nature to someone who implements search algoritms.

I think that the main difference is that Norvig already *knew* how to solve it.

Lucio

Anonymous said...

Lucio Torre's comment "I think that the main difference is that Norvig already *knew* how to solve it" is spot on.

Others have noted that Ron exposes his thought processes whereas Peter's writing is like a textbook excerpt. I wouldn't be surprised if Peter's actual thought process was quite close to that textbook-like presentation, given that he has written textbooks in which he applies the same techniques to similar problems.

Nested said...

I think http://devgrind.com/2007/04/25/how-to-not-solve-a-sudoku/ makes the right point that TDD is not the right tool for the job trying to develop an algorithm. You can also read my reply on my own blog, which is longer but makes the same point! :)

Anonymous said...

@joe

someone said

"It's like comparing guitars by making Jimi Hendrix play one, and the teen next door the other. The comparison is in fact interesting, but the conclusions are all wrong."

and you (joe) said

And does your teen next door also go around claiming to a be a guitar God? Does he write books on guitar playing and presume to tell other guitar players how to play? Does he have a "guitar playing method"?


BWAAA HA HA HA HA HA HA HAHAA!!!!!

ROTFLMAO!!!

joe, that was excellent!!!!!!

>At least Ron Jeffries came up with a working solution, not being a mathematical oracle or anything like that.

he did? As far as i can see he stopped halfway and wandered off into programming shotgun images or something equally crappy, all the while proclaiming the superiority of agile/tdd?



BWAAAAAA HA HA HAHA HAAAAAA!!!!

Made my day! Thanks!!
(Tears of mirth ...)

Anonymous said...

Jeffries doesn't claim to be a great programmer; in fact he claims the opposite. His main claim is that TDD helps him create working programs, and it does. The sudoku challenge is kind of an extreme case showing where the limits of TDD are.

Meanwhile, Norvig is an expert in sudoku type problems, and he employed a tool (backtracking search) which Jeffries probably didn't know well. If he had, he could have used TDD and come up with an elegant solution.

I suggest people analyze the problem at a high level to find a strategy, then use TDD to implement that strategy.

Ravi said...

"His main claim is that TDD helps him create working programs, and it does."

For some value of "working" yes. The question is whether that is good enough. The answer as demonstrated by his code (and his TDD driven thought process) is plainly no.

Then there is the question about a self acknowledged bad programmer (which he is if "Jeffries doesn't claim to be a great programmer; in fact he claims the opposite" is true) evangelizing a programming methodology, but we won't get into that. It is a free world.

The claim that TDD allows the design to "fall out" of the test_code_refactor_repeat cycle is what is being questioned here.

"The sudoku challenge is kind of an extreme case showing where the limits of TDD are"

Correct. But sudoku is "extreme" only wrt TDD as a design technique. Algorithmically it is only a moderately complex problem. The key is that it illustrates perfectly how limited a tool TDD is(as you correctly point out).

"Norvig ... employed a tool (backtracking search) which Jeffries probably didn't know well."

Again the tools Norvig employs are less important than the calibre of his thinking. He explicitly uses analytical,algorithmic, mathematical **thinking** while Ron stumbles around with his "TDD". It is not as simple as knowing or not knowing a particular tool.

"I suggest people analyze the problem at a high level to find a strategy, then use TDD to implement that strategy."

Excellent advice, as long as it is clear that you can create elegant, powerful programs can be created without TDD,as Norvig demonstrates. The value TDD adds *in this context* is fairly marginal.

But yes, deep analysis + tdd is a possible path.

uncle bob said...

The old master sat in the corner rotating his wrist back and forth, back and forth. His concentration was total. He seemed oblivious to the world around him.

A young black-belt, the kind that think they actually know something, sneered as he talked with his compatriots. "The addled old fool. Why does he move his wrists so." The gaggle laughed discretely and rolled their eyes knowingly.

Ravi said...

Argument by analogy?
:-)

Sadly enough all old men are not masters of anything.

Some addled old men are just addled old men.

Worse are addled old men rotating their wrists who pretend to be Karate masters and even run dojos and have many disciples, but crawl home, dragging their broken legs behind them spitting blood after meeting some real fighters.

Withered ancients trying to pretend a mastery they don't have and desperately hoping that passersby will notice their wrist rolling and conclude it is some mystic fighting move are pathetic.

Grey Hair by itself is not a badge of merit.

Especially as in this case, when the code (or karate move) is out there for everyone (including the young black belts and the gaggle) to see (and judge).

Nice try though ;-).

Josué said...

May be I am wrong, but I think Ron showed his process from the very beginning (without any deep studying of the domain problem ). It seems to me that Norvig show only the solution, not all the mistakes he did in the way.

In my opinion, the Soduku is the kind of problem where a deep knowledge of the domain (complex math) is more important than the methodology (TDD) utilized to solve the problem. But, in real life , how many times did we found problems like that in normal development? As an equivalent, how many times we use assembler in the place of OO?

One mistake that happens with people is to think that there is silver bullets and only one thing must resolve all cases. The only silver bullet I know is to be good to go to heaven ( I hope :) ). As any other kind of thing, TDD is not silver bullet. But in my opinion, it is very very very very good. An analogy, OO is good? Well, I think so. But there is cases that we can´t not apply it (example, optimized calculus do graphical devices, where we will need the assembler help ).

If in the soduku example one reached the solution and other no, it proves nothing about the TDD process. If we want to test TDD, we have to experiment development with various teams, ones using TDD and other no, and try to isolate the other variables( the teams with more or less the same skill to develop, the same knowledge of the problem domain , the same number of members, the same schedule, the same language etc.). Of course isolate the influence variables is not easy. But a large amount of experiments could show some tendency.

With equals conditions, I bet that the TDD teams will be closer to the solution than the other. And I am speaking as someone who one day did not used TDD and nowadays is using.

By coincidence, in my graduate work I am doing a summary about papers that does this kind of study, and the only variable that was worst to TDD was the time of development in one case. In that one TDD takes 16% time longer (but the TDD team will have tests to the biggest phase of software: maintenance. And the other no). In compensation there is another study were TDD was 50% faster. There is one case where the only team that complete all the requirements requested was the TDD team. Of course, it proves nothing but with time and with more experiments we could have a good idea about the practice.

Well, personally I don´t need of any prove because I know how good developer I was before TDD and how good I am now with it.

Ravi said...

"With equals conditions, I bet that the TDD teams will be closer to the solution than the other"


Josue, here "I bet" === "I believe".
Believing is one thing. Lots of people "believe" in TDD. Showing belief to be valid is another, which is what this whole discussion is about.

Anyway thank you for your comment.

Cristache said...

I met Ron in person. He might look like an idiot, and even talk like and idiot, but make no mistake about it: he is an idiot.

What I think is the most dangerous facet of TDD and Agile/Scrum is that it lulls people into the false belief that even if they are morons, they can still write good code because they follow the "correct process".

I have seen some morons at my work that write tests to test the tests that tests their tests in some hope that Goedels' theorem will go away. I agree that the opposite (no process, no test units) is hell. But here's the thing: test harnesses are to software like scaffoldind to building. If you are inclined to read about how Brunelleschi went to overcome obstacles, you may see that there is value in props. But only if you are good, to begin with.

Ron Jeffries (and it applies to his retared followers as well) is just an old fart with no talent for programming whatsoever. Blindly following Jeffries puts one in my "fire tomorrow, if I can" book. I can afford to say it. I wrote my own C++ debugger for Linux, and oh my, I did not use agile, nor TDD (but I do have a suite of automated tests that saved my bacon more than once).

And I am just super-lucky to have bosses in my day job that have a sixth sense for the kind of bullshit that the agile crowd is pushing, and have been able to steer clear of the Ron Jeffries putrid "charisma" so far.

I am with you man, thanks for posting.

Anonymous said...

" ...addled old men rotating their wrists, who pretend to be Karate masters and even run dojos and have many disciples, but crawl home, dragging their broken legs behind them and spitting blood after meeting some real fighters...."


BWAAAAA HA HA HA HA HA HA HAAAAAAAAAA!!!

I've never seen a truer description of these "agile alliance" idiots! They should stick to "process consulting".

That was REALLY funny!

Good work dude!

Dibs on Muad said...

@uncle bob (and I really hope you are not *the* uncle bob)

The Master and his gaggle
--------------------------
An old master goes on stage, demonstrating how to walk a tight rope. He fails, fails, fails, fails and fails... even with a balancing rod. Then he gives up and starts rotating his wrists, hoping desperately no one will ask him why he failed.

Another old master traipses across the same rope whistling "Waltzing Mathilda" and juggling 7 firesticks doing a few somersaults with very few steps and landing perfectly on the swaying rope.

The former old master can keep rotating his wrists oblivious of other Masters around him.

The gaggle, like all gaggles can close their eyes or choose to learn.

Simon Lin said...

After reading all the comments, I have to say that it’s a stupid discussion. I have at least two reasons.

First, Sudoku is not the appropriate topic to base the comparison on. It’s the kind of problem that requires relatively complex algorithm but has well defined requirement. In this case, the requirement is: Solve the Sudoku. But if you ask the majority of business application developers what kind of requirement they get, the answer will most likely be something like “Make it work”, “I can tell you. But don’t expect the same answer six months from now.” or “Requirement? We are not sure”. That’s the challenge the main audiences of TDD are facing. Whoever says you don’t need TDD in this kind of situation must be either a genius or insane. No, let me rephrase that. They are just insane.

Second, Ron Jeffries’s example is terrible. He seems like the perfect guy to reference if you want to badmouth Agile and TDD. He made it sound as if TDD eliminates the need for upfront design. That’s not what we do! Brainstorm/design sessions happen a lot more often in an Agile team than in a traditional development team. TDD is there to insure that we don’t write unnecessary code and all the code we write are covered by tests. These tests are usually white box tests. We already know how we want to implement it. We just want to make sure it works and continues to work over time. There are, however, times when we have to write black box tests. That’s when we were given a chunk of legacy code that nobody knows how it’s supposed to work. We have no choice but to gather the up-to-date requirements, write test to demonstrate them and refactor/rewrite the legacy code to be readable and working.

That’s my take on this debate. Ron Jeffries is not a good representative of Agile. There are better guys out there.

Ravi said...

@Simon,

"But if you ask the majority of business application developers what kind of requirement they get, the answer will most likely be something like “Make it work”, “I can tell you. But don’t expect the same answer six months from now.” or “Requirement? We are not sure”. That’s the challenge the main audiences of TDD are facing. Whoever says you don’t need TDD in this kind of situation must be either a genius or insane. No, let me rephrase that. They are just insane."

Beat your wife much?

You are reacting to things no one ever said. No one, either in the original post or any of the comments, claimed that TDD is inappropriate for certain kinds of enterprise projects or that TDD is a "bad" tool , never to be used, or that Sudoku is typical of what a typical "business application developer" faces.
These issues are orthogonal to the point under discussion.

Besides, there is a subtle difference between having good coverage with unit tests and using unit tests to drive the design. The claim that the latter, TDD, "solves" unclear requirements is just that - a claim, by you in this case.

Good unit test coverage certainly helps the design to evolve by making refactoring safe. Whether development should be test DRIVEN is a more subtle question.



As to Ron Jeffries being a bad example, good point. You might want to try saying this on the extreme programming list :-).

What does it say about the state of the agile "movement" if he is a "guru"?
:-)

Simon Lin said...

@Ravi,

I might be reacting to things that no one ever said. But some of the comments up there are to the point of attacking a certain person and community. I don't those who wrote them have any respect to Agile or TDD.

I think development should very much be test DRIVEN. Design, on the other hand, should not be. From my understanding and experience, test driven simply means we write the tests before we write the implementation code. Through this practice, we make sure that we try our best not to write any useless code and not to miss any test scenario. Once again, test does not drive our design. We even list all the test cases we can think of at the time before we write any test.

I've never been to any extreme programming list. There are a lot of people out there who claim to be Agile but in fact have not a single clue what it is. But there ARE also the group people who understand and love Agile. Unfortunately, they usually don't like to talk too much.

Ravi said...

@Simon,
I keep a fairly "open" blog and I don't wantt o edit what people say as long as tehy are sincere. So , yes some of those comments can indeed look like "attacking". That is fine by me. I am a big believer in the clash of ideas and the regular slaughter of sacred cows.

"I think development should very much be test DRIVEN. Design, on the other hand, should not be."

fwiw this is totally consonant with my experience.This is how I (try to) develop these days. Of course the future may show me a better way.

ananthd said...

The following is the list of all known problem solving techniques, in order of decreasing effectiveness:
1) Knowing the solution to the problem
2) Knowing the solution to a similar/related problem
3) All other techniques.

Most of the current 'methodologies' fall under 3). They often don't help you in solving the problem at all.

As a corollary there are two kinds of engineering:

1) Orderly: In this kind, you know /understand the problem space. You r particular project may require some variation on the design that applies to this problem space. Eg:
building bridges, compiler for a new CPU.

2) Exploratory: You don't understand the problem space. Your attempts at a solution are unstructured.

Norvig obviously recognizes the problem as being part of two other well known problem classes. His attempt is very reminiscent of orderly engineering.

Jeffries is a textbook example of
exploratory engineering.

This is what pisses me off the methodology-hype train: Almost every body claims to have a panacea(UNIVERSAL MEDICINE). Ultimately, they don't apply to any problem space well.

I find it sad that so many developers unquestionably accept the latest FAD. If we are to mature as an engineering discipline we need to spend time doing more taxonomy/analysis/theory into problem domains. Compiler construction, text processing, search are excellent examples. I know most of the enterprise software business is supposed to arbitrary, ill-defined etc., but there is very little attempt to codify/internalize various domains from an IT/non-IT perspective.

Even design patterns, that SACRED COW is more about the solution space than the problem space.

As far as I know, Michael Jackson(the software guy, not the singer)'s work has always emphasized the problem:

JSP, JSP(Information systems problems of the classic, mainframe era)

Problem Frames - more recent, more modern.

Sryn said...

Hi all,

I just read the top posts and I'm not sure whether this is a good place for this, but, here goes.

I'm trying to design in Flash a Sudoku creator. However, I'm stuck at a point where, after a while, the square I'm about to fill has run out of possible numbers to fill it with. Both a random choice of squares to fill and a top-to-bottom approach failed me.

I started with a simple algorithm, i.e. fill this square with a number that is not already chosen in the same row, column or 3x3 grid. That failed.

I then elaborated on that by filling that square by biasing on a number that has been chosen in an adjacent row, column or 3x3 grid. E.g. Suppose A1 has 1 in it. Then the next randomly chosen square D2 has a bias to choose 1 as well, but not necessarily 1 is chosen. That too failed.

Finally, I tried to limit a number to one 3-column in the same 3-row or 3-row in the same 3-column. E.g. Suppose A1 has 1, then D1-D3, G1-G3, A4-C4 and A7-C7 will not have a 1. This failed as well.

I'm thinking of back-tracking but haven't implemented it. Designing Sudoku seems to be difficult as I haven't come across any 'rules' on its design. I'm trying to think thru this on my own but am stumped.

Any suggestions are helpful. Thnx in advance.


Sryn

Anonymous said...

Here is a paper that details the algorithm for solving Soduku in amy N x N puzzle, where N = m*m. The small 'm' is the submatrix. If m=3, then N=9. The author of the paper, Prof. Amy Langville, has already developed a Matlab code to solve her N x N soduku puzzle. The user just have to specify 'm' at the beginning, such as m = 6, and the algorithm will generate a N x N or 36 x 36 matrix soduku game. The author derived her algorithm using Integer Programming.

"An Integer Programming Model for the Sudoku Problem"
http://www.cofc.edu/~langvillea/Sudoku/sudoku2.pdf

Malab codes is available from the following link. You need Matlab ver 7, to run the code.

http://math.cofc.edu/langvillea/

Currently available Soduku, N = 9 (m=3), that is the soduku game is a 9 x 9 puzzle. The algorithm described above is a generalization to any N x N, eg, if m = 4, then the puzzle becomes a 16 x 16 one, which is more difficult.

Sanjoy Das said...

Very inspiring.

I have been trying very hard to go from a mad alchemist to deep systematic thought myself. I just hope I'm on the right path. :)