Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I want to make a first SAT solver. I know the SAT competition and the SAT conference, and there are just so many papers on this subject. I'm a starter, an overwhelmed starter. Where should I begin? Eventually I want to push the state-of-the-art. I want some expert advice on how to start, so that I won't be wasting my time on the non-essentials too early. Many thanks.

share|improve this question
6  
Have you already implemented the DPLL algorithm? Have you fine-tuned and polished your implementation so that it runs extremely fast? –  Jukka Suomela Aug 3 '11 at 8:10
5  
The Handbook of Satisfiability - amazon.co.uk/… (perhaps check a library, the cost is pretty high). –  MGwynne Aug 3 '11 at 14:23
1  
@Jukka: comment -> answer ? –  Suresh Venkat Aug 3 '11 at 16:26
4  
I disagree with Jukka. Why reinvent the wheel? There's no reason to redo what MiniSAT already provides open source. If you're interested in adding to the CDCL framework your addition will show in boosted MiniSAT performance. Also, DPLL by itself is not enough; a lot of improvements have been made. Basically, follow Mikolas' answer! –  Huck Bennett Aug 4 '11 at 5:14
1  
See also related question cstheory.stackexchange.com/q/1988 –  András Salamon Aug 6 '11 at 16:05
show 1 more comment

4 Answers 4

An excellent beginner overview is given by the following article from 2009.

There are several ways to get into the technical aspects. You can even start with the original Davis-Putnam paper. It is extremely clear and has detailed examples. When discussing SAT optimizations in a course, we discovered that a few one may imagine are already there. The Davis-Logeman-Loveland paper is (I feel) less instructive, but it is so short you may as well read it.

There are may ways to catch up on the developments of the next 50 years. I would recommend lecture slides. Just searching for 'DPLL' will throw up many many tutorials. If you browse through them, I'm sure the mist will clear -- to some extent. There are also many useful surveys. The Zhang-Malik paper is a good place to start. There are several articles in the Handbook of Satisfiability you may find useful.

I second the suggestion of Mikolaos. The MiniSAT code is clean and of manageable size. You can play with it. There are several other solvers you can try. CryptoMiniSat is also quite clean. You should also consult the work of Armin Biere, who writes SAT solvers and writes about writing SAT solvers.

share|improve this answer
add comment

I suggest first understanding which techniques really advanced the solvers, for which I would suggest the following overview and analysis.

Then I would recommend downloading the source code of minisat and read its description.

It might of course be individual but I found looking at the source code most valuable.

share|improve this answer
add comment

If you're overwhelmed by all of the work that's out there, why don't you start out pretending that nobody's worked on the problem before? If your goal is to eventually build a competitive SAT solver, it's going to be a fairly long journey. By starting out just playing around without 'checking the solutions', so to speak, you have more to gain than to lose.

First build the simplest solver you can and make sure it works. This will probably be a brute force algorithm whose running time depends more or less only on the $n$, the number of variables, and $m$, the number of clauses. Then implement something a little bit smarter like branch-and-bound. Write (or find) a generator that will give you random instances for given values of $n$ and $m$.

Do some benchmarking tests for your branch-and-bound solver. See how it does for varying values of $n$ and $m$. Then improve your solver to make it faster. See how far you can get without reading about other work. When you run out of ideas, do some of the reading suggested in the other answers.

share|improve this answer
add comment

Start with a good survey paper. It's easy to attack the subject piecemeal and get confused by different names in the literature for the same techniques and the same name used for different techniques. It's also easy to re-enact old algorithmic battles (occur lists vs. head-tail lists vs. two watched literals for DPLL implementations for instance) if you don't know what the state of the art is.

Satisfiability Solvers by Gomes, et. al. will give you the rough lay of the land.

Improving SAT Solvers Using State-of-the-Art Techniques by Manthey will bring you closer to the present.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.