The Sudoku Affair
19 comments
·February 5, 2025abetusk
Good article. For me, this is the fundamental concept:
> Both Norvig and Jeffries are genre programmers; they have spent most of their career solving a specific kind of problem. And that problem, inevitably, lends itself to a particular kind of solution.
I wish more people would be circumspect about the genre of problem they're trying to solve and how their framing railroads them into a particular type of solution that might have a better method.
gavinhoward
As someone who wrote 60 pages of design for a new VCS before writing a single line of code, I appreciate this post.
Design is crucial. The optimal time for that design may be different for different things, but I do know that incremental design can, and often does, fail.
jcranmer
One of the most useful skills I gained from programming competitions is the ability to write and debug an algorithm in my head. And I suspect your 60-page design document was written by essentially doing the same thing: coming up with a prototype design, and mentally testing it against the use cases to figure out if the design is workable, and committing the notes to paper only after you confirmed that it worked in your head.
gavinhoward
Interesting. Perhaps that is what I did.
I did do that to design the UX, but for algorithms, I am not so sure. I am really bad at coding competitions, for example.
aidenn0
Was that for Yore?
gavinhoward
Um, yeah. How do you know the name?
I have never mentioned it by name, I think. Only linked to it occasionally.
Edit: Another reason I am surprised is that Yore became its name only a few months ago.
Archit3ch
Your method is still incremental design, unless you started at page 1 and stopped at page 60.
gavinhoward
That is, in fact, what I did.
But then again, you know I was referring to Jeffries' SOP of designing while coding and refactoring incrementally.
frankfrank13
It is interesting to basically critique a series of blog posts like its a film.
But re: design vs. increment, I do think incremental TDD is pretty useful in domains where you have low confidence that you could come up with a good design. If you asked me to implement an LLM today, 0% I could design a good one. But given enough time I could slowly start to implement one (maybe?).
The two quotes that got me are
Jeffries:
> So I try to make small decisions, simple decisions, decisions that will be easy to change when, not if, a better idea comes along.
Norvig, about Jeffries:
> He didn't know that so he was sort of blundering in the dark even though all his code "worked" because he had all these test cases.
I fear someone could say this about me, about almost everything I've ever built. I guess something like "I just kept crawling and it just kept working!"
copypasterepeat
The way I think of this is that there is no shame in Jeffries not having as good and intuitive grasp of the problem as Norvig. After all, this kind of problem is almost tailor-made for Norvig's skill set. Like many of us who haven't done a lot of work in this space would do, Jeffries spends a lot of time early on just exploring the problem space. He starts with a seemingly intuitive (naive?) data structure and goes from there. So far so good. No shame in any of that. All of us have been in a similar situation. I think that the key moment comes at blog post number 12. As the author of this post describes, this is where Jeffries basically recognizes that his approach needs to radically change and where a lot of people would throw away what they have, it having served the function of helping one understand the problem, and start from scratch with different assumptions, data structures, etc. Jeffries didn't do that, probably because he firmly believes in the TDD dogma and probably because he felt pressured to make this work, since he way publicly working through this. That's where Jeffries goes wrong. He should probably have admitted that in some cases you should just start from scratch instead of tinkering at the edges of something that's clearly suboptimal.
karmakaze
I do something similar where even for something substantial, I'll start out with "what's the simplest thing that might work".
Of course with past experience, my first 'simple' thought is usually quite practical or sensible. In the same way it's hard to invent an inefficient algorithm that does no useless busywork--we've wired our brains toward good.
spoonjim
Norvig is a world level genius and he outdid Jefferies because of that. No shame in losing a basketball match to LeBron James.
mjd
Leaving Norvig out of it, it seems to me that there is some shame in taking a reasonably straightforward problem like this one, thrashing around with it for months or years without producing an effective solution, and then being unable to see that your methodology wasn't working.
If the account is accurate, this Jeffries guy wasn't getting the ball through the hoop, whether or not LeBron was around.
taeric
Sadly, link isn't loading for me. I'm assuming this is the attempt to TDD into a Sudoku solver?
Sucks, as it is largely a dunk on the author. It really is a sobering experience, to attempt something like that and use what are advertised as good tools, only to fall flat on your face.
I think what people often fail to appreciate is if you see ANY strategy work, it has almost certainly been rehearsed. Many many times. Even when you are doing something where you are using the exact correct tools, for it to work smoothly pretty much requires rehearsal.
And this is exactly why you do gamedays for how to react to failures. If you have not practiced it, then you should not expect success.
aidenn0
It's specifically about the limits of incremental design.
TFA's thesis is roughly that incremental design dooms you to a local maximum:
Since Jeffries (the TDD/Sudoku guy you seem to be aware of) starts out with a suboptimal representation for the board, there is no small change that can turn the bad code into good code. At some point along the line, he makes motions in the direction of the design that Norvig used, but as there is no incremental way to get there (maintaining two representations was a dead-end since it hurt performance so much), he never does.
taeric
Thanks! Annoyed that the link still isn't loading for me.
I'm curious on the thesis. I'm assuming "locked in by tests" increments are the problem? I'm curious why you couldn't treat this like any learning task where you can take efforts that are effectively larger steps to see where they can get you?
I should also note that I am not clear I understand how bad of a representation of the board you could get locked with. I got a working solver years ago with what is almost certainly a poor representation. https://taeric.github.io/Sudoku.html
Hilarious post. I recommend people read to the end
> If Jeffries started with a different core representation, then it's likely his subsequent design decisions would also change. The bookkeeping for constraint propagation might push him towards Norvig's relational approach to the rules of Sudoku; rather than continually recomputing the rows, columns, and boxes, he could simply have a map of each cell onto its peers. He could distill every lesson of the previous posts, creating something simpler and faster.
> But Jeffries isn't in the business of starting over. He not only believes in incremental design, but in using the smallest possible increments. In his posts, he regularly returns to GeePaw Hill's maxim of "many more much smaller steps." He is only interested in designs that are reachable through a series of small, discrete steps.
Jeffries has radicalized me. This sort of puttering-around with "incremental design" is too pervasive in the corporate world. In software we have the luxury of rethinking from first principles, and we must use it. Death to MMMSS