Minimalistic SAT solver
MiniSat is a minimalistic, open-source Boolean satisfiability problem (SAT) solver, developed to help researchers and developers alike to get started on SAT. Together with SatELite, MiniSat was recently awarded in the three industrial categories and one of the "crafted" categories of the SAT 2005 competition. A SAT solver can determine if it is possible to find assignments to boolean variables that would make a given expression true, if the expression is written with only AND, OR, NOT, parentheses, and boolean variables. If the expression is satisfiable, MiniSAT can also produce a set of assignments that make the expression true. Although the problem is NP-complete, SAT solvers (like this one) are often able to decide this problem in a reasonable time frame.