Sudoku in Coders At work

Once upon a time, I wrote this blog entry. Peter Norvig references it (indirectly) in his interview in Peter Seibel's great new book "Coders At Work".


"Seibel: Though your job now doesn’t entail a lot of programming you still write programs for the essays on your web site. When you’re writing these little programs, how do you approach it?


Norvig: I think one of the most important things is being able to keep everything in your head at once. If you can do that you have a much better chance of being successful. That makes a small program easier. For a bigger program, you need extra tools to be able to handle that. It’s also important to know what you’re doing. When I wrote my Sudoku Solver, some bloggers commented on that.

They said, “Look at the contrast—here’s Norvig’s Sudoku thing and then there’s this other guy, whose name I’ve forgotten, one of these test-driven design gurus. He starts off and he says, “Well, I’m going to do Sudoku and I’m going to have this class and first thing I’m going to do is write a bunch of tests.” But then he
never got anywhere. He had five different blog posts and in each one he wrote a little bit more and wrote lots of tests but he never got anything working because he didn’t know how to solve the problem. I actually knew—from AI—that, well, there’s this field of constraint propagation—I know how that works. There’s this field of recursive search—I know how that works. And I could see, right from the start, you put these two together, and you could solve this Sudoku thing. 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.

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.

Seibel: So then the question is, how should he have known that? Should he have gone and gotten a PhD and specialized in artificial intelligence? You can’t know every algorithm. These days you have Google, but finding the right approach to a problem is a little different than finding a web framework.

Norvig: How do you know what you don’t know?
Seibel: Exactly.

Norvig: So I guess it’s two parts. One is to recognize that maybe there is a known solution to this. You could say, “Well, nobody could possibly know how to do this, so just exploring randomly is as good as everything else.” That’s one possibility. The other possibility is, “Well, probably somebody does know how to do this. I just don’t know what the words are for it, so I
have to discover those.” I guess that’s partly just intuition and saying, “It seems like the kind of thing that should be in the body of knowledge from AI.” And then you have to figure out, how do I find it? And probably he could’ve done a search on Sudoku and found it that way. Maybe he thought that was cheating. I don’t know

.
Seibel: So let’s say that is cheating—say you were the first person ever to try and solve Sudoku. The techniques that you ended up using would still have been out there waiting to be applied.

Norvig: Let’s say I wanted to solve some problem in biology. I wouldn’t know what the best algorithms were for doing gene sequencing or whatever. But I’d have a pretty good idea that there were such algorithms. Then I could start looking around. At another level, some of these things are pretty fundamental—if you don’t know what dynamic programming is, then you’re at a severe disadvantage. It’s going to come up time and time
again. If you don’t know this idea of search in general—that you can make a choice and backtrack when you don’t need it. These are all ideas from the ’60s. It was only a few years into programming that people discovered these things. It seems like that’s the type of thing that everyone should know. Some things that were discovered last year, not everybody should know.


Seibel: So should programmers go back and read all the old papers?
Norvig: No, because there are lots of false starts and lots of mergers where two different fields develop completely different technology and terminology, and then they discover they were really doing the same thing. I think you’d rather have a story from the modern point of view rather than have to follow all the steps. But you should have them. I don’t know what the best books are for that since I picked it up the hard way, piecemeal."


Dr. Norvig is a much nicer (and wiser) person than I am. I (completely) agree with him that bloggers' blather (including mine) doesn't mean much and TDD is great as one (vs the only) tool in one's arsenal.

That said, I still think many so called "agile" "gurus" can't program for nuts, as Jeffries so amply demonstrates. It is hypocrisy of the first order that people who don't know how to program well advise the rest of us how to. The "agile" movement brimmeth over with such pseudo programmer snake oil salesmen.

"These are all ideas from the ’60s. It was only a few years into programming that people discovered these things. It seems like that’s the type of thing that everyone should know."

"Should know" is correct. It is also true that most "developers" wouldn't know Dynamic Programming if it showed up at the front door and slapped them silly.

One reason for this is that most "enterprise" programming uses essentially two data structures, the List and the Hashtable and most language implementations provide default implementations of these. And a lot of "programmers" do this all their lives and think they are cool because they drank the latest/greatest shiny methodology Kool Aid. And these folks get the "gurus" they deserve!

"Seibel: What about the idea of using tests to drive design?

Norvig: I see tests more as a way of correcting errors rather than as a way of design. This extreme approach of saying, “Well, the first thing you do is write a test that says I get the right answer at the end,” and then you run it and see that it fails, and then you say, “What do I need next?”—that doesn’t seem like the right way to design something to me."

heh! heh!

Anyway, it is great that something I wrote got reflected, however indirectly, in this great book.


Coders at Work is a great book with legendary programmers talking in great detail about many aspects of programming. It is very interesting how Peter Seibel (the author) has captured each "voice" so perfectly. Every programmer should read this book, *especially* if you are stuck in a sucky job writing leasing systems (or accounting systems or whatever).

"What power would Hell have if those imprisoned there were not able to dream of Heaven?" as the Dream King says in Neil Gaiman's "The Sandman", but even at the cost of granting Hell some power, do dream of Heaven, say I, for that way lies eventual redemption.

This book provides a glimpse of what programming looks like for people who are already "in heaven".