00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "examples/support.hh"
00023
00024 #ifdef GECODE_HAVE_SET_VARS
00025 #include "set.hh"
00026 #endif
00027
00028 #include "minimodel.hh"
00029
00030
00031 #include "examples/sudoku.icc"
00032
00033 IntVarArgs unionOfArgs(const IntVarArgs as, const IntVarArgs bs) {
00034 IntVarArgs res(as.size() + bs.size());
00035 for (int i=as.size(); i--;)
00036 res[i] = as[i];
00037 for (int i=bs.size(); i--;)
00038 res[as.size()+i] = bs[i];
00039 return res;
00040 }
00041
00042 #ifdef GECODE_HAVE_SET_VARS
00043 void same(Space* home, IntVarArgs as, IntVarArgs bs) {
00044 SetVar u(home, IntSet::empty, 1, 81);
00045 rel(home, SOT_DUNION, as, u);
00046 rel(home, SOT_DUNION, bs, u);
00047 }
00048 #endif
00049
00058 class Sudoku : public Example {
00059 protected:
00060 static const int n = 3;
00061 IntVarArray x;
00062 public:
00064 Sudoku(const Options& opt)
00065 : x(this,n*n*n*n,1,n*n) {
00066 const int nn = n*n;
00067 MiniModel::Matrix<IntVarArray> m(x, nn, nn);
00068
00069
00070 for (int i=0; i<nn; i++) {
00071 distinct(this, m.row(i), opt.icl);
00072 distinct(this, m.col(i), opt.icl);
00073 }
00074
00075
00076 for (int i=0; i<nn; i+=n)
00077 for (int j=0; j<nn; j+=n) {
00078 distinct(this, m.slice(i, i+n, j, j+n), opt.icl);
00079 }
00080
00081 #ifdef GECODE_HAVE_SET_VARS
00082 if (!opt.naive) {
00083
00084
00085 for (int i=0; i<nn; i+=n)
00086 for (int j=0; j<nn; j+=n) {
00087 MiniModel::Matrix<IntVarArgs> block = m.slice(i, i+n, j, j+n);
00088 for (int r1=0; r1<2; r1++)
00089 for (int r2=r1+1; r2<3; r2++) {
00090 IntVarArgs b1 = unionOfArgs(block.col(r1), block.col(r2));
00091 IntVarArgs b2 = unionOfArgs(block.row(r1), block.row(r2));
00092 IntVarArgs r(0);
00093 IntVarArgs c(0);
00094 switch (r1+r2) {
00095 case 1:
00096 r = unionOfArgs(m.slice(0,i,j+2,j+3), m.slice(i+n,nn,j+2,j+3));
00097 c = unionOfArgs(m.slice(i+2,i+3,0,j), m.slice(i+2,i+3,j+n,nn));
00098 assert(r.size()==6);
00099 break;
00100 case 2:
00101 r = unionOfArgs(m.slice(0,i,j+1,j+2), m.slice(i+n,nn,j+1,j+2));
00102 c = unionOfArgs(m.slice(i+1,i+2,0,j), m.slice(i+1,i+2,j+n,nn));
00103 assert(r.size()==6);
00104 break;
00105 case 3:
00106 r = unionOfArgs(m.slice(0,i,j+0,j+1), m.slice(i+n,nn,j+0,j+1));
00107 c = unionOfArgs(m.slice(i+0,i+1,0,j), m.slice(i+0,i+1,j+n,nn));
00108 assert(r.size()==6);
00109 break;
00110 default:
00111 assert(false);
00112 }
00113 same(this, r, b1);
00114 same(this, c, b2);
00115 }
00116 }
00117 }
00118 #endif
00119
00120
00121 for (int i=0; i<nn; i++)
00122 for (int j=0; j<nn; j++)
00123 if (examples[opt.size][i][j] != 0)
00124 rel(this, m(i,j), IRT_EQ, examples[opt.size][i][j]);
00125
00126 branch(this, x, BVAR_MIN_MIN, BVAL_SPLIT_MIN);
00127 }
00128
00130 Sudoku(bool share, Sudoku& s) : Example(share,s) {
00131 x.update(this, share, s.x);
00132 }
00133
00135 virtual Space*
00136 copy(bool share) {
00137 return new Sudoku(share,*this);
00138 }
00139
00141 virtual void
00142 print(void) {
00143 std::cout << '\t';
00144 for (int i = 0; i<n*n*n*n; i++) {
00145 std::cout << x[i] << " ";
00146 if((i+1)%(n*n) == 0)
00147 std::cout << std::endl << '\t';
00148 }
00149 std::cout << std::endl;
00150 }
00151 };
00152
00153
00157 int
00158 main(int argc, char** argv) {
00159 Options opt("Sudoku");
00160 opt.iterations = 1000;
00161 opt.size = 0;
00162 opt.icl = ICL_DOM;
00163 opt.solutions = 1;
00164 opt.naive = true;
00165 opt.parse(argc,argv);
00166 if (opt.size >= n_examples) {
00167 std::cerr << "Error: size must be between 0 and "
00168 << n_examples-1 << std::endl;
00169 return 1;
00170 }
00171 Example::run<Sudoku,DFS>(opt);
00172 return 0;
00173 }
00174
00175
00176