Tuesday, July 10 2012
Common-Lisp, Sudoku, Solver, Puzzle

Solving Every Sudoku Puzzle

Peter Norvig published a while ago a very nice article titled Solving Every Sudoku Puzzle wherein he presents a programmatic approach to solving that puzzle game.

The article is very well written and makes it easy to think that coming up with the code for such a solver is a very easy task, you apply some basic problem search principles and there you are. Which is partly true, in fact. Also, he uses python, and that means that a lot of trivial programming activities are not a concern anymore, such as memory management.

As I've been teaching myself Common Lisp for some weeks now I though I would like to read a lisp version of his code, and the article even has a section titled Translations. Unfortunately, no lisp version is available there. One might argue that Clojure is a decent enough lisp, but my current quest is all about Common Lisp really. So I had to write one myself.

CL-USER> (sudoku:print-puzzle
	  (sudoku:solve-grid
"530070000600195000098000060800060003400803001700020006060000280000419005000080079"))
5 3 4 | 6 7 8 | 9 1 2 
6 7 2 | 1 9 5 | 3 4 8 
1 9 8 | 3 4 2 | 5 6 7 
------+-------+------
8 5 9 | 7 6 1 | 4 2 3 
4 2 6 | 8 5 3 | 7 9 1 
7 1 3 | 9 2 4 | 8 5 6 
------+-------+------
9 6 1 | 5 3 7 | 2 8 4 
2 8 7 | 4 1 9 | 6 3 5 
3 4 5 | 2 8 6 | 1 7 9 
took 1,974 microseconds (0.001974 seconds) to run.
During that period, and with 2 available CPU cores,
     1,894 microseconds (0.001894 seconds) were spent in user mode
        88 microseconds (0.000088 seconds) were spent in system mode
 174,320 bytes of memory allocated.
#<SUDOKU::PUZZLE #x3020023BB9FD>

Comments on the python version

Norvig's article is very well written, I think. By that I mean that by reading it you're confident that you've understood the problem and how the solution is articulated, so you almost think you don't need to really try to understand the code, it's just an illustration of the text.

Well, not so much. When you want to port the exact same algorithm you have to understand exactly what the code is doing so that you're not implementing something else. All the more when, as I did, you want to use some other data structure.

My goal was not to rewrite the code as-is, but to try and come up with idiomatic lisp code implementing Norvig's solution. So rather than using strings and dictionaries (in lisp, they still call them a hash table) I've been using more natural data structures.

The python code is really not that easy to follow, full of functional programming veteran tricks. I mean avoiding exceptions and simply returning False whenever there's a problem, and using functions such as all and some to manage that. It's certainly working, it's not making the code any easier to read.

To summarize, that code looks like it's been written by someone smart who didn't want to spend more than a couple of hours on it, and did take all known trustworthy shortcuts he could to achieve that goal. Quality and readability certainly weren't the key motive. I've been quite deceived after reading a very good article.

Comments on the common lisp version

Keep in mind that I'm just a Common Lisp newbie. I've been told some good pieces of advice by knowledgeable people though, so with some luck my implementation is somewhat lispy enough.

So we start by defining some data structures and low-level functions to build up the more complex one, so that it's easier to read and debug. The sudoku puzzle is then a grid of digits and a grid of possible values in places where the digits are yet unknown.

The way to represent that 9x9 grid is with using make-array:

(make-array '(9 9)
	    :element-type '(integer 0 9)
	    :initial-element 0)

Then the possible values. I though about using a bit-vector (and actually I did implement it that way), then I've been told that the Common Lisp way to approach that is using 2-complement integer representation, as we have plenty of functions to operate numbers that way. I wouldn't believe that would make the code simpler, but in fact it really did, see:

