Right. So. I’ve been writing my standard hello-world Sudoku solver in Go. It reached a plateau about a week ago when some changes that I thought were going to make it faster actually made it slower. I think I did something to a function that stopped the compiler inlining it. Or something. The point is that I was getting diminishing returns from incremental improvements to the current code.

The next step is to add some concurrency. At the moment it does some steps in parallel in the puzzle-generation stage, but it’s still solving a single grid serially. (The general algorithm is: solve an empty grid; then visit each square, and clear it if the resulting puzzle still has a unique solution. Right now, the check for a unique solution (or rather, the search for other solutions, which is expected to fail) is happening in several goroutines.)

The approach I used with the Java version was to keep partial solutions in a priority queue, ordered by the number of squares filled (so that the next one out of the queue is the most complete). These were farmed out to a thread pool. The result was a more-or-less depth-first search of the solution space. For reference, the thread manager code is here. (IIRC, there’s a bug in it somewhere – it doesn’t terminate properly.)

Concurrency is one of the things that’s supposed to be nice in Go. The basic approach I’m going to take for the priority queue is to have two channels, tied together by a goroutine that reads items from the “in” channel, puts them into a heap, then pops from the heap and writes to the “out” channel.

This morning I knocked together the code to do this in abstract. (Well, with ints, anyway. I’ll try to abstract out the type before using it for the Sudoku stuff. Generics would be nice here – generics are one of the longest-standing items on the wishlist for Go – but I think I can see a Go-like way of doing it regardless…) There are some funny corner cases with blocking – it needs to read eagerly enough from the “in” channel that things don’t just pass through, but not so much that it starves the “out” channel – and I’m not sure I’ve got the most parsimonious version yet, but it seems to work. And compared to the Java version, it really is quite pretty. Okay, okay, it might be a bit messier by the time I add a couple of other things needed by the Sudoku solver.

So, yeah. Progress.

A couple of my interests overlapped this morning when I found out that Google Goggles solves Sudoku.

(As an almost-related aside, I’m still tweaking my Go Sudoku solver. More on that later.)

So, after a bit of discussion, we decided to try to mess with it by feeding it invalid puzzles. Here’s one of the tests I tried – note the 4 in the upper-left block, which should be a 3.

What Goggles detected is below. Note that the 4 in question is there, but it’s missed a few numbers elsewhere in the puzzle.

It solves this version quite happily. At first I thought it was cheating by overwriting some of the original cells, until I noticed the gaps. I tried it again a few times, keeping the camera as steady as possible and cropping out other distractions; it detected a different subset of the numbers each time, so I started to think that the OCR was a bit flaky. But it always seemed to detect a valid puzzle… and when I tried it with the original valid puzzle, it detected everything.

It seems like Goggles doesn’t just recognise any old 9×9 grid of numbers as a Sudoku puzzle; it will only recognise a valid Sudoku puzzle as a Sudoku puzzle. My theory is that when it looks at the invalid Sudoku, its best match for it is a valid Sudoku with fewer numbers, plus some noise where its OCR thought there was probably a number but wasn’t quite as confident – as though, for example, there was some dust on the lens in front of those squares. (Most of the time it seemed to drop 1s, which have fewer obvious features than other numbers and are hard to distinguish from 2s.)

The interesting thing about this is that a naïve implementation (i.e. what I’d probably do) would OCR the grid first, set that in stone, then feed it into a Sudoku solver/validity-checker. Google’s implementation seems to tie more organically into however its recognition engine works (from this very limited set of tests anyway) – i.e. the space of objects it recognises includes all valid Sudoku puzzles. Somehow.

A few orders of business heading into the new year…

• My resolution for 2010 to learn to use Emacs properly remains unfulfilled. Despite my flirtation with Eclipse, I’m now back with Emacs and will probably stay there unless I do something Java-related. Eclipse is just too bulky and all-encompassing – my mentality is starting to drift back towards the Unix-y toolset approach. (Yes, I just used Emacs as an example of a tool that isn’t bulky. Shut up.)
• In-progress: Hello World Sudoku in Go.
• There are at least two dangling promises for follow-up posts: the ongoing review of Effective Java and/or critique of Java itself, which I’ll get around to soon; and The Design of Design, which I’ve stalled in reading again, having been distracted by Good Omens by Terry Pratchett and Neil Gaiman, because, as mentioned, it’s by Terry Pratchett and Neil Gaiman. I mean, come on.