Reflections on Sudoku, or the Impossibility of Systematizing Thought

That’s pretty much just Feynman’s algorithm but with more steps:

1. Write down the problem.

2. Think real hard.

3. Write down the solution.

But Uncle Bob said that if I follow his TDD process by rote then my code will automatically attain good design! /s

I had a similar reaction to Jeffries' Gilded Rose solution in Ruby [1]. After 13 blog posts he ended up with something [2] a lot less elegant than Victor Shepelev who also used TDD but came up with a one-shot solution [3]. Just like Norvig with his Sudoku solver, Shepelev codifies the rules as a set of relationships. He writes:

  When rereading the requirements, we might notice that all conditions can be described as a simple dependency (name, sell_in) => change of quality.

  The most natural representation of this in the modern Ruby would be pattern matching.

2. https://github.com/RonJeffries/gold-1/blob/master/wrappers.r...

3. https://zverok.substack.com/i/149071314/the-implementation

The smart way to write a Suduoku solver these days is to formulate the problem for an SMT solver, which is specifically intended to solve that kind of problem. The SMT solver already has tests, so you don't need to write tests.

When I wrote my first Sudoku solver I started out with a solver that solved easy problems where, at each step, there was some square with only one possible solution. That didn't work for harder problems where you have to guess. Eventually I realized that you could just pick any square, try all the numbers, and recursively solve the remaining problem. This works no matter which square you pick but it is faster if you start with the square that has the minimum number of choices available.

If you write a solver haphazardly like that you're very likely to wind up with two or more copies of the board because you're not sure what kind of queries you'll need to do. If you understand the problem, you won't.

The role of the tests is complex here. In principle they could help you refactor your data structures, in practice the sheer bulk of them could reify the data structures you have and add to the burden of refactoring them. A code-golfed version of the solver could be smaller than the tests.

Writing a chess program I found testing was a challenge. Move generators are easy to test, evaluation functions are easy to test. A decent alpha-beta search with transposition tables, killer heuristic and such is not so easy to test in terms of unit tests. Before I'd have the program play anyone I'd run a set of integration tests based on

https://www.chessprogramming.org/Bratko-Kopec_Test

I think of a system I inherited that had a part that was prone to race conditions, part of vanquishing the race conditions was writing a "super hammer" test that would run a few 1000 threads for about 40 seconds. Maybe it still has race conditions, but they won't be triggered often.

Long-running tests like that aren't really unit tests but for some problems they're the right tool. In general though long-running tests are a big problem because slow builds are a problem.

> incremental search from a simple start point towards a solutions

Good point. More broadly than just TDD, we might characterize an "easy" problem as one where the surface from conception to completion is broadly visible and there's a logical set of steps (i.e. "differentiable"). Or maybe "easy" is I can see the full set of steps immediately, and "tractable" is that I've got a good guess.

But the set of steps you can take is highly dependent on your knowledge and skillset. For example, if I know how about completing the square, then deriving the quadratic equation is a basic algebra exercise. If I don't, then I might struggle for a long time before I manage to discover that key insight.

I'm sure there are coding methodologies which can lead to better or worse results, but they augment knowledge or skill, they don't replace it.

Obvious counters aside (like syntax issues or whatever) I have almost the opposite intuition. Most of my programs start out as partial solutions to a problem I don't fully understand, and it is only through interaction with the environment (users, or other machines sometimes) that the edge-cases and incorrect assumptions become clear. These programs have a lifecycle of refinement to deployment to analysis to refinement and repeat. At each step they are workable or almost-so, and over time the solutions start to map the domain more correctly. Sometimes (like in business) the domain is evolving simultaneously!

