this repo has no description
dekker.one
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
52#include <examples/sudoku-instances.hh>
53
54/// Base class for %Sudoku puzzles
55class Sudoku : public Script {
56protected:
57 /// The size of the problem
58 const int n;
59public:
60#ifdef GECODE_HAS_SET_VARS
61 /// Model variants
62 enum {
63 MODEL_INT, ///< Use integer constraints
64 MODEL_SET, ///< Use set constraints
65 MODEL_MIXED ///< Use both integer and set constraints
66 };
67#endif
68 // Branching variants
69 enum {
70 BRANCH_NONE, ///< Use lexicographic ordering
71 BRANCH_SIZE, ///< Use minimum size
72 BRANCH_SIZE_DEGREE, ///< Use minimum size over degree
73 BRANCH_SIZE_AFC, ///< Use minimum size over afc
74 BRANCH_AFC ///< Use maximum afc
75 };
76
77 /// Constructor
78 Sudoku(const SizeOptions& opt)
79 : Script(opt),
80 n(example_size(examples[opt.size()])) {}
81
82 /// Constructor for cloning \a s
83 Sudoku(Sudoku& s) : Script(s), n(s.n) {}
84
85};
86
87/**
88 * \brief %Example: Solving %Sudoku puzzles using integer constraints
89 *
90 * \ingroup Example
91 */
92class SudokuInt : virtual public Sudoku {
93protected:
94 /// Values for the fields
95 IntVarArray x;
96public:
97#ifdef GECODE_HAS_SET_VARS
98 /// Propagation variants
99 enum {
100 PROP_NONE, ///< No additional constraints
101 PROP_SAME, ///< Use "same" constraint with integer model
102 };
103#endif
104 /// Constructor
105 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) {
173 branch(*this, x, INT_VAR_DEGREE_SIZE_MAX(), INT_VAL_SPLIT_MIN());
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
181 /// Constructor for cloning \a s
182 SudokuInt(SudokuInt& s) : Sudoku(s) {
183 x.update(*this, s.x);
184 }
185
186 /// Perform copying during cloning
187 virtual Space*
188 copy(void) {
189 return new SudokuInt(*this);
190 }
191
192 /// Print solution
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:
213 /// Post the constraint that \a a and \a b take the same values
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
220 /// Extract column \a bc from block starting at (\a i,\a j)
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
226 /// Extract row \a br from block starting at (\a i,\a j)
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/**
236 * \brief %Example: Solving %Sudoku puzzles using set constraints
237 *
238 * \ingroup Example
239 */
240class SudokuSet : virtual public Sudoku {
241protected:
242 /// The fields occupied by a certain number
243 SetVarArray y;
244public:
245 /// Constructor
246 SudokuSet(const SizeOptions& opt)
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) {
310 branch(*this, y, SET_VAR_DEGREE_SIZE_MAX(), SET_VAL_MIN_INC());
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
318 /// Constructor for cloning \a s
319 SudokuSet(SudokuSet& s) : Sudoku(s) {
320 y.update(*this, s.y);
321 }
322
323 /// Perform copying during cloning
324 virtual Space*
325 copy(void) {
326 return new SudokuSet(*this);
327 }
328
329 /// Print solution
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
351/**
352 * \brief %Example: Solving %Sudoku puzzles using both set and integer
353 * constraints
354 *
355 * \ingroup Example
356 */
357class SudokuMixed : public SudokuInt, public SudokuSet {
358public:
359 /// Constructor
360 SudokuMixed(const SizeOptions& opt)
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
384 /// Constructor for cloning \a s
385 SudokuMixed(SudokuMixed& s)
386 : Sudoku(s), SudokuInt(s), SudokuSet(s) {}
387
388 /// Perform copying during cloning
389 virtual Space*
390 copy(void) {
391 return new SudokuMixed(*this);
392 }
393
394 /// Print solution
395 virtual void print(std::ostream& os) const { SudokuInt::print(os); }
396
397};
398
399#endif
400
401/** \brief Main-function
402 * \relates Sudoku
403 */
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()) {
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