Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
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 Lagerkvist <lagerkvist@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  * Christian Schulte <schulte@gecode.org>
7  *
8  * Copyright:
9  * Mikael 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.org
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 <string>
47 #include <cmath>
48 #include <cctype>
49 
50 using namespace Gecode;
51 
53 
55 class Sudoku : public Script {
56 protected:
58  const int n;
59 public:
60 #ifdef GECODE_HAS_SET_VARS
61  enum {
65  MODEL_MIXED
66  };
67 #endif
68  // Branching variants
69  enum {
74  BRANCH_AFC
75  };
76 
79  : Script(opt),
80  n(example_size(examples[opt.size()])) {}
81 
83  Sudoku(Sudoku& s) : Script(s), n(s.n) {}
84 
85 };
86 
92 class SudokuInt : virtual public Sudoku {
93 protected:
96 public:
97 #ifdef GECODE_HAS_SET_VARS
98  enum {
102  };
103 #endif
104  SudokuInt(const SizeOptions& opt)
106  : Sudoku(opt), x(*this, n*n*n*n, 1, n*n) {
107  const int nn = n*n;
108  Matrix<IntVarArray> m(x, nn, nn);
109 
110  // Constraints for rows and columns
111  for (int i=0; i<nn; i++) {
112  distinct(*this, m.row(i), opt.ipl());
113  distinct(*this, m.col(i), opt.ipl());
114  }
115 
116  // Constraints for squares
117  for (int i=0; i<nn; i+=n) {
118  for (int j=0; j<nn; j+=n) {
119  distinct(*this, m.slice(i, i+n, j, j+n), opt.ipl());
120  }
121  }
122 
123  // Fill-in predefined fields
124  for (int i=0; i<nn; i++)
125  for (int j=0; j<nn; j++)
126  if (int v = sudokuField(examples[opt.size()], nn, i, j))
127  rel(*this, m(i,j), IRT_EQ, v );
128 
129 #ifdef GECODE_HAS_SET_VARS
130  if (opt.propagation() == PROP_SAME) {
131  // Implied constraints linking squares and rows
132  for (int b=0; b<n; b++) {
133  int b1c = 0;
134  int b2c = 0;
135  IntVarArgs bc1(nn-n);
136  IntVarArgs bc2(nn-n);
137  IntVarArgs br1(nn-n);
138  IntVarArgs br2(nn-n);
139  for (int i=0; i<n; i++)
140  for (int j=0; j<n; j++) {
141  b1c = 0; b2c = 0;
142  for (int k=0; k<n; k++) {
143  if (k != j) {
144  IntVarArgs bc1s = block_col(m, b, i, k);
145  IntVarArgs br1s = block_row(m, b, i, k);
146  for (int count=0; count<n; count++) {
147  bc1[b1c] = bc1s[count];
148  br1[b1c] = br1s[count];
149  ++b1c;
150  }
151  }
152  if (k != i) {
153  IntVarArgs bc2s = block_col(m, b, k, j);
154  IntVarArgs br2s = block_row(m, b, k, j);
155  for (int count=0; count<n; count++) {
156  bc2[b2c] = bc2s[count];
157  br2[b2c] = br2s[count];
158  ++b2c;
159  }
160  }
161  }
162  same(*this, nn, bc1, bc2);
163  same(*this, nn, br1, br2);
164  }
165  }
166  }
167 #endif
168  if (opt.branching() == BRANCH_NONE) {
169  branch(*this, x, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
170  } else if (opt.branching() == BRANCH_SIZE) {
171  branch(*this, x, INT_VAR_SIZE_MIN(), INT_VAL_SPLIT_MIN());
172  } else if (opt.branching() == BRANCH_SIZE_DEGREE) {
174  } else if (opt.branching() == BRANCH_SIZE_AFC) {
175  branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
176  } else if (opt.branching() == BRANCH_AFC) {
177  branch(*this, x, INT_VAR_AFC_MAX(opt.decay()), INT_VAL_SPLIT_MIN());
178  }
179  }
180 
183  x.update(*this, s.x);
184  }
185 
187  virtual Space*
188  copy(void) {
189  return new SudokuInt(*this);
190  }
191 
193  virtual void
194  print(std::ostream& os) const {
195  os << " ";
196  for (int i = 0; i<n*n*n*n; i++) {
197  if (x[i].assigned()) {
198  if (x[i].val()<10)
199  os << x[i] << " ";
200  else
201  os << (char)(x[i].val()+'A'-10) << " ";
202  }
203  else
204  os << ". ";
205  if((i+1)%(n*n) == 0)
206  os << std::endl << " ";
207  }
208  os << std::endl;
209  }
210 
211 #ifdef GECODE_HAS_SET_VARS
212 private:
214  void same(Space& home, int nn, IntVarArgs a, IntVarArgs b) {
215  SetVar u(home, IntSet::empty, 1, nn);
216  rel(home, SOT_DUNION, a, u);
217  rel(home, SOT_DUNION, b, u);
218  }
219 
221  IntVarArgs
222  block_col(Matrix<IntVarArray> m, int bc, int i, int j) {
223  return m.slice(bc*n+i, bc*n+i+1, j*n, (j+1)*n);
224  }
225 
227  IntVarArgs
228  block_row(Matrix<IntVarArray> m, int br, int i, int j) {
229  return m.slice(j*n, (j+1)*n, br*n+i, br*n+i+1);
230  }
231 #endif
232 };
233 
234 #ifdef GECODE_HAS_SET_VARS
235 
240 class SudokuSet : virtual public Sudoku {
241 protected:
244 public:
247  : Sudoku(opt),
248  y(*this,n*n,IntSet::empty,1,n*n*n*n,
249  static_cast<unsigned int>(n*n),static_cast<unsigned int>(n*n)) {
250 
251  const int nn = n*n;
252 
253  Region r;
254  IntSet* row = r.alloc<IntSet>(nn);
255  IntSet* col = r.alloc<IntSet>(nn);
256  IntSet* block = r.alloc<IntSet>(nn);
257 
258  // Set up the row and column set constants
259  int* dsc = r.alloc<int>(nn);
260  for (int i=0; i<nn; i++) {
261  row[i] = IntSet((i*nn)+1, (i+1)*nn);
262 
263  for (int j=0; j<nn; j++) {
264  dsc[j] = (j*nn)+1+i;
265  }
266  col[i] = IntSet(dsc, nn);
267  }
268 
269  // Set up the block set constants
270  int* dsb_arr = r.alloc<int>(nn);
271  for (int i=0; i<n; i++) {
272  for (int j=0; j<n; j++) {
273 
274  for (int ii=0; ii<n; ii++) {
275  for (int jj=0; jj<n; jj++) {
276  dsb_arr[ii*n+jj] = j*nn*n+i*n+jj*nn+ii+1;
277  }
278  }
279  block[i*n+j] = IntSet(dsb_arr, nn);
280  }
281  }
282 
283  IntSet full(1, nn*nn);
284  // All x must be pairwise disjoint and partition the field indices
285  rel(*this, SOT_DUNION, y, SetVar(*this, full, full));
286 
287  // The x must intersect in exactly one element with each
288  // row, column, and block
289  for (int i=0; i<nn; i++)
290  for (int j=0; j<nn; j++) {
291  SetVar inter_row(*this, IntSet::empty, full, 1U, 1U);
292  rel(*this, y[i], SOT_INTER, row[j], SRT_EQ, inter_row);
293  SetVar inter_col(*this, IntSet::empty, full, 1U, 1U);
294  rel(*this, y[i], SOT_INTER, col[j], SRT_EQ, inter_col);
295  SetVar inter_block(*this, IntSet::empty, full, 1U, 1U);
296  rel(*this, y[i], SOT_INTER, block[j], SRT_EQ, inter_block);
297  }
298 
299  // Fill-in predefined fields
300  for (int i=0; i<nn; i++)
301  for (int j=0; j<nn; j++)
302  if (int idx = sudokuField(examples[opt.size()], nn, i, j))
303  dom(*this, y[idx-1], SRT_SUP, (i+1)+(j*nn) );
304 
305  if (opt.branching() == BRANCH_NONE) {
306  branch(*this, y, SET_VAR_NONE(), SET_VAL_MIN_INC());
307  } else if (opt.branching() == BRANCH_SIZE) {
308  branch(*this, y, SET_VAR_SIZE_MIN(), SET_VAL_MIN_INC());
309  } else if (opt.branching() == BRANCH_SIZE_DEGREE) {
311  } else if (opt.branching() == BRANCH_SIZE_AFC) {
312  branch(*this, y, SET_VAR_AFC_SIZE_MAX(opt.decay()), SET_VAL_MIN_INC());
313  } else if (opt.branching() == BRANCH_AFC) {
314  branch(*this, y, SET_VAR_AFC_MAX(opt.decay()), SET_VAL_MIN_INC());
315  }
316  }
317 
320  y.update(*this, s.y);
321  }
322 
324  virtual Space*
325  copy(void) {
326  return new SudokuSet(*this);
327  }
328 
330  virtual void
331  print(std::ostream& os) const {
332  os << '\t';
333  for (int i = 0; i<n*n*n*n; i++) {
334  for (int j=0; j<n*n; j++) {
335  if (y[j].contains(i+1)) {
336  if (j+1<10)
337  os << j+1 << " ";
338  else
339  os << (char)(j+1+'A'-10) << " ";
340  break;
341  }
342  }
343  if((i+1)%(n*n) == 0)
344  os << std::endl << '\t';
345  }
346  os << std::endl;
347  }
348 };
349 
350 
357 class SudokuMixed : public SudokuInt, public SudokuSet {
358 public:
361  : Sudoku(opt), SudokuInt(opt), SudokuSet(opt) {
362  const int nn = n*n;
363 
364  IntSet is0(0,0);
365  SetVar dummySet0(*this, is0, is0);
366  IntVar dummyInt0(*this, 0, 0);
367  SetVarArgs ys(nn+1);
368  ys[0] = dummySet0;
369  for (int i=0; i<nn; i++)
370  ys[i+1] = y[i];
371  IntVarArgs xs(nn*nn+1);
372  xs[0] = dummyInt0;
373  for (int i=0; i<nn*nn; i++)
374  xs[i+1] = x[i];
375 
376  channel(*this, xs, ys);
377 
378  IntArgs values(nn);
379  for (int i=0; i<nn; i++)
380  values[i] = i+1;
381  count(*this, x, IntSet(nn,nn), values, IPL_DOM);
382  }
383 
386  : Sudoku(s), SudokuInt(s), SudokuSet(s) {}
387 
389  virtual Space*
390  copy(void) {
391  return new SudokuMixed(*this);
392  }
393 
395  virtual void print(std::ostream& os) const { SudokuInt::print(os); }
396 
397 };
398 
399 #endif
400 
404 int
405 main(int argc, char* argv[]) {
406  SizeOptions opt("Sudoku");
407  opt.size(0);
408  opt.ipl(IPL_DOM);
409  opt.solutions(1);
410 #ifdef GECODE_HAS_SET_VARS
412  opt.model(Sudoku::MODEL_INT, "int", "use integer constraints");
413  opt.model(Sudoku::MODEL_SET, "set", "use set constraints");
414  opt.model(Sudoku::MODEL_MIXED, "mixed",
415  "use both integer and set constraints");
417  opt.propagation(SudokuInt::PROP_NONE, "none", "no additional constraints");
418  opt.propagation(SudokuInt::PROP_SAME, "same",
419  "additional \"same\" constraint for integer model");
420 #endif
422  opt.branching(Sudoku::BRANCH_NONE, "none", "none");
423  opt.branching(Sudoku::BRANCH_SIZE, "size", "min size");
424  opt.branching(Sudoku::BRANCH_SIZE_DEGREE, "sizedeg", "min size over degree");
425  opt.branching(Sudoku::BRANCH_SIZE_AFC, "sizeafc", "min size over afc");
426  opt.branching(Sudoku::BRANCH_AFC, "afc", "maximum afc");
427  opt.parse(argc,argv);
428  if (opt.size() >= n_examples) {
429  std::cerr << "Error: size must be between 0 and "
430  << n_examples-1 << std::endl;
431  return 1;
432  }
433 #ifdef GECODE_HAS_SET_VARS
434  switch (opt.model()) {
435  case Sudoku::MODEL_INT:
436  Script::run<SudokuInt,DFS,SizeOptions>(opt);
437  break;
438  case Sudoku::MODEL_SET:
439  Script::run<SudokuSet,DFS,SizeOptions>(opt);
440  break;
441  case Sudoku::MODEL_MIXED:
442  Script::run<SudokuMixed,DFS,SizeOptions>(opt);
443  break;
444  }
445 #else
446  Script::run<SudokuInt,DFS,SizeOptions>(opt);
447 #endif
448  return 0;
449 }
450 
451 // STATISTICS: example-any
SetVarArray y
The fields occupied by a certain number.
void size(unsigned int s)
Set default size.
Definition: options.hpp:586
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Select variable with largest degree divided by domain size.
Definition: var.hpp:221
Options for scripts with additional size parameter
Definition: driver.hh:675
virtual Space * copy(void)
Perform copying during cloning.
SetVarBranch SET_VAR_SIZE_MIN(BranchTbl tbl)
Definition: var.hpp:206
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
Example: Solving Sudoku puzzles using set constraints
Example: Solving Sudoku puzzles using both set and integer constraints
Use integer constraints.
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:183
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition: channel.cpp:41
void propagation(int v)
Set default propagation value.
Definition: options.hpp:203
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
Use "same" constraint with integer model.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:666
SudokuSet(const SizeOptions &opt)
Constructor.
Use set constraints.
Example: Solving Sudoku puzzles using integer constraints
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
SudokuSet(SudokuSet &s)
Constructor for cloning s.
SetVarBranch SET_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Definition: var.hpp:221
Slice< A > slice(int fc, int tc, int fr, int tr) const
Access slice of the matrix.
Definition: matrix.hpp:171
Integer variable array.
Definition: int.hh:763
virtual void print(std::ostream &os) const
Print solution.
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
Handle to region.
Definition: region.hpp:55
Superset ( )
Definition: set.hh:647
SetVarBranch SET_VAR_NONE(void)
Definition: var.hpp:96
IntVarArray x
Values for the fields.
Computation spaces.
Definition: core.hpp:1701
Parametric base-class for scripts.
Definition: driver.hh:729
virtual Space * copy(void)
Perform copying during cloning.
Use maximum afc.
void decay(double d)
Set default decay factor.
Definition: options.hpp:238
SudokuInt(SudokuInt &s)
Constructor for cloning s.
SudokuMixed(const SizeOptions &opt)
Constructor.
virtual void print(std::ostream &os) const
Print solution.
SetVarBranch SET_VAR_AFC_MAX(double d, BranchTbl tbl)
Definition: var.hpp:136
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count divided by domain size with decay factor d...
Definition: var.hpp:236
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Equality ( )
Definition: int.hh:926
Options opt
The options.
Definition: test.cpp:97
Gecode::IntArgs i({1, 2, 3, 4})
virtual Space * copy(void)
Perform copying during cloning.
SudokuMixed(SudokuMixed &s)
Constructor for cloning s.
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
unsigned int size(I &i)
Size of all ranges of range iterator i.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
Base class for Sudoku puzzles.
Intersection
Definition: set.hh:663
Integer sets.
Definition: int.hh:174
const int n
The size of the problem.
void branching(int v)
Set default branching value.
Definition: options.hpp:225
IntVarBranch INT_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:136
Passing integer variables.
Definition: int.hh:656
Passing integer arguments.
Definition: int.hh:628
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition: array.hpp:1899
SetValBranch SET_VAL_MIN_INC(void)
Definition: val.hpp:55
static const IntSet empty
Empty set.
Definition: int.hh:283
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
Sudoku(const SizeOptions &opt)
Constructor.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
const int v[7]
Definition: distinct.cpp:259
Passing set variables.
Definition: set.hh:488
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:206
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Set variables
Definition: set.hh:127
Disjoint union.
Definition: set.hh:662
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:177
int main(int argc, char *argv[])
Main-function.
Integer variables.
Definition: int.hh:371
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
Use lexicographic ordering.
Equality ( )
Definition: set.hh:644
void solutions(unsigned int n)
Set default number of solutions to search for.
Definition: options.hpp:283
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition: minimodel.hh:1993
Post propagator for SetVar x
Definition: set.hh:767
No additional constraints.
Sudoku(Sudoku &s)
Constructor for cloning s.
Matrix-interface for arrays.
Definition: minimodel.hh:2048
Set variable array
Definition: set.hh:570
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:75
void model(int v)
Set default model value.
Definition: options.hpp:177
Gecode toplevel namespace
SetVarBranch SET_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Definition: var.hpp:236
Use both integer and set constraints.
Use minimum size over afc.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Use minimum size over degree.
virtual void print(std::ostream &os) const
Print solution.
Use minimum size.