PCPlus 289: Solve Sudoku

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.)

  Loading links to posts on similar topics...