# Starting SAT solver papers

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.

-
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
The Handbook of Satisfiability - amazon.co.uk/… (perhaps check a library, the cost is pretty high). –  MGwynne Aug 3 '11 at 14:23
@Jukka: comment -> answer ? –  Suresh Venkat Aug 3 '11 at 16:26
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
See also related question cstheory.stackexchange.com/q/1988 –  András Salamon Aug 6 '11 at 16:05
show 1 more comment

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.

-

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

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

-

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.

-