(can give examples if anyone's interested but this is getting long already)

I imagine this wouldn't work so well for hard algorithmic stuff where there are mathematical properties you need to be aware of and maintain. But I find most problems I solve are more organic - people are quite resilient to fuzzy boundaries, so people-facing stuff tends to have that property too. There's a large fuzzy space of "workable solutions", so to speak, and navigating that space is kind of inevitable if you want a quality solution.

Perhaps I'm just not intelligent enough to one-shot that kind of stuff =P

I always use the following analogy:

I f your customer orders a feature, you implement all the code, just the button to call the feature is missing, then you delivered nothing.

If you just add the button to the program, but implement nothing else, you delivered the feature. It's just still buggy.

> Isn't there a less-conceptual (but still conceptual) problem that correctness of software is commonly abrupt rather than continuous? You don't get a series of almost-right programs gradually approximating the right program, you have a correct program and variations on it may fail completely.

I consider it to be plausible that such a topology could exist (at least for many situations). The problem rather is that such a topology would likely behave very different from users' expectations.

Yes. The difference between "A program that does what you want" and "A program that crashes on startup" can be one character.

Working large systems overwhelmingly started out as working small systems, with working systems all in-between.

This is not an endorsement of TDD, but shows that there is a correctness path from small to large, without usually needing to take large leaps in-between, and taking such a path tends to be the most successful strategy.

I think there’s an analogy in the dumb management dream that there’s a process by which you can replace these expensive skilled workers with cheap unskilled idiots and still get great results.

Another variation: the magic process that lets you get great results from people who don’t care.

Excellence doesn’t come solely from process. The benchmarks of great process with unskilled workers who don’t care is fast food, and this product is consistently mediocre. Consistency is good but consistent mediocrity is an unworthy ambition in many fields.

NASA is massively process driven but they get people to space and back, and the people in their process are highly skilled and care deeply.

Larry Wall, inventor of Perl, used to say (and probably still does) that complexity has to go somewhere. If you’re solving a complex problem then either it’s a simple program with complex tools, or a complex program with simple tools.

That’s really stuck with me. The art of library, framework, language, API design is to provide a set of tools — if you make simple tools then complex problems become complex programs. And if you offer complex tools, complex problems can have simple solutions. And people will gripe at you for all the punctuation for decades. :)

But the complexity exists and can’t be wished away. Which is kinda your point too. Thanks for writing!

I'd be somewhat more charitable and say that it's an attempt to break down a big, complicated problem into chunks that are more easily digestible. The problem I think Jeffries ran into is that Sudoku and the search space is essentially atomic, where breaking it down further isn't helpful, while seeming like it's simple to break it down to row, column, and box and work from there.

There's the principle "never let them see you sweat" and if you're trying to convince people of an idea like TDD you never want to be seen floundering. You don't publish anything about your sudoku solver until you've succeeded at it. Otherwise you're just proving "TDD sux" which, for all "X sux", TDD sux more than X.

It was bound to happen to someone.

I respect he's open about his work and struggles, and it's cool he's programming at 86, but it does seem like his approach makes it harder for him rather than easier.

For example with the bowling score calculator, it's great to start with some tests, but I think he then marched towards a specific OOP formulation which obscured rather than clarified the problem.

I won't argue with the idea whether you can test a particular program produces a result (we aren't so interested in programs that run forever in any case). Your observation of the origins of TDD makes sense in this regard: there may be domains where the TDD approach is more useful, but it's not a generic panacea, and assuming it is can lead to sadness.

My point was more about arbitrary programs and tasks. In general, I don't think there's any particular process you can follow that, in effect, reduces programming or math to a checklist. I'm sure there are techniques that can help structure many problems but they're necessarily fairly general e.g. "think about the problem, take a nap, think about it some more".

What I was hoping to highlight was more the danger of trying to hill-climb without having the right set of skills, thus assuming you can solve a problem by following a particular pattern.

To give an example, I remember trying to derive the quadratic equation when I was young, and no amount of algebraic repositioning was going to help me unless I know how to complete the square! But once that type of trick is in your toolbox, you can begin to solve all sorts of other problems.

Even the bowling calculator can become hard if you don't know what your doing, not because TDD is bad or a wrong way to do things, but because you don't know how to reason about your program. Even bowling has 12^13 outcomes, with a bunch of silly special cases if you approach it the wrong way. Thus a truly naive approach might lead you down a weird direction.