CL-USER> #b111111111
511
CL-USER> (logcount #b111111111)
9
CL-USER> (logcount 511)
9
CL-USER> (logbitp 3 #b100100100)
NIL
CL-USER> (logbitp 2 #b100100100)
T
CL-USER> (format nil "~2r" (logxor #b111111111 (ash 1 4)))
"111101111"
CL-USER> (logbitp 4 (logxor #b111111111 (ash 1 4)))
NIL

With that in mind, we can write the following code:

(defun count-remaining-possible-values (possible-values)
  "How many possible values are left in there?"
  ;; we could raise an empty-values condition if we get 0...
  (logcount possible-values))

(defun first-set-value (possible-values)
  "Return the index of the first set value in POSSIBLE-VALUES."
  (+ 1 (floor (log possible-values 2))))

(defun only-possible-value-is? (possible-values value)
  "Return a generalized boolean which is true when the only value found in
   POSSIBLE-VALUES is VALUE"
  (and (logbitp (- value 1) possible-values)
       (= 1 (logcount possible-values))))

(defun list-all-possible-values (possible-values)
  "Return a list of all possible values to explore"
  (loop for i from 1 to 9
     when (logbitp (- i 1) possible-values)
     collect i))

(defun value-is-set? (possible-values value)
  "Return a generalized boolean which is true when given VALUE is possible
   in POSSIBLE-VALUES"
  (logbitp (- value 1) possible-values))

(defun unset-possible-value (possible-values value)
  "return an integer representing POSSIBLE-VALUES with VALUE unset"
  (logxor possible-values (ash 1 (- value 1))))

You can see here that I was also under the influence of a recent reading about making it obvious, or so called intentional programming, following what Joe Armstrong has to say about it:

Intentional programming is a name I give to a style of programming where the reader of a program can easily see what the programmer intended by their code. The intention of the code should be obvious from the names of the functions involved and not be inferred by analysing the structure of the code. (Reading the code should) precisely expresses the intention of the programmer—here no guesswork or program analysis is involved, we clearly read what was intended.

Joe Armstrong in Intentional Programming

So there we go with function names such as count-remaining-possible-values, that will help when reading some more complex code, as in the following, the meat of the solution:

(defmethod eliminate ((puzzle puzzle) row col value)
  "Eliminate given VALUE from possible values in cell ROWxCOL of PUZZLE, and
   propagate when needed"
  (with-slots (grid values) puzzle
    ;; if already unset, work is already done
    (when (value-is-set? (aref values row col) value)
      ;; eliminate the value from the set of possible values
      (let* ((possible-values
	      (unset-possible-value (aref values row col) value)))
	(setf (aref values row col) possible-values)

	;; now if we're left with a single possible value
	(when (= 1 (count-remaining-possible-values possible-values))
	  (let ((found-value (first-set-value possible-values)))
	    ;; update the main grid
	    (setf (aref grid row col) found-value)

	    ;; eliminate that value we just found in all peers
	    (eliminate-value-in-peers puzzle row col found-value)))

	;; now check if any unit has a single possible place for that value
	(loop
	   for (r . c)
	   in (list-places-with-single-unit-solution puzzle row col value)
	   do (assign puzzle r c value))))))

So that lisp code is quite verbose and at 389 lines almost doubles the 201 lines Norvig had. When clarity is part of the goal, that's hard to avoid, I hope I made a good case that this is not due to lisp being overly verbose by itself.

Comments on the development environment

Or why I even considered Common Lisp as an interesting language for that kind of exercise, and some more. I'll have to tell about re-sharding data live with 16 threads and 256 databases, all in CL, someday.

So I've been doing some Emacs Lisp development for a while now, and the part that makes that so much fun is the instant reward. You write some code in your editor, type a key chord (usually, that's C-M-x runs the command eval-defun) and your code is loaded up, ready to be tested. In Emacs Lisp the test can be simply using your editor and watching the new behavior taking place, or playing in the M-x ielm console. When the code is not ready, it crashes, and you're left in the interactive debugger, where you can use C-x C-e runs the command eval-last-sexp to evaluate any expression in your source and see its value in the current debug frame.

That way of working is a huge productivity boost, that I've been missing much when getting back to writing C code for PostgreSQL. I can't C-M-x the current function and go write some SQL to test it right away, I have to compile the whole source tree, then install the new binaries, then restart the test server and then open up a psql console to interact with the new code. Of course I could just make check and watch the results, but then if I attach a debugger it complains that the code on-disk is more recent than the code in the core dump.

What if you want Emacs Lisp integrated facilities and something made for general programming rather than suited to building a text editor? Don't get me wrong, you can probably find more production ready code in elisp than in many other languages, just because Emacs has been there for about 35 years. Editor targeted production code, though.

This integrated development cycle is all the same when you're using Common Lisp. The awesome Superior Lisp Interaction Mode for Emacs is providing exactly that experience. Just run M-x slime and then as you define your code you can C-M-x the function at point, see the compilation errors and warnings if any in the associated REPL, and just try your code. I tend to mostly play in the command line, it's possible to just use C-x C-e while typing too.

Performances

Of course we do care! After all the original article came with a quite detailed performance analysis with graphs and all. I won't be reproducing that, sorry. I'll just show you what penalty you get for using an older language specification, much more dynamic and with more features than python, and with a great, scratch that, awesome development environment.

Oh wait, that's the other way round, no penalty, it's actually so much faster!

Python version perfs

The results I got on my desktop machine are about twice as fast as in the original article, I guess newer machines and newer python have something to say for that:

dim ~/dev/CL/sudoku python sudoku.dim.py 
  All tests pass.
  Solved 50 of 50 easy puzzles (avg 0.01 secs (151 Hz), max 0.01 secs).
  Solved 95 of 95 hard puzzles (avg 0.02 secs (42 Hz), max 0.12 secs).
  Solved 11 of 11 hardest puzzles (avg 0.01 secs (115 Hz), max 0.01 secs).

That makes an average of (50*151 + 95*42 + 11*115) / (50+95+11) = 82Hz.

That seems pretty good, let's continue.

As you can see I've cut away the random puzzle part, that's because I was too lazy to implement that part, which didn't seem all that interesting to me. If you think that's a problem and need solving, I accept patches.

Common lisp version perfs

When using SBCL on the same machine, what I got was:

(sudoku:solve-example-grids)
  Solved 50 of 50 easy puzzles (avg .0021 sec (471.7 Hz), max 0.015 secs).
  Solved 95 of 95 hard puzzles (avg .0022 sec (446.0 Hz), max 0.008 secs).
  Solved 11 of 11 hardest puzzles (avg .0018 sec (550.0 Hz), max 0.003 secs).

With the same way to compute the average, we now have 461.6Hz.

Now, that's between 3 times and more than 10 times faster than the python version (taken collection per collection), for a comparable effort, a much better development environment, and the same all dynamic no explicit compiling approach.

Conclusion

I guess I'm fond of Common Lisp, which I already saw coming (so did you, right?), and now I have some public article and code to share about why :)

The code is hosted at https://github.com/dimitri/sudoku if you're interested, with the necessary files to reproduce, some docs, etc.

Also, apart from using integers as bitfields, which I did more for being lispy than for performances, I did very little effort for optimizing the code. It's quite naive in this respect, yet allow me an average of 461.6Hz rather than 82Hz, that's 5.6 times faster average.

So yes, I will continue to invest some precious time in Common Lisp as a very good interactive scripting language, and maybe more than that.