kissat

Kissat is a high-performance open-source solver for propositional satisfiability problems. It is implemented primarily in C and C++, designed to be fast and robust across a wide range of benchmarks. Kissat accepts formulas in the DIMACS CNF format and provides a command-line interface as well as an API for integration into other software.

Its solver core is a modern CDCL (conflict-driven clause learning) engine. It uses efficient data structures and a two-literal watching scheme for unit propagation, along with a dynamically managed learned clause database. Kissat emphasizes aggressive clause learning and deletion strategies, along with effective restart policies, to manage search space. The solver supports incremental solving and solving under assumptions, enabling applications that require multiple related queries without restarting from scratch.

Development and usage: Kissat is maintained by a team of researchers and contributors and is widely used in academic research, software verification work, and SAT benchmarking. It has participated in SAT solver competitions and is noted for strong performance on large industrial and real-world problem instances.

See also: other prominent SAT solvers such as Minisat, Glucose, Lingeling, and CryptoMiniSat.