Description:

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.