Generated on for Gecode by doxygen 1.17.0
sudoku-advanced.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 * Guido Tack <tack@gecode.dev>
6 * Christian Schulte <schulte@gecode.dev>
7 *
8 * Copyright:
9 * Mikael Zayenz Lagerkvist, 2005
10 * Guido Tack, 2005
11 * Christian Schulte, 2005
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.dev
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/driver.hh>
39#include <gecode/int.hh>
40#include <gecode/minimodel.hh>
41
42#ifdef GECODE_HAS_SET_VARS
43#include <gecode/set.hh>
44#endif
45
46#include <algorithm>
47#include <string>
48#include <cmath>
49#include <cctype>
50#include <cstring>
51
52using namespace Gecode;
53
55
65class Sudoku : public Script {
66protected:
68 int nn;
70 int bw;
72 int bh;
75public:
76#ifdef GECODE_HAS_SET_VARS
78 enum {
82 };
83#endif
84 // Branching variants
85 enum {
91 };
92
95 : Script(opt) {
96 SudokuInstance si(opt);
97 nn = si.nn; bw = si.bw; bh = si.bh;
98 givens = IntSharedArray(si.givens);
99 }
100
103 : Script(s), nn(s.nn), bw(s.bw), bh(s.bh), givens(s.givens) {}
104
105};
106
112class SudokuInt : virtual public Sudoku {
113protected:
116public:
117#ifdef GECODE_HAS_SET_VARS
119 enum {
122 };
123#endif
126 : Sudoku(opt), x(*this, nn*nn, 1, nn) {
128
129 // Constraints for rows and columns
130 for (int i=0; i<nn; i++) {
131 distinct(*this, m.row(i), opt.ipl());
132 distinct(*this, m.col(i), opt.ipl());
133 }
134
135 // Constraints for boxes
136 for (int i=0; i<nn; i+=bw) {
137 for (int j=0; j<nn; j+=bh) {
138 distinct(*this, m.slice(i, i+bw, j, j+bh), opt.ipl());
139 }
140 }
141
142 // Fill-in predefined fields
143 for (int i=0; i<nn; i++)
144 for (int j=0; j<nn; j++)
145 if (int v = givens[j*nn+i])
146 rel(*this, m(i,j), IRT_EQ, v );
147
148#ifdef GECODE_HAS_SET_VARS
149 if (opt.propagation() == PROP_SAME) {
150 // Implied constraints linking boxes with columns and rows: the
151 // fields of a line outside a box take the values that the fields of
152 // the box outside the line take
153 for (int l=0; l<nn; l++)
154 for (int j=0; j<std::max(bw,bh); j++) {
155 if (j < bw)
156 same(*this, nn, column_outside_box(m, l, j), box_outside_column(m, l, j));
157 if (j < bh)
158 same(*this, nn, row_outside_box(m, l, j), box_outside_row(m, l, j));
159 }
160 }
161#endif
162 if (opt.branching() == BRANCH_NONE) {
164 } else if (opt.branching() == BRANCH_SIZE) {
166 } else if (opt.branching() == BRANCH_SIZE_DEGREE) {
168 } else if (opt.branching() == BRANCH_SIZE_AFC) {
169 branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
170 } else if (opt.branching() == BRANCH_AFC) {
171 branch(*this, x, INT_VAR_AFC_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
172 }
173 }
174
177 x.update(*this, s.x);
178 }
179
181 virtual Space*
182 copy(void) {
183 return new SudokuInt(*this);
184 }
185
187 virtual void
188 print(std::ostream& os) const {
189 os << " ";
190 for (int i = 0; i<nn*nn; i++) {
191 if (x[i].assigned()) {
192 print_value(os, x[i].val());
193 os << " ";
194 }
195 else
196 os << ". ";
197 if((i+1)%nn == 0)
198 os << std::endl << " ";
199 }
200 os << std::endl;
201 }
202
203#ifdef GECODE_HAS_SET_VARS
204private:
206 void same(Space& home, int nn, IntVarArgs a, IntVarArgs b) {
207 SetVar u(home, IntSet::empty, 1, nn);
208 rel(home, SOT_DUNION, a, u);
209 rel(home, SOT_DUNION, b, u);
210 }
211
213 IntVarArgs
214 column_outside_box(const Matrix<IntVarArray>& m, int c, int j) const {
215 IntVarArgs a;
216 for (int k=0; k<bw; k++)
217 if (k != j)
218 a << m.slice(c, c+1, k*bh, (k+1)*bh);
219 return a;
220 }
221
223 IntVarArgs
224 box_outside_column(const Matrix<IntVarArray>& m, int c, int j) const {
225 IntVarArgs a;
226 int first = (c / bw) * bw;
227 for (int k=first; k<first+bw; k++)
228 if (k != c)
229 a << m.slice(k, k+1, j*bh, (j+1)*bh);
230 return a;
231 }
232
234 IntVarArgs
235 row_outside_box(const Matrix<IntVarArray>& m, int r, int j) const {
236 IntVarArgs a;
237 for (int k=0; k<bh; k++)
238 if (k != j)
239 a << m.slice(k*bw, (k+1)*bw, r, r+1);
240 return a;
241 }
242
244 IntVarArgs
245 box_outside_row(const Matrix<IntVarArray>& m, int r, int j) const {
246 IntVarArgs a;
247 int first = (r / bh) * bh;
248 for (int k=first; k<first+bh; k++)
249 if (k != r)
250 a << m.slice(j*bw, (j+1)*bw, k, k+1);
251 return a;
252 }
253#endif
254};
255
256#ifdef GECODE_HAS_SET_VARS
262class SudokuSet : virtual public Sudoku {
263protected:
266public:
269 : Sudoku(opt),
270 y(*this,nn,IntSet::empty,1,nn*nn,
271 static_cast<unsigned int>(nn),static_cast<unsigned int>(nn)) {
272
273 Region r;
274 IntSet* row = r.alloc<IntSet>(nn);
275 IntSet* col = r.alloc<IntSet>(nn);
276 IntSet* block = r.alloc<IntSet>(nn);
277
278 // Set up the row and column set constants
279 int* dsc = r.alloc<int>(nn);
280 for (int i=0; i<nn; i++) {
281 row[i] = IntSet((i*nn)+1, (i+1)*nn);
282
283 for (int j=0; j<nn; j++) {
284 dsc[j] = (j*nn)+1+i;
285 }
286 col[i] = IntSet(dsc, nn);
287 }
288
289 // Set up the block set constants, for the box in box column i and
290 // box row j
291 int* dsb_arr = r.alloc<int>(nn);
292 for (int i=0; i<bh; i++) {
293 for (int j=0; j<bw; j++) {
294
295 for (int ii=0; ii<bw; ii++) {
296 for (int jj=0; jj<bh; jj++) {
297 dsb_arr[ii*bh+jj] = (j*bh+jj)*nn+i*bw+ii+1;
298 }
299 }
300 block[i*bw+j] = IntSet(dsb_arr, nn);
301 }
302 }
303
304 IntSet full(1, nn*nn);
305 // All x must be pairwise disjoint and partition the field indices
306 rel(*this, SOT_DUNION, y, SetVar(*this, full, full));
307
308 // The x must intersect in exactly one element with each
309 // row, column, and block
310 for (int i=0; i<nn; i++)
311 for (int j=0; j<nn; j++) {
312 SetVar inter_row(*this, IntSet::empty, full, 1U, 1U);
313 rel(*this, y[i], SOT_INTER, row[j], SRT_EQ, inter_row);
314 SetVar inter_col(*this, IntSet::empty, full, 1U, 1U);
315 rel(*this, y[i], SOT_INTER, col[j], SRT_EQ, inter_col);
316 SetVar inter_block(*this, IntSet::empty, full, 1U, 1U);
317 rel(*this, y[i], SOT_INTER, block[j], SRT_EQ, inter_block);
318 }
319
320 // Fill-in predefined fields
321 for (int i=0; i<nn; i++)
322 for (int j=0; j<nn; j++)
323 if (int idx = givens[j*nn+i])
324 dom(*this, y[idx-1], SRT_SUP, (i+1)+(j*nn) );
325
326 if (opt.branching() == BRANCH_NONE) {
327 branch(*this, y, SET_VAR_NONE(), SET_VAL_MIN_INC());
328 } else if (opt.branching() == BRANCH_SIZE) {
330 } else if (opt.branching() == BRANCH_SIZE_DEGREE) {
332 } else if (opt.branching() == BRANCH_SIZE_AFC) {
333 branch(*this, y, SET_VAR_AFC_SIZE_MAX(opt.decay()), SET_VAL_MIN_INC());
334 } else if (opt.branching() == BRANCH_AFC) {
335 branch(*this, y, SET_VAR_AFC_MAX(opt.decay()), SET_VAL_MIN_INC());
336 }
337 }
338
341 y.update(*this, s.y);
342 }
343
345 virtual Space*
346 copy(void) {
347 return new SudokuSet(*this);
348 }
349
351 virtual void
352 print(std::ostream& os) const {
353 os << '\t';
354 for (int i = 0; i<nn*nn; i++) {
355 for (int j=0; j<nn; j++) {
356 if (y[j].contains(i+1)) {
357 print_value(os, j+1);
358 os << " ";
359 break;
360 }
361 }
362 if((i+1)%nn == 0)
363 os << std::endl << '\t';
364 }
365 os << std::endl;
366 }
367};
368
369
376class SudokuMixed : public SudokuInt, public SudokuSet {
377public:
380 : Sudoku(opt), SudokuInt(opt), SudokuSet(opt) {
381
382 IntSet is0(0,0);
383 SetVar dummySet0(*this, is0, is0);
384 IntVar dummyInt0(*this, 0, 0);
385 SetVarArgs ys(nn+1);
386 ys[0] = dummySet0;
387 for (int i=0; i<nn; i++)
388 ys[i+1] = y[i];
389 IntVarArgs xs(nn*nn+1);
390 xs[0] = dummyInt0;
391 for (int i=0; i<nn*nn; i++)
392 xs[i+1] = x[i];
393
394 channel(*this, xs, ys);
395
397 for (int i=0; i<nn; i++)
398 values[i] = i+1;
399 count(*this, x, IntSet(nn,nn), values, IPL_DOM);
400 }
401
405
407 virtual Space*
408 copy(void) {
409 return new SudokuMixed(*this);
410 }
411
413 virtual void print(std::ostream& os) const { SudokuInt::print(os); }
414
415};
416
417#endif
418
422int
423main(int argc, char* argv[]) {
424 InstanceOptions opt("Sudoku", instance_spec);
425 opt.instance("0");
426 opt.ipl(IPL_DOM);
427 opt.solutions(1);
428#ifdef GECODE_HAS_SET_VARS
429 opt.model(Sudoku::MODEL_INT);
430 opt.model(Sudoku::MODEL_INT, "int", "use integer constraints");
431 opt.model(Sudoku::MODEL_SET, "set", "use set constraints");
432 opt.model(Sudoku::MODEL_MIXED, "mixed",
433 "use both integer and set constraints");
434 opt.propagation(SudokuInt::PROP_NONE);
435 opt.propagation(SudokuInt::PROP_NONE, "none", "no additional constraints");
436 opt.propagation(SudokuInt::PROP_SAME, "same",
437 "additional \"same\" constraint for integer model");
438#endif
439 opt.branching(Sudoku::BRANCH_SIZE_AFC);
440 opt.branching(Sudoku::BRANCH_NONE, "none", "none");
441 opt.branching(Sudoku::BRANCH_SIZE, "size", "min size");
442 opt.branching(Sudoku::BRANCH_SIZE_DEGREE, "sizedeg", "min size over degree");
443 opt.branching(Sudoku::BRANCH_SIZE_AFC, "sizeafc", "min size over afc");
444 opt.branching(Sudoku::BRANCH_AFC, "afc", "maximum afc");
445 opt.parse(argc,argv);
446 try {
447 if (!SudokuInstance(opt).valid()) {
448 std::cerr << "Error: instance must be a number between 0 and " << n_examples-1 << " or a file" << std::endl;
449 return 1;
450 }
451 } catch (const Instance::Error& e) {
452 std::cerr << e.what() << std::endl;
453 return 1;
454 }
455#ifdef GECODE_HAS_SET_VARS
456 switch (opt.model()) {
459 break;
462 break;
465 break;
466 }
467#else
469#endif
470 return 0;
471}
472
473// STATISTICS: example-any
static void run(const Options &opt, Script *s=nullptr)
Options for scripts with additional instance parameter
Definition driver.hh:834
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
Integer sets.
Definition int.hh:179
static const IntSet empty
Empty set.
Definition int.hh:302
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
Matrix-interface for arrays.
Slice< A > slice(int fc, int tc, int fr, int tr) const
Access slice of the matrix.
Definition matrix.hpp:171
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Handle to region.
Definition region.hpp:55
Passing set variables.
Definition set.hh:491
Set variable array
Definition set.hh:575
Set variables
Definition set.hh:127
Computation spaces.
Definition core.hpp:1787
virtual Space * copy(void)
Perform copying during cloning.
virtual void print(std::ostream &os) const
Print solution.
SudokuInt(SudokuInt &s)
Constructor for cloning s.
@ PROP_NONE
No additional constraints.
@ PROP_SAME
Use "same" constraint with integer model.
IntVarArray x
Values for the fields.
SudokuInt(const InstanceOptions &opt)
Constructor.
SudokuMixed(SudokuMixed &s)
Constructor for cloning s.
virtual void print(std::ostream &os) const
Print solution.
virtual Space * copy(void)
Perform copying during cloning.
SudokuMixed(const InstanceOptions &opt)
Constructor.
SetVarArray y
The fields occupied by a certain number.
virtual Space * copy(void)
Perform copying during cloning.
virtual void print(std::ostream &os) const
Print solution.
SudokuSet(SudokuSet &s)
Constructor for cloning s.
SudokuSet(const InstanceOptions &opt)
Constructor.
int main(int argc, char *argv[])
Main-function.
@ MODEL_INT
Use integer constraints.
@ MODEL_SET
Use set constraints.
@ MODEL_MIXED
Use both integer and set constraints.
const char * instance_spec
Reader spec for sudoku files.
const unsigned int n_examples
The number of instances.
Sudoku(const InstanceOptions &opt)
Constructor.
void print_value(std::ostream &os, int v)
Print value v of a field, with the symbols of the scaled sudoku corpus.
int nn
The side of the grid.
int bh
The height of a box.
IntSharedArray givens
Given values in row-major order (0 for blank).
@ BRANCH_NONE
Use lexicographic ordering.
@ BRANCH_SIZE_AFC
Use minimum size over afc.
@ BRANCH_SIZE
Use minimum size.
@ BRANCH_SIZE_DEGREE
Use minimum size over degree.
@ BRANCH_AFC
Use maximum afc.
int bw
The width of a box.
Sudoku(Sudoku &s)
Constructor for cloning s.
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 rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( ).
Definition int.hh:1226
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
@ SOT_DUNION
Disjoint union.
Definition set.hh:669
@ SOT_INTER
Intersection
Definition set.hh:670
@ SRT_EQ
Equality ( ).
Definition set.hh:651
@ SRT_SUP
Superset ( ).
Definition set.hh:654
Gecode toplevel namespace
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition val.hpp:75
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
Definition var.hpp:236
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
SetVarBranch SET_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
SetVarBranch SET_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree divided by domain size.
Definition var.hpp:221
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Definition int.hh:1813
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition dom.cpp:40
IntVarBranch INT_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
Definition var.hpp:136
SetVarBranch SET_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest unknown set.
Definition var.hpp:206
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1936
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
SetVarBranch SET_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
Definition var.hpp:136
SetValBranch SET_VAL_MIN_INC(void)
Include smallest element.
Definition val.hpp:55
SetVarBranch SET_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
Definition var.hpp:236
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree divided by domain size.
Definition var.hpp:221
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
Gecode::FloatVal a(-8, 5)
const int r[4][2]
Definition dom.cpp:152