Monday, February 11, 2008

On Algorithm X, Sudoku, Common Lisp, and Pants

So, as I mentioned in my previous post, my current proramming project is trying to implement Knuth's Algorithm X in Common Lisp. I was initially going to write a sudoku solver, but realized that I was basically copying Peter Norvig's solver, so I decided to try and generalize. You see, I am very anal about having general solutions to problems. An example: I recently acquired a pair of pants with a nifty little pocket on the side of the leg, between the hip pocket and the side pocket. Now, I always need more pockets, as I tend to carry tons of random things with me. However, I never use that pocket, although it would be idea for my keys and phone. Why? Because it isn't a general solution to the problem of carrying my stuff: I'd need to have that pocket on all my pants before I started using it. Right, I'm crazy.

Anyway, enough about pants. While looking at the wikipedia article on the mathematics of sudoku, I came across the intriguing fact that sudoku (along with n-queens, among others) can be reduced to the problem of finding an exact covering set for a sparse matrix, a problem which Donald Knuth developed an algorithm to solve. Without further ado, I decided that this was to be my next programming challenge.

(Note: Before reading further, you might want to at least glance at the Wikipedia article on the algorithm)

As I began considering the program I was to write, I decided to first make an implementation of sparse matrices. I'm sure that there are other Common Lisp packages for that far better than mine, but I figured that having control over the representation of the matrix would make it much easier to write the solver. I'm glad I did too, as I've since had to change my matrix implementation several times. Initially, I had the matrix as a class with slots for the number of rows and columns, and a hash table keyed on the (1-indexed) rows, with the values being a list of integers corresponding to the occupied columns in that row. However, some time later, I realized a fundamental flaw: The way I had designed the algorithm, I had no way of knowing which row of the original matrix the reduced rows I was choosing in the recursive stage corresponded to. The quick hack that I'm currently using was to change the values stored in the hash table to cons pairs of (<occupied columns list> . <id character>). The idea is that all the places (which were few, by design) that were directly accessing the hash would just have the (gethash …) replaced with (car (gethash …)).

Of course, there ended up being other places where things went weird, such as when mapping over the hash, and one annoying bug that took me a while to track down: One of the common operations the algorithm performs is dropping rows and columns from the matrix. Of course, we don't want to trash the original matrix, so we make a copy of the matrix to pass to the recursive stage. Okay, but to copy the matrix, we need to copy the hash table that maps the rows to occupied columns. Okay, we can do that too, thanks to a helpful soul on #lisp:

(defun copy-hash-table (ht)
  "Shallow hashtable copy."
  (let ((nht (make-hash-table :size (hash-table-size ht))))
    (maphash (lambda (key value)
               (setf (gethash key nht) (if (listp value) (copy-list value) value)))
             ht)
    nht))
The problem was that, since the value was now a list, I needed to copy the list, otherwise the destructive drop-* operations would alter the original matrix. Once I figured out that this was the problem, the solution was a simple replacing of the setf in the code above with (setf (gethash key nht) (if (listp value) (copy-list value) value)). You may (fairly) point out that I don't need the check if value is a list, since it always will be. Remember what I said at the beginning about specific solutions though? Even that makes me unhappy…

Well, it's after 1:00 AM now, so I think it's time to wrap this up. Tune it next time to learn the current state of my implementation!

I guess I need to figure out how to get syntax-highlighting with Blogger...Let's see if I can get it working for the next post! Update:Looks like I've got emacs htmlize-region to play nicely with Blogger, huzzah

2 comments:

Abhishek said...

U can also Use trees/vectors to represent a matrix

Anonymous said...

It is certainly interesting for me to read this article. Thank author for it. I like such themes and anything connected to this matter. I definitely want to read a bit more soon.