Solving Sudoku Puzzles in Common Lisp 

DiscussionSudoku puzzles are usually 9x9 matrices with some of the cells initialized with positive numbers from 1 to 9. The object is to fill in the remaining cells so all numbers 1 to 9 are present in each row, column and 3x3 major subsquare. In general, these kinds of puzzles can be of any size square matrix whose sides are are k*k for integer k. I first worked out this algorithm in 2007. I wrote a generalized solver that would solve any puzzles k^2 by k^2 in size, for integer k. The algorithm walks the solution tree of possibilities recursively, always picking one of the higher probability guesses at each branch, which generally speeds up the search time tremendously. Then I ran across , "Solving Sudoku in Matlab," in the Matlab Newsletter, January 2010. Curious to test the mettle of my algorithm against his, I was chagrined to discover mine actually didn't converge on his "difficult" problem (see Figure 1) at all. It revealed a curious bug (thanks alot, Cleve!), which caused me to rethink my algorithm and come up with an even faster one. This is my new code. EnvironmentThere are no dependencies other than two trivial macros I call from a utility package^{1} The codeThe code itself can be downloaded here. The heart of it is the following two functions: The second is the recursion which always starts by calling UPDATECELLS, a function which goes through the puzzle filling in any singletons (cells which have only one possible number). The first function searches through the list of nonsingleton cells and finds the first with only two possibilities. Guessing one of these will have the highest probability of success. Once all the twoguess cells are gone, there are typically very few unsolved cells left, so it is probably not worth the overhead of sorting machinery (I have only partially quantified this). The speed up of stopping at the first pair though is tremendous. 
(1) (defmacro whenbind ((var expr) &body body) `(let ((,var ,expr)) (when ,var ,@body))) (defmacro ifbind ((var expr) &body body) `(let ((,var ,expr)) (if ,var (progn ,(first body)) ,@(cdr body)))) (defmacro whenbind* (binds &body body) (if (null binds) `(progn ,@body) `(let (,(car binds)) (if ,(caar binds) (whenbind* ,(cdr binds) ,@body))))) 

The "Sudoku Challenge"Here is the solution to Cleve's problem above. I didn't take the time to write graphic output like his — this prettyprinter will have to do. But algorithm only took 631 trial guesses to solve it, instead of 19,422 steps that his took. I don't know how long his took in time  he didn't say. I'm guessing it wasn't as fast as 0.219 seconds either.
Other ExamplesHere are several more puzzles that I obtained off the internet along with my solutions:
The last one was supposed to be "hard".

