October, 2011

The last several weeks, we’ve begun exploring and implementing our first CSP solvers. Our first solver implemented the simplest backtracking algorithm, BT, and used several forms of static variable ordering. We studied Patrick Prosser’s paper on types of back-checking, forward-checking, and hybrids of the two. 

We then began work on CBJ (Conflict-Directed Backjumping), one of the most efficient backtracking algorithms mentioned in Prosser’s paper. We are now moving on to forward checking and dynamic variable ordering, which I expect will be a lot more difficult to implement, but I am looking forward to the challenge. 

 The last few weeks, I have been spending some extra time improving and debugging by AC and NC algorithms from earlier. NC reduces a problem that has unary constraints, a case not handled by my AC algorithm, which is why it is important to run NC before AC, or your domains will not be properly filtered. I discovered a bug in my NC algorithm that I only discovered when testing on instances of the Zebra problem—our only test cases in which NC altered the resulting domains. 

Once correcting this, I was able to catch a bug in my implementation of AC-3 and work to correct it. Implementing algorithms is what I find to be the most time-consuming aspect of research, but also the most rewarding aspect. 

My main frustration lately has been time constraints—having a heavy course-load this semester makes it difficult to find extended periods of time to devote to coding and studying. I am happy to say that I have recently registered for spring classes, and have arranged for a lighter schedule that would allow me to devote more time to research. 

-Maggie