Generated on for Gecode by doxygen 1.17.0
sat.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Raphael Reischuk <reischuk@cs.uni-sb.de>
5 * Guido Tack <tack@gecode.dev>
6 *
7 * Contributing authors:
8 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
9 *
10 * Copyright:
11 * Raphael Reischuk, 2008
12 * Guido Tack, 2008
13 * Mikael Zayenz Lagerkvist, 2026
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.dev
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#include <gecode/driver.hh>
41#include <gecode/int.hh>
42
43#include <string>
44
45using namespace Gecode;
46
47namespace {
48
56 const char* instance_spec = R"(format dimacs-cnf
57
58comment "c"
59stop "%" # SATLIB files end with "%" and "0"
60line "p cnf {vars:0..gecode.int_max} {clauses:0..}"
61repeat clauses {
62 list clause: -vars..vars until 0 # the terminating 0 is not stored
63}
64)";
65
66}
67
102class Sat : public Script {
103private:
105 BoolVarArray x;
106public:
109 : Script(opt) {
110 Instance::Data d = opt.data();
111 x = BoolVarArray(*this, static_cast<int>(d.integer("vars")), 0, 1);
112 for (int c=0; c<d.size("clause"); c++) {
113 IntArgs literals = d.ints("clause", {c});
114 BoolVarArgs positives, negatives;
115 for (int l : literals)
116 if (l > 0)
117 positives << x[l-1];
118 else
119 negatives << x[-l-1];
120 clause(*this, BOT_OR, positives, negatives, 1);
121 }
122 branch(*this, x, BOOL_VAR_AFC_MAX(), BOOL_VAL_MIN());
123 }
124
126 Sat(Sat& s) : Script(s) {
127 x.update(*this, s.x);
128 }
129
131 virtual Space*
132 copy(void) {
133 return new Sat(*this);
134 }
135
137 virtual void
138 print(std::ostream& os) const {
139 os << "solution:\n" << x << std::endl;
140 }
141};
142
143
147int main(int argc, char* argv[]) {
148
149 InstanceOptions opt("SAT", instance_spec);
150 opt.parse(argc,argv);
151 if (argc > 2) {
152 std::cerr << "Error: unexpected arguments after the DIMACS file" << std::endl;
153 return 1;
154 }
155
156 if (!opt.is_file()) {
157 if (opt.instance() == nullptr)
158 std::cerr << "Error: no DIMACS file given" << std::endl;
159 else
160 std::cerr << "Error: cannot read file '" << opt.instance() << "'" << std::endl;
161 return 1;
162 }
163 try {
164 // Read here to report errors before solving starts
165 (void) opt.data();
166 } catch (const Instance::Error& e) {
167 std::cerr << e.what() << std::endl;
168 return 1;
169 }
170
171 // Run SAT solver
173 return 0;
174}
175
176// STATISTICS: example-any
Passing Boolean variables.
Definition int.hh:739
Boolean variable array.
Definition int.hh:840
static void run(const Options &opt, Script *s=nullptr)
Options for scripts with additional instance parameter
Definition driver.hh:834
Named values read from an instance.
Definition instance.hh:406
Exception for errors in specs and instance files
Definition instance.hh:337
virtual const char * what(void) const noexcept override
Return the full message.
Definition data.cpp:56
Passing integer arguments.
Definition int.hh:653
unsigned int size(void) const
Return size (cardinality) of set.
Computation spaces.
Definition core.hpp:1787
const char * instance_spec
Reader spec for DIMACS CNF files.
Definition sat.cpp:56
virtual Space * copy(void)
Perform copying during cloning.
Definition sat.cpp:132
virtual void print(std::ostream &os) const
Print solution.
Definition sat.cpp:138
Sat(Sat &s)
Constructor for cloning.
Definition sat.cpp:126
Sat(const InstanceOptions &opt)
The actual problem.
Definition sat.cpp:108
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:177
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:1002
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void clause(Home home, BoolOpType o, const BoolVarArgs &x, const BoolVarArgs &y, BoolVar z, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for Boolean clause with positive variables x and negative variables...
Definition bool.cpp:955
@ BOT_OR
Disjunction.
Definition int.hh:1252
int main(void)
Definition main.cpp:15
Gecode toplevel namespace
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition val.hpp:130
BoolVarBranch BOOL_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
Definition var.hpp:404
Options opt
The options.
Definition test.cpp:163