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 MatrixGameOptions : public Options {
64protected:
65 /// Optional file name
66 Gecode::Driver::StringValueOption _file;
67 /// Print strategy or not
68 Gecode::Driver::BoolOption _printStrategy;
69 /// Flag to known if we have to print initial board
70 Driver::BoolOption _printBoard;
71public:
72 int n; /// Parameter to be given on the command line
73 /// Initialize options for example with name \a s
74 MatrixGameOptions(const char* s, int n0, bool pb0)
75 : Options(s), _file("-file","File name for MatrixGameOptionsrix input"),
76 _printStrategy("-printStrategy","Print strategy",false),
77 _printBoard("-printBoard",
78 "whether to print initial board",pb0),
79 n(n0) {
80 add(_file);
81 add(_printStrategy);
82 add(_printBoard);
83 }
84 /// Parse options from arguments \a argv (number is \a argc)
85 void parse(int& argc, char* argv[]) {
86 Options::parse(argc,argv);
87 if (argc < 2)
88 return;
89 n = atoi(argv[1]);
90 }
91 /// Print help message
92 virtual void help(void) {
93 Options::help();
94 std::cerr << "\t(unsigned int) default: " << n << std::endl
95 << "\t\tDepth of the matrix" << std::endl;
96 }
97 /// Return file name
98 const char* file(void) const {
99 return _file.value();
100 }
101 /// Return true if the strategy must be printed
102 bool printStrategy(void) const {
103 return _printStrategy.value();
104 }
105 /// Return true if we have to print initial board
106 bool printBoard(void) const {
107 return _printBoard.value();
108 }
109};
110
111class QCSPMatrixGame : public Script, public QSpaceInfo {
112 IntVarArray X;
113
114public:
115
116 QCSPMatrixGame(const MatrixGameOptions& opt) : Script(opt), QSpaceInfo()
117 {
118 std::cout << "Loading problem" << std::endl;
119 if (!opt.printStrategy()) strategyMethod(0); // disable build and print strategy
120 using namespace Int;
121 int depth = opt.n;// Size of the matrix is 2^depth. Large values may take long to solve...
122 int boardSize = (int)pow((double)2,(double)depth);
123 std::srand(static_cast<unsigned int>(std::time(NULL)));
124
125 // If a file is given we take the matrix from the file
126 bool bFile = false;
127 std::vector<int> tab;
128 if (opt.file() != NULL) {
129 std::ifstream inS(opt.file());
130 if(!inS.is_open())
131 bFile = false;
132 else {
133 bFile = true;
134 int x;
135 while (inS >> x) tab.push_back(x);
136 boardSize = (int)sqrt(tab.size());
137 depth = (int) (log(boardSize) / log(2));
138 }
139 }
140
141 IntArgs board(boardSize*boardSize);
142 for (int i=0; i<boardSize; i++)
143 for (int j=0; j<boardSize; j++)
144 if (bFile)
145 board[j*boardSize+i] = tab[j*boardSize+i];
146 else
147 board[j*boardSize+i] = (int)( (double)rand() / ((double)RAND_MAX + 1) * 50 ) < 25 ? 0:1;
148
149 int nbDecisionVar = 2*depth;
150 IntArgs access(nbDecisionVar);
151 access[nbDecisionVar-1]=1;
152 access[nbDecisionVar-2]=boardSize;
153 for (int i=nbDecisionVar-3; i>=0; i--)
154 access[i]=access[i+2]*2;
155
156 // Print initial board
157 if (opt.printBoard()) {
158 for (int i=0; i<boardSize; i++)
159 {
160 for (int j=0; j<boardSize; j++)
161 std::cout << board[i*boardSize+j] << " ";
162 std::cout << std::endl;
163 }
164 std::cout << std::endl;
165 }
166
167 // Defining the player variables
168 IntVarArgs x;
169 X = IntVarArray(*this,nbDecisionVar,0,1);
170 for (int i=0; i<nbDecisionVar; i++)
171 {
172 x << X[i];
173 if ((i%2) == 1) setForAll(*this, X[i]);
174 }
175
176 // Goal constaints
177 IntVar cstUn(*this,1,1);
178 IntVar boardIdx(*this,0,boardSize*boardSize);
179 linear(*this, access, x, IRT_EQ, boardIdx, IPL_DOM);
180 element(*this, board, boardIdx, cstUn, IPL_DOM);
181
182 branch(*this, X, INT_VAR_NONE(), INT_VAL_MIN());
183 }
184
185 QCSPMatrixGame(bool share, QCSPMatrixGame& p)
186 : Script(share,p), QSpaceInfo(*this,share,p)
187 {
188 X.update(*this,share,p.X);
189 }
190
191 virtual Space* copy(bool share) { return new QCSPMatrixGame(share,*this); }
192
193
194 void print(std::ostream& os) const {
195 strategyPrint(os);
196 }
197};
198
199int main(int argc, char* argv[])
200{
201
202 MatrixGameOptions opt("QCSP Matrix-Game",5,false);
203 opt.parse(argc,argv);
204 Script::run<QCSPMatrixGame,QDFS,MatrixGameOptions>(opt);
205
206 return 0;
207}