Reflections on Sudoku, Or the Impossibility of Systematizing Thought

I reflect on the Entscheidungsproblem how it relates to Sudoku solvers. It's a little weird..

N.B. I've gotten some flack for overstating the relationship of Entscheidungsproblem to real-world problems. Mea culpa. I wanted to convey 2 things: formalizing thought - thinking precisely - is hard, and there's no general mechanism to avoid it. The related point is that you can't hill-climb the task of programming, and attempting to do so can lead you in circles. There's no simple & efficient way to turn a vague idea into reality. Sorry.

The other day, to no one's surprise, I was fumbling over a programming problem. This wasn't anything satisfyingly algorithmic, but more the thing where you're evaluating a million questions on "how should I structure this system?". While I'm no design purist, I like to at least make an attempt at sketching out the problem space and think through options before I just start coding something. My rule of thumb for this is, let's call it the "10% rule" - make sure I try to think hard about a problem for 10% of the time before I start playing around with code. Writing code helps clarify many things but it's also easy to get stuck in local minimaI have the same problem when writing text, like this blog post. Put me in front of an editor and I'll pointlessly recraft sentences instead of getting the thing finished. . This rule helps keep me from getting lost too early, but I often think about whether I could do better.

I'd like to say I have a systematic process I apply here. I don't. I think over one idea, then another, writing down my thoughts, but it's always hard to feel like you're making a lot of progress. It's honestly frustrating. I often wish I could "systematize" it somehow, applying some rigorous method and march towards the solution. Could I become one of those magic people who just sit down in front of a problem and watch it decompose in front of them?

Over time I've accepted that is impossible. There is no person, no process, which can systematize thought. Millions of math problems elude Terence Tao despite his brilliance.

Now I see these differences in aptitude as having different sets of mental tools at your disposal. The more tools you have, the better tools you have, and the better you are at applying them, then the better you get at certain problems. Maybe your background makes you better or more interested in different tools. But we can all learn new tools, and get better at the ones we have.

This is all kind of murky and unsatisfying though. Wouldn't it be nice if you just had a general method you could apply to solve everything? What happens if you think you have a method to solve all problems?

The Sudoku Affair

A few months ago I read Zach Tellman's fascinating article on the Sudoku Affair, in which he revisited Peter Norvig & Ron Jeffries very, very different attempts to produce a workable Sudoku solver. (I highly recommend reading the original article as well, as Zach's deep analysis of Ron Jeffries attempts at producing a Sudoku solver is fascinating).

Some background: Ron Jeffries made a career advocating for test-driven development (TDD) and extreme programming. Peter Norvig is a research lead at Google and author of many papers and a few books on AI. As you'd expect, this leads to different approaches to problems.

Ron Jeffries attempted to solve Sudoku by approaching it "rigorously"No offense intended, but just being clear this isn't like mathematical rigour but more of an applied philosophy. from the perspective of TDD. He outlines the problem, writes a test case and begins to iterate, adding tests and refactoring. In the initial set of posts, he can't get to a real solution despite many hours of effort. He then revisited the problem 20 years later, and in the end spends 50 posts writing about the process of building a solver. At some point, he finds code from another site and starts to bring that into the fold. He eventually gets to a solution, though at that point I honestly have trouble figuring out how much TDD had to do with the process.

Peter Norvig takes a different approach, analyzing the high-level problem and then breaking down the data structures and outlining the solution in the course of ~20 lines of code. While his code might be a bit dense to follow initially, the way he approaches the problem and pre-builds data structures makes "testing" trivial. His test for validity is part of the search condition for his program. It's hard not to appreciate the systematic nature of Peter's approach: define the problem, look through your toolkit, apply the relevant tools, success. Of course, Peter has an advantage that he's written books about related techniques.

Ron Jeffries attempt definitely didn't make me excited about TDD, I at least respected that he didn't try to hide things after the fact.

Many people have commented about this over time, with lots to say about TDD and programming. In Peter Siebel's post on Unit testing in Coders at Work even Peter Norvig chimes in, indicating he's not "anti-test", but that tests don't fix the underlying issue of "knowing what to do."

