this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
5 *
6 * Copyright:
7 * Vincent Barichard, 2013
8 *
9 * Last modified:
10 * $Date$ by $Author$
11 * $Revision$
12 *
13 * This file is part of Quacode:
14 * http://quacode.barichard.com
15 *
16 * Permission is hereby granted, free of charge, to any person obtaining
17 * a copy of this software and associated documentation files (the
18 * "Software"), to deal in the Software without restriction, including
19 * without limitation the rights to use, copy, modify, merge, publish,
20 * distribute, sublicense, and/or sell copies of the Software, and to
21 * permit persons to whom the Software is furnished to do so, subject to
22 * the following conditions:
23 *
24 * The above copyright notice and this permission notice shall be
25 * included in all copies or substantial portions of the Software.
26 *
27 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
28 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
29 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
30 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
31 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
32 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
33 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34 *
35 */
36
37#include <iostream>
38#include <vector>
39
40#include <quacode/qspaceinfo.hh>
41#include <gecode/minimodel.hh>
42#include <gecode/driver.hh>
43
44
45using namespace Gecode;
46
47#ifdef GECODE_HAS_GIST
48namespace Gecode { namespace Driver {
49 /// Specialization for QDFS
50 template<typename S>
51 class GistEngine<QDFS<S> > {
52 public:
53 static void explore(S* root, const Gist::Options& opt) {
54 (void) Gist::explore(root, false, opt);
55 }
56 };
57}}
58#endif
59
60/**
61 * \brief Options taking one additional parameter
62 */
63class NimFiboOptions : public Options {
64public:
65 int n; /// Parameter to be given on the command line
66 /// Print strategy or not
67 Gecode::Driver::BoolOption _printStrategy;
68 /// Use cut or not
69 Gecode::Driver::BoolOption _cut;
70 /// Initialize options for example with name \a s
71 NimFiboOptions(const char* s, int n0)
72 : Options(s), n(n0),
73 _printStrategy("-printStrategy","Print strategy",false),
74 _cut("-cut","Use cut in problem model",true) {
75 add(_printStrategy);
76 add(_cut);
77 }
78 /// Parse options from arguments \a argv (number is \a argc)
79 void parse(int& argc, char* argv[]) {
80 Options::parse(argc,argv);
81 if (argc < 2)
82 return;
83 n = atoi(argv[1]);
84 }
85 /// Print help message
86 virtual void help(void) {
87 Options::help();
88 std::cerr << "\t(unsigned int) default: " << n << std::endl
89 << "\t\tnumber of initial matchs" << std::endl;
90 }
91 /// Return true if the strategy must be printed
92 bool printStrategy(void) const {
93 return _printStrategy.value();
94 }
95 /// Return true if cut must be used
96 bool cut(void) const {
97 return _cut.value();
98 }
99};
100
101/// Succeed the space
102static void gf_success(Space& home) {
103 Space::Branchers b(home);
104 while (b()) {
105 BrancherHandle bh(b.brancher());
106 ++b;
107 bh.kill(home);
108 }
109}
110
111/// Dummy function
112static void gf_dummy(Space& ) { }
113
114/// Adding cut
115static void cut(Space& home, const BoolExpr& expr) {
116 BoolVar o(home,0,1);
117 rel(home, o == expr);
118 when(home, o, &gf_success, &gf_dummy);
119}
120
121class QCSPNimFibo : public Script, public QSpaceInfo {
122 IntVarArray X;
123
124public:
125
126 QCSPNimFibo(const NimFiboOptions& opt) : Script(opt), QSpaceInfo()
127 {
128 std::cout << "Loading problem" << std::endl;
129 if (!opt.printStrategy()) strategyMethod(0); // disable build and print strategy
130 using namespace Int;
131 // Number of matches
132 int NMatchs = opt.n;
133 int nIterations = (NMatchs%2)?NMatchs:NMatchs+1;
134
135 IntVarArgs x;
136 X = IntVarArray(*this,nIterations,1,NMatchs-1);
137 x << X[0];
138
139 BoolVar o_im1(*this,1,1);
140 BoolExpr cutExpr1(BoolVar(*this,1,1));
141 BoolExpr cutExpr2(BoolVar(*this,1,1));
142 branch(*this, X[0], INT_VAR_NONE(), INT_VAL_MIN());
143
144 for (int i=1; i < nIterations; i++) {
145 BoolVar oi(*this,0,1), o1(*this,0,1), o2(*this,0,1);
146
147 x << X[i];
148
149 rel(*this, X[i], IRT_LQ, expr(*this, 2*X[i-1]), o1);
150 linear(*this, x, IRT_LQ, NMatchs, o2);
151
152 if (i%2) {
153 // Universal Player
154 setForAll(*this,X[i]);
155 rel(*this, o_im1 == ((o1 && o2) >> oi));
156 // Adding Cut
157 if (opt.cut())
158 cut(*this, cutExpr1 && cutExpr2 && !(o1 && o2)); // Universal player can't play
159 branch(*this, X[i], INT_VAR_NONE(), INT_VAL_MIN());
160 } else {
161 // Existantial Player
162 rel(*this, o_im1 == (o1 && o2 && oi));
163 branch(*this, X[i], INT_VAR_NONE(), INT_VAL_MIN());
164 }
165 cutExpr1 = cutExpr1 && o1;
166 cutExpr2 = o2;
167 o_im1 = oi;
168 }
169 }
170
171 QCSPNimFibo(bool share, QCSPNimFibo& p)
172 : Script(share,p), QSpaceInfo(*this,share,p)
173 {
174 X.update(*this,share,p.X);
175 }
176
177 virtual Space* copy(bool share) { return new QCSPNimFibo(share,*this); }
178
179
180 void print(std::ostream& os) const {
181 strategyPrint(os);
182 }
183};
184
185int main(int argc, char* argv[])
186{
187
188 NimFiboOptions opt("QCSP Nim-Fibo",3);
189 opt.parse(argc,argv);
190 Script::run<QCSPNimFibo,QDFS,NimFiboOptions>(opt);
191
192 return 0;
193}