I reflect on the Entscheidungsproblem how it relates to Sudoku solvers. It's a little weird..
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 minima I 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.
... continue reading