views:

84

answers:

1

What are good documents to read on SAT (Boolean satisfiability problem) solvers. I have not been able to find good material via Google. The documents I found were either birds eye view, too advanced or corrupted PDF files...

Which papers/documents do you recommend to learn about the algorithms in modern practical SAT solvers?

+2  A: 

The Davis-Putnam-Logemann-Loveland page on Wikipedia has a good overview.

Then you should be able to follow the minisat paper "An Extensible SAT-solver".

You should also read "GRASP - A New Search Algorithm for Satisfiability" to understand the conflict-driven learning algorithm used in minisat.

I was able to write a SAT solver in Python quite easily using those resources. My sat.py code is available (LGPL 2.1 currently), but it's quite recent so may still contain bugs. It lacks a few optimisations from the minisat design; if you want raw speed use the minisat code ;-)

Thomas Leonard
Thanks. No PDF reader would open the files on the minisat website, so I gave up on these. But since you suggested them I assume that you *can* open them. And indeed when I open them with Google's online pdf viewer they *do* work! Thanks.Is your Python SAT solver's code available?
Jules
Good idea - I've added a link to my code. The PDFs opened fine for me (in Evince: http://projects.gnome.org/evince/).
Thomas Leonard