Then bloggers were arguing back and forth about what this means. I don’t think it means much of anything—I think test-driven design is great. I do that a lot more than I used to do. But you can test all you want and if you don’t know how to approach the problem, you’re not going to get a solution.

On How to Think

Something in Peter's quote really struck me when pondering these issues of how we approach problems.

... if you don’t know how to approach the problem, you’re not going to get a solution.

Why did Ron Jeffries struggle so much to build a Sudoku solver? Because he doesn't know much about search or CSP. And if you don't know how to frame and solve a search problem, and you don't know or desire to use the "meta-tools"Or you know, ask an LLM. But more generally, "do a lot of similar problems and find patterns", or "look around for things that seem similar and how people solve it". to learn about them, then you won't be able to solve this type of problem.

With this in mind, I was unsurprised when Jeffries spent multiple articles recently writing about the process of building a bowling score calculator. This isn't quite FizzBuzz, but it's a still a single for-loopIt's a fun little problem if you want to try it yourself before you look at my solution. . My assertion is that Ron Jeffries downfall is due to the belief, and he doesn't come out and say this directly, but it's implied, that with TDD he's found a tool that can systematize programming.From Kent Beck's "Test-driven development: by example": One of the ironies of TDD is that it isn't a testing technique (the Cunningham Koan). It's an analysis technique, a design technique, really a technique for structuring all the activities of development. That is, if you apply this approach, you will unfailingly reach your goal: you don't need to know all this other stuff like CSP. Jeffries selection of and struggles with these simple problems, like the Sudoku solver and bowling calculator, are indicative of the limitations of his approach to problem solving.

The issue is that the results from the Entscheidungsproblem would suggest that there is no general method to solving problems.

The Entscheidungsproblem

The Entscheidungsproblem ("the decision problem") asks whether there is an algorithm that can determine whether a given statement is provable from a set of axioms. There's a bunch of related theorems you're probably familiar with if you have a CS background, like the Halting Problem or Rice's theorem. They all have to do with the impossibility of making a determination about whether a machine "does something".

The corollary for our case (which is more or less, "can I devise an algorithm for solving problems") is simple. If we can't decide if a program P solves a task T, then we certainly can't solve the even harder problem of finding a program P that solves a given task. More philosophically, we can't systematize the process of thinking itself.

These proofs are all on infinite machines, but we can of course observe this empirically as well: math and programming would be trivialized if you could follow a simple process to solve all problems. This is part of the joy, the art, of the discipline. If you can turn a crank to get the result, you lose the fun in the process.

This isn't to say you can't have a process which helps you write programs, but solving a new problem will always require some amount of insight.

On Solving Problems

The desire to have a system for solving problems is understandable. And I do think Ron Jeffries really believes in it. After all, who wouldn't like to be smart like Peter Norvig? Just imagine if you could apply a simple procedure to solve all of these problems - it would be magical.

But the reality is there's no single approach we can take. If I'm good at programming, it's because I've built up the right toolbox for programming problems. When I start a project, or hit a bug, I reach for certain "tools" (literally, in the case of say, an editor, but also figuratively, in the sense of how I approach problems). I might even have "meta" tools, like how I approach a new problem: how do I attempt to break things down. If my toolset is a good match for the problem, then I will be more successful. A big part of learning and becoming better at a task is finding and learning how to apply the right tools. You learn from teachers, or from trying things out and paying attention to what works.

The best we can do is to try develop better and better tools to understand them, and ideally, figure out the right set of tools to have fun in the process. But we have to have humility in what we believe and what we promise. Ruby on Rails makes it easier for the average developer to make an average web app. It doesn't attempt to solve all problems, but it is a good tool for a specific set of problems. TDD might, for all I knowI'm not convinced, but if it genuinely helps some people do better, that's great. Andrew Daike's post outlines most of the issues I see as well. , be a decent way to develop certain types of programs. It can't be a solution for how to do all of programming. In a sense, the broader the subject, the less "directed" our tools can afford to be.

I know, I know, this is all so deeply... unsatisfying. Like, why can't someone at least figure out general tools that work most of the time? In penance for making you read through this, here's a grab bag of mine:

And more tactically:

...or perhaps I'm way off base and there is a general solution to everything. The best I've found is to try things, and pay attention to what I try, and be open to learning new things. What tools to you use?