Learning From Sudoku Solvers

I wrote a Sudoku Solver. In a few hours. I'm sure many have.

this thing is, puzzles like this don't need "design up front" as one commenter suggested - they need a flash of inspiration to solve the nub of the hard problem. If you have that, then tests will help you implement it correctly, and help you change it without breaking it.

If you don't have that inspirations, then tests won't help you. Maybe you'll get inspired while you're messing around with tests on the puzzle, maybe not.

Puzzles are almost completely unlike everyday tasks that programmers typically encounter, e.g. Adding TPS report generation to your website.

It seems to me like the lesson here is that you can't write a program without having any idea how the program ought to work.

Formal training in computer programming should expose people to "standard" methods of solving problems (like constraint satisfaction, dynamic programming etc.).

I did an AI course (and separately a lab) while at college and there were a few problems we were asked to solve using specific algorithms. The "hardest" was a Tic-Tac-Toe player that used a game tree. It wasn't too hard and I remember thinking that I didn't learn much but the general methodologies stay in your head and when there's a problem that comes up later, you have an arsenal of thing you can draw on to attack it.

I'm not saying that it will guarantee better solutions but when all you have is a hammer, every problem will look like a nail.

The one thing that's not mentioned in the article or the comments was that Jeffries had never played sudoku before this problem whereas Norvig presumably has.

It was after a few months of playing the game when I started thinking "Oh, this is just a constraint propagation search problem" and, indeed, when I had to code a solution for a programming competition, it took about 45 minutes to hack together the code.

Many years ago I tackled the Project Euler problem involving Sudoku. I wrote a solution. Ran it. It worked but was way slower than I wanted it to be.

I googled, found Norvig's article. Read it. Looked conceptually simpler. Tried implementing again. Massively faster.

Why? Because I used strings rather than a fancy object representation. And strings are faster. Not a little bit, but an order of magnitude at least.

One of the first major programs I wrote was a Sudoku Solver in python. I learnt a lot from it, and looking back it had such horrible code. Probably the worst was the hard-coded row, column and square indexes for function calls. Somehow I couldn't think of an easy way to do it automatically at the time, but now it seems like the easiest thing in the world. There was also a point where I used "+" on all 81 elements as strings, which was rather slow. After using a ''.join(), it was much, much faster, because the join was one operation instead of 80 (for those that don't know python, join is simply a function that joins strings).

Ironically I also tried writing an object orientated version to learn C++, but that didn't get very far.

I kind of feel like a lot of programs add complexity for complexity's sake. Looking up Ron Jeffries, I see he's an expert at programming (invented extreme programming, worked on the Agile manifesto) -- someone who's been doing it for a long time and is MUCH better than I am.

So it confuses me that he adds so much structure and goes about solving a simple problem in such a weird way. I wrote a Sudoku solver when I was in high school in less lines of C than the tests in his example. He did state that he hadn't played Sudoku first, and that could be a big part of it. If I wrote a program to play checkers, I imagine it would be a lot longer than it needs to be. But still, someone of his caliber... I am surprised. Maybe he wanted to make it extensible in the future; I guess my solver would be a little harder to extend than his.