So, a bit of fun for the Christmas 2009 issue: solving Sudoku puzzles efficiently. Not if you’re a human, you understand, unless you’re the type of human who likes programming, but from the viewpoint of discussing algorithms for solving via computer. Because, once you’ve programmed how to solve a Sudoku puzzle, it’s pretty easy to then generate puzzles to solve.

I started off with a brute force technique (that is, try every digit in every cell, all the time following the rules about no duplicates in a row, column, or box), which to be truthful, works pretty well most of the time. It did allow me to natter on about depth-first algorithms and backtracking though, and how to recognize that a puzzle is impossible (there’s nowhere left to backtrack before you solve the puzzle) or that there are several solutions (save the first one you find and then backtrack from there). Once you have that basic algorithm down pat, it’s the work of moments to generate puzzles by randomly selecting digits to go in cells and checking whether a puzzle is solvable in one or many ways.

After that I touch on the whole difficulty problem. Newspapers categorize the puzzles they print into easy, moderate, difficult or diabolical, but how do they do so? Get their (human) compiler/editor to try them out and rate them accordingly? Or is there some possible algorithm for doing so?

And then I tossed off an aside on Knuth’s Dancing Links algorithm (paper), which is very efficient at solving Sudoku. But that’s a whole new ball of wax, and, as I said, the brute force method is pretty efficient for Sudoku.

Actually, for me personally, this particular article became very portentous. You see it was my parents who first turned me onto Sudoku by sending us clippings of puzzles from the Telegraph, urging us to try them. My first few attempts were pretty grim until I formulated an algorithm to solve them that I could easily follow with pencil and eraser. We even found a book of blank Sudoku grids at Barnes & Noble one year, bought something like 6 of them and shipped them home to Mum & Dad for Christmas so that they could copy puzzles from the newspaper and each solve them.

Then just before Christmas 2009, pretty much as this issue hit the newsagents’ shelves in England, my Dad had a heart attack from which he didn’t really recover. He died on 21 December 2009, a year ago tomorrow as I write this (let me just say that this past seven days have been difficult because of the remembrance). I’d flown to England to be beside his bedside and had purchased the Christmas issue containing this article at Heathrow on my way up. Anyway, for his lucid moments in the hospital, he had a collection of Sudoku puzzles in book form on the bedside table to keep his mind occupied. I kept it after his death. The writing in the later puzzles is very shaky indeed and has the single word DELIRIUM on the last puzzle he attempted — one of his doctors has asked him to jot down words that described what he felt (presumably as an exercise in keeping him thinking lucidly) and this happened to be the only one he did write down. Trust Dad to write down a word that I just had difficulty remembering how to spell correctly, second vowel I or E? — he was an avid Telegraph crossword puzzle solver.

This article first appeared in issue 289, Christmas 2009.

You can download the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

I was chatting with Mehul in the DevExpress offices yesterday about writing iPhone apps with MonoTouch. He wanted to know what iPhone app had most impressed me, now that I'd had the phone for a little while and therefore what I might be trying to emulate in my own programming. My reply was Sudoku Grab.

Yeah, yeah, I can hear you saying. There are a bazillion apps out there already that do Sudoku. What's so special about this one?

Well, it's the grab part that fascinates me and that elevates this app above the run of the mill (I'll admit, the solving part of the app is quite ordinary). What I like is the way it uses other iPhone features rather than just the screen and touch interface. Without embellishing it too much, the grab feature allows you to take a photo using the iPhone camera of a Sudoku puzzle printed in a newspaper or displayed on your screen (say, from Web Sudoku). The program does a bit of image processing and OCR and imports the puzzle into the program's own interface. The program even determines the difficulty of the puzzle. You don't have to transcribe anything to play a puzzle on your phone, the program does it all. It really is quite magic to see it for the first time.

The author of Sudoku Grab has written a very informative blog post about how the image processing and OCR works. It's fascinating to read if you're at all interested in algorithms.

So, in short, it's the programs that make use of the iPhone's hardware features (GPS, compass, accelerometer, camera, etc) that I find the most interesting. It reveals that the author is trying to fit what might be after all a pretty bog-standard program into the universe of the iPhone to make it uniquely recognizable as an iPhone program.