This repo contains SAT solvers that are implemented following descriptions in Donald Knuth's "The Art of Computer Programming, Volume 4, Fascicle 6: Satisfiability".
Solvers currently implemented are:
- 7.2.2.2 Algorithm B: Backtracking with watched literals
- 7.2.2.2 Algorithm D: DPLL
- 7.2.2.2 Algorithm C: CDCL
- 7.2.2.2 Algorithm L: DPLL with lookahead (modeled after march [1] [2])
- 7.2.2.2 Algorithm W: WalkSAT
These solvers are all built to accept DIMACS input files and follow the output format used in SAT comptetitions.
You'll need git
to clone this repo, g++
and make
to build and python3
to run
instance generators in the gen/ subdirectory. bash
is used as the shell for scripts.
On a debian-based Linux distribution, you can make sure you have everything you need by running:
apt-get update && apt-get install bash build-essential git python3
Next, clone this repo:
git clone [email protected]:aaw/sat.git
cd into the top level of the clone (cd sat
) and run make
to buld everything.
This should produce five binaries and put them in the bin/ subdirectory:
btwl
(Algorithm B)dpll
(Algorithm D)cdcl
(Algorithm C)look
(Algorithm L)walk
(Algorithm W)
To create the fastest binaries, compile out any logging, counters, or timers by adding
OPT=1
and rebuilding from scratch:
make clean bin/cdcl OPT=1
Run any of the SAT solver binaries against a DIMACS CNF input file by passing the input file as an argument, for example:
./bin/dpll ./test/simple_1.cnf
All solvers accept a set of common flags:
-sN
: Set the random seed to integerN
.-vN
: Set the logging verbosity to a numberN
>= 0. 0 means no logging, more detail comes with higher levels.-t
: Collect timing information, dump at exit.-c
: Collect counters, dump at exit.-dF
: Output a DRAT proof on unsatisfiable instances to file F. (Only works forcdcl
.)-p[p1=v1][;pn=vn]*
: Set binary-specific parameters to floating point values.-h
: Display all flags and parameters available.
The script/ subdirectory contains test scripts and the test/ subdirectory contains test instances (DIMACS CNF files). Test files are all annotated with comments labeling them as satisfiable/unsatisfiable and a subjective rating of easy/medium/hard.
The script/test.sh
script can be used to test a SAT solver against these files.
Pass the solver with -b
, the difficulty with -d
and an optional per-instance
timeout with -t
. For example, to test the dpll
solver against all easy instances
with a timeout of 10 seconds per instance, run:
./script/test.sh -bdpll -deasy -t10s
A full list of flags accepted by script/test.sh
:
-bX
: The solver to test, whereX
is one of{btwl,dpll,cdcl,look,walk}
. Default:btwl
.-dX
: Test instance difficulty, whereX
is one of{easy,medium,hard}
. Default: easy.-lX
: Test instance label, whereX
is eithersat
orunsat
. Default: test both sat and unsat.-pX
: Binary-specific params.X
is passed through directly as-p
flags to the solver.-sN
: Random seed, an integer.N
is passed through directly as-s
flag to the solver.-tX
: Timeout. Format forX
is a floating point duration with an optional suffix ofs
(seconds, default),m
(minutes),h
(hours),d
(days).-v
: If set, verify results. Usesscript/verify_sat.py
to verify satisfiable results and expectsbin/drat-trim
to exist to verify unsatisfiable results. All binaries can have their satisfiable results verified, onlycdcl
can have its unsatisfiable results verified.
Generators in the gen/ subdirectory are meant to be run at the command line and
output the instance to stdout
. Read the header comments for a generator to see
the command-line arguments it expects. To generate an instance file,
for example, just redirect the output to a file:
./gen/langford.py 5 > langford_5.cnf
To run a SAT solver directly against the output of a generator without an intermediate file, use bash process substitution:
./bin/dpll <(./gen/langford.py 5)
./script/fuzz.sh
supports fuzz-testing one binary against another on randomly generated
instances. Random instances close to the sat/unsat threshold are created using the ./gen/rand.py
generator.
Flags accepted:
-bX
: The experiment solver, whereX
is one of{btwl,dpll,cdcl,look,walk}
. Default:look
.-cX
: The control solver, whereX
is one of{btwl,dpll,cdcl,look,walk}
. Default:cdcl
.-dX
: The difficulty, whereX
is one of{easy,medium,hard}
. Default: easy.-nN
: Number of testsN
to run. Default: 20.-pX
: Parameters sent to the experiment solver.-rN
: Integer random seedN
used by the control binary.-sN
: Integer random seedN
used by the experiment binary.-tX
: Timeout.X
should be in the same timeout format accepted by./script/test.sh
.