Example: CNF SAT solver More...
Public Member Functions | |
| Sat (const InstanceOptions &opt) | |
| The actual problem. | |
| Sat (Sat &s) | |
| Constructor for cloning. | |
| virtual Space * | copy (void) |
| Perform copying during cloning. | |
| virtual void | print (std::ostream &os) const |
| Print solution. | |
| Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > > | |
| ScriptBase (const Options &opt) | |
| Constructor. | |
| ScriptBase (ScriptBase &e) | |
| Constructor used for cloning. | |
| virtual void | compare (const Space &home, std::ostream &os) const |
| Compare with s. | |
| Public Member Functions inherited from Gecode::Driver::IgnoreStepOption< BaseSpace > | |
| IgnoreStepOption (const Options &) | |
| Constructor. | |
| IgnoreStepOption (BaseSpace &e) | |
| Constructor used for cloning. | |
Related Symbols | |
(Note that these are not member symbols.) | |
| const char * | instance_spec |
| Reader spec for DIMACS CNF files. | |
Additional Inherited Members | |
| Static Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > > | |
| static std::ostream & | select_ostream (const char *sn, std::ofstream &ofs) |
| Choose output stream according to sn. | |
| static void | run (const Options &opt, Script *s=nullptr) |
Detailed Description
Example: CNF SAT solver
SAT finds assignments of Boolean variables such that a set of clauses is satisfied or shows that no such assignment exists.
The clauses are read from a DIMACS CNF file with a reader spec, and a clause propagator is posted for each of them.
Format of dimacs CNF files:
A dimacs file starts with comments (each line starts with c). The number of variables and the number of clauses is defined by the line
p cnf <variables> <clauses>
Then follow the clauses. A positive literal is denoted by a positive integer, a negative literal is denoted by the corresponding negative integer. Each clause is terminated by 0, and clauses may span several lines.
c sample CNF file p cnf 3 2 3 -1 0 1 2 -1 0
Benchmarks on satlib.org, for instance, are in the dimacs CNF format.
Constructor & Destructor Documentation
◆ Sat() [1/2]
|
inline |
◆ Sat() [2/2]
Member Function Documentation
◆ copy()
|
inlinevirtual |
◆ print()
|
inlinevirtual |
Print solution.
Reimplemented from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >.
Friends And Related Symbol Documentation
◆ instance_spec
|
Reader spec for DIMACS CNF files.
See Instance::Spec for the spec language.
The documentation for this class was generated from the following file:
- examples/sat.cpp
