Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
sudoku.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 #include <string>
43 #include <cmath>
44 #include <cctype>
45 
46 using namespace Gecode;
47 
49 
55 class Sudoku : public Script {
56 protected:
58  const int n;
61 public:
62 
65  : Script(opt),
66  n(example_size(examples[opt.size()])),
67  x(*this, n*n*n*n, 1, n*n) {
68 
69  const int nn = n*n;
70  Matrix<IntVarArray> m(x, nn, nn);
71 
72  // Constraints for rows and columns
73  for (int i=0; i<nn; i++) {
74  distinct(*this, m.row(i), opt.ipl());
75  distinct(*this, m.col(i), opt.ipl());
76  }
77 
78  // Constraints for squares
79  for (int i=0; i<nn; i+=n) {
80  for (int j=0; j<nn; j+=n) {
81  distinct(*this, m.slice(i, i+n, j, j+n), opt.ipl());
82  }
83  }
84 
85  // Fill-in predefined fields
86  for (int i=0; i<nn; i++)
87  for (int j=0; j<nn; j++)
88  if (int v = sudokuField(examples[opt.size()], nn, i, j))
89  rel(*this, m(i,j), IRT_EQ, v );
90 
91  branch(*this, x, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
92  }
93 
95  Sudoku(Sudoku& s) : Script(s), n(s.n) {
96  x.update(*this, s.x);
97  }
98 
100  virtual Space*
101  copy(void) {
102  return new Sudoku(*this);
103  }
104 
106  virtual void
107  print(std::ostream& os) const {
108  os << " ";
109  for (int i = 0; i<n*n*n*n; i++) {
110  if (x[i].assigned()) {
111  if (x[i].val()<10)
112  os << x[i] << " ";
113  else
114  os << (char)(x[i].val()+'A'-10) << " ";
115  }
116  else
117  os << ". ";
118  if((i+1)%(n*n) == 0)
119  os << std::endl << " ";
120  }
121  os << std::endl;
122  }
123 
124 };
125 
129 int
130 main(int argc, char* argv[]) {
131  SizeOptions opt("Sudoku");
132  opt.size(0);
133  opt.ipl(IPL_DOM);
134  opt.solutions(1);
135  opt.parse(argc,argv);
136  if (opt.size() >= n_examples) {
137  std::cerr << "Error: size must be between 0 and "
138  << n_examples-1 << std::endl;
139  return 1;
140  }
141  Script::run<Sudoku,DFS,SizeOptions>(opt);
142  return 0;
143 }
144 
145 // STATISTICS: example-any
virtual void print(std::ostream &os) const
Print solution.
Definition: sudoku.cpp:107
Post propagator for SetVar x
Definition: set.hh:767
unsigned int size(I &i)
Size of all ranges of range iterator i.
Slice< A > row(int r) const
Access row r.
Definition: matrix.hpp:177
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
Computation spaces.
Definition: core.hpp:1742
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
IntVarArray x
Values for the fields.
Definition: sudoku.cpp:60
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
Integer variable array.
Definition: int.hh:763
virtual Space * copy(void)
Perform copying during cloning.
Definition: sudoku.cpp:101
Gecode toplevel namespace
Options opt
The options.
Definition: test.cpp:97
Parametric base-class for scripts.
Definition: driver.hh:729
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:548
Base class for Sudoku puzzles.
Slice< A > slice(int fc, int tc, int fr, int tr) const
Access slice of the matrix.
Definition: matrix.hpp:171
Matrix-interface for arrays.
Definition: minimodel.hh:2087
const int v[7]
Definition: distinct.cpp:259
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
Slice< A > col(int c) const
Access column c.
Definition: matrix.hpp:183
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
Equality ( )
Definition: int.hh:926
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
void solutions(unsigned int n)
Set default number of solutions to search for.
Definition: options.hpp:283
Sudoku(const SizeOptions &opt)
Constructor.
Definition: sudoku.cpp:64
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
int main(int argc, char *argv[])
Definition: test.cpp:208
Gecode::IntArgs i({1, 2, 3, 4})
Sudoku(Sudoku &s)
Constructor for cloning s.
Definition: sudoku.cpp:95
Options for scripts with additional size parameter
Definition: driver.hh:675