Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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 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
50using namespace Gecode;
51
53
55class Sudoku : public Script {
56protected:
58 const int n;
59public:
60#ifdef GECODE_HAS_SET_VARS
62 enum {
66 };
67#endif
68 // Branching variants
69 enum {
75 };
76
78 Sudoku(const SizeOptions& opt)
79 : Script(opt),
80 n(example_size(examples[opt.size()])) {}
81
83 Sudoku(Sudoku& s) : Script(s), n(s.n) {}
84
85};
86
92class SudokuInt : virtual public Sudoku {
93protected:
96public:
97#ifdef GECODE_HAS_SET_VARS
99 enum {
102 };
103#endif
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) {
170 } else if (opt.branching() == BRANCH_SIZE) {
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
212private:
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
240class SudokuSet : virtual public Sudoku {
241protected:
244public:
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) {
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
357class SudokuMixed : public SudokuInt, public SudokuSet {
358public:
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
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
404int
405main(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
411 opt.model(Sudoku::MODEL_INT);
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");
416 opt.propagation(SudokuInt::PROP_NONE);
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
421 opt.branching(Sudoku::BRANCH_SIZE_AFC);
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()) {
437 break;
440 break;
443 break;
444 }
445#else
447#endif
448 return 0;
449}
450
451// STATISTICS: example-any
static void run(const Options &opt, Script *s=NULL)
Passing integer arguments.
Definition int.hh:634
Integer sets.
Definition int.hh:174
static const IntSet empty
Empty set.
Definition int.hh:283
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Integer variables.
Definition int.hh:371
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:573
Set variables
Definition set.hh:127
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1744
virtual Space * copy(void)
Perform copying during cloning.
SudokuInt(const SizeOptions &opt)
Constructor.
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.
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 SizeOptions &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 SizeOptions &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 unsigned int n_examples
The number of instances.
int example_size(const char *s)
The size of an instance.
Sudoku(const SizeOptions &opt)
Constructor.
const char * examples[]
The specifications.
int sudokuField(const char *s, int n, int i, int j)
Return value at position (i,j) in the example s of size n.
const int n
The size of the problem.
@ 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.
Sudoku(Sudoku &s)
Constructor for cloning s.
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
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:941
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:994
@ SOT_DUNION
Disjoint union.
Definition set.hh:668
@ SOT_INTER
Intersection
Definition set.hh:669
@ SRT_EQ
Equality ( )
Definition set.hh:650
@ SRT_SUP
Superset ( )
Definition set.hh:653
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
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
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
Select first unassigned variable SetVarBranch SET_VAR_NONE(void)
Definition var.hpp:96
Select variable with largest degree divided by domain size SetVarBranch SET_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr)
Definition var.hpp:221
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
Select variable with smallest unknown set SetVarBranch SET_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Definition var.hpp:206
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1943
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
Select variable with largest accumulated failure count with decay factor a d SetVarBranch SET_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Definition var.hpp:136
Include smallest element SetValBranch SET_VAL_MIN_INC(void)
Definition val.hpp:55
Select variable with largest accumulated failure count divided by domain size with decay factor a d SetVarBranch SET_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
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