The Sudoku Affair

Hilarious post. I recommend people read to the end<p>&gt; If Jeffries started with a different core representation, then it&#x27;s likely his subsequent design decisions would also change. The bookkeeping for constraint propagation might push him towards Norvig&#x27;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.<p>&gt; But Jeffries isn&#x27;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&#x27;s maxim of &quot;many more much smaller steps.&quot; He is only interested in designs that are reachable through a series of small, discrete steps.<p>Jeffries has radicalized me. This sort of puttering-around with &quot;incremental design&quot; 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

Good article. For me, this is the fundamental concept:<p>&gt; 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.<p>I wish more people would be circumspect about the genre of problem they&#x27;re trying to solve and how their framing railroads them into a particular type of solution that might have a better method.

It is interesting to basically critique a series of blog posts like its a film.<p>But re: design vs. increment, I do think incremental TDD is pretty useful in domains where you have low confidence that you <i>could</i> 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?).<p>The two quotes that got me are<p>Jeffries:<p>&gt; So I try to make small decisions, simple decisions, decisions that will be easy to change when, not if, a better idea comes along.<p>Norvig, about Jeffries:<p>&gt; He didn&#x27;t know that so he was sort of blundering in the dark even though all his code &quot;worked&quot; because he had all these test cases.<p>I fear someone could say this about me, about almost everything I&#x27;ve ever built. I guess something like &quot;I just kept crawling and it just kept working!&quot;

As someone who wrote 60 pages of design for a new VCS before writing a single line of code, I appreciate this post.<p>Design is crucial. <i>The optimal time</i> for that design may be different for different things, but I do know that incremental design can, and often does, fail.

Sadly, link isn&#x27;t loading for me. I&#x27;m assuming this is the attempt to TDD into a Sudoku solver?<p>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.<p>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.<p>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.

I once wrote a Sudoku solver in SQL in an afternoon because I was playing a Sudoku (a very newb player at that time) and it spontaneously occurred to me that all I was doing was a join or anti-join query repeatedly.<p>My data model was X,Y,V. Nothing nullable. Separately you need a table (possibly generated on the fly) of range 1 to 9. You wind up joining that a lot.<p>The whole program consisted of running INSERT INTO ... SELECT ... in a loop until 0 rows were inserted, indicating you were either done or you hit a point where no cell had a single solution. I&#x27;ll spare everyone the rest of the details.<p>Incomplete, I know, but it fired the neurons, particularly with respect to the utility of the EXISTS expression in SQL.<p>I had no idea about things like &quot;naked pairs&quot; at that time, but I&#x27;m sure I could extend it to suport that.<p>It&#x27;s interesting that if I translate that to a more traditional language, I independently came up with what is a cousin to Norvig&#x27;s solution. I sure don&#x27;t have his background, in fact my background is probably closer to Jeffries.<p>The main difference is that Norvig pre-enumerates all 9 possible values for all 81 cells then sieves them out, whereas my SQL constructs the 9*4 matrix from a temporary range 1..9 table, discovers the &quot;must be&quot; values, inserts those, then just repeats the process. Basically I&#x27;m Map&lt;Coordinate, Integer&gt; whereas Norvig is Map&lt;Coordinate, Set&lt;Integer&gt;&gt; and the algorithm is slightly different.<p>My experience agrees with the author&#x27;s. Incremental design does not work. Prototyping and being willing to throw away your prototype and do something wildly different has always been the better approach in my experience.<p>You wouldn&#x27;t believe how many less experienced engineers I help with problems by coming in and approaching the problem with a fresh set of eyes. It takes years to build the skill and willpower to incinerate days or weeks worth of work in favor of an alternative solution you can write in an afternoon. But it&#x27;s not a waste! If you gained enough insight from doing it the wrong way to be able to write it the right way, then you maximized the value of your time. It is actually a waste of your time to keep iterating on a fundamentally flawed design.

Not trying to defend Jeffries, but Norvig&#x27;s solution despite looking so elegant and in hindsight seemingly the obvious solution by everyone here, is not at all obvious, and I doubt someone without prior experience in exploring the problem area would come up with it. Just no way.

Slightly off topic, but this made me think of an example from the PuLP (Python Linear Programming library) that solves a sudoku using LP constraints.<p><a href="https:&#x2F;&#x2F;coin-or.github.io&#x2F;pulp&#x2F;CaseStudies&#x2F;a_sudoku_problem.html" rel="nofollow">https:&#x2F;&#x2F;coin-or.github.io&#x2F;pulp&#x2F;CaseStudies&#x2F;a_sudoku_problem....</a><p>One nice thing about this approach is that by adding each solution in as a constraint and re-running, you can exhaustively enumerate all possible solutions for a given puzzle.

This makes me think of an example from the PuLP docs of solving sudoku using constraint based linear programming.<p><a href="https:&#x2F;&#x2F;coin-or.github.io&#x2F;pulp&#x2F;CaseStudies&#x2F;a_sudoku_problem.html" rel="nofollow">https:&#x2F;&#x2F;coin-or.github.io&#x2F;pulp&#x2F;CaseStudies&#x2F;a_sudoku_problem....</a><p>This example helped me enormously in developing my understanding of how to use binary variables in an LP solver

Norvig is a world level genius and he outdid Jefferies because of that. No shame in losing a basketball match to LeBron James.

Since Sudoku is a logic-based game, why not use Prolog to create a solver? Example of Prolog code can be found here, <a href="https:&#x2F;&#x2F;www.metalevel.at&#x2F;sudoku&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.metalevel.at&#x2F;sudoku&#x2F;</a>.

A practical programmer will use a SAT solver. And bang!, problem solved! :)