00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "gecode/set.hh"
00023 #include "examples/support.hh"
00024 #include "gecode/minimodel.hh"
00025
00026 #include "examples/sudoku.icc"
00027
00034 void same(Space* home, int nn, IntVarArgs a, IntVarArgs b) {
00035 SetVar u(home, IntSet::empty, 1, nn);
00036 rel(home, SOT_DUNION, a, u);
00037 rel(home, SOT_DUNION, b, u);
00038 }
00039
00040 MiniModel::Matrix<IntVarArray>::Slice
00041 block_col(MiniModel::Matrix<IntVarArray> m,
00042 int n, int bc, int i, int j) {
00043 return m.slice(bc*n+i, bc*n+i+1, j*n, (j+1)*n);
00044 }
00045
00046 MiniModel::Matrix<IntVarArray>::Slice
00047 block_row(MiniModel::Matrix<IntVarArray> m,
00048 int n, int br, int i, int j) {
00049 return m.slice(j*n, (j+1)*n, br*n+i, br*n+i+1);
00050 }
00051
00063 class SudokuMixed : public Example {
00064 protected:
00065 const int n;
00066 SetVarArray x;
00067 public:
00069 SudokuMixed(const Options& opt)
00070 : n(example_size(examples[opt.size])),
00071 x(this,n*n,IntSet::empty,1,n*n*n*n,9,9) {
00072
00073 const int nn = n*n;
00074
00075
00076
00077
00078
00079
00080 IntVarArray y(this,n*n*n*n,1,n*n);
00081
00082 MiniModel::Matrix<IntVarArray> m(y, nn, nn);
00083
00084
00085 for (int i=0; i<nn; i++) {
00086 distinct(this, m.row(i), opt.icl);
00087 distinct(this, m.col(i), opt.icl);
00088 }
00089
00090
00091 for (int i=0; i<nn; i+=n)
00092 for (int j=0; j<nn; j+=n) {
00093 distinct(this, m.slice(i, i+n, j, j+n), opt.icl);
00094 }
00095
00096
00097 for (int i=0; i<nn; i++)
00098 for (int j=0; j<nn; j++)
00099 if (int v = value_at(examples[opt.size], nn, i, j))
00100 rel(this, m(i,j), IRT_EQ, v );
00101
00102
00103 for (int b=0; b<n; b++) {
00104 int b1c = 0;
00105 int b2c = 0;
00106 IntVarArgs bc1(nn-n);
00107 IntVarArgs bc2(nn-n);
00108 IntVarArgs br1(nn-n);
00109 IntVarArgs br2(nn-n);
00110 for (int i=0; i<n; i++)
00111 for (int j=0; j<n; j++) {
00112 b1c = 0; b2c = 0;
00113 for (int k=0; k<n; k++) {
00114 if (k != j) {
00115 IntVarArgs bc1s = block_col(m, n, b, i, k);
00116 IntVarArgs br1s = block_row(m, n, b, i, k);
00117 for (int count=0; count<n; count++) {
00118 bc1[b1c] = bc1s[count];
00119 br1[b1c] = br1s[count];
00120 ++b1c;
00121 }
00122 }
00123 if (k != i) {
00124 IntVarArgs bc2s = block_col(m, n, b, k, j);
00125 IntVarArgs br2s = block_row(m, n, b, k, j);
00126 for (int count=0; count<n; count++) {
00127 bc2[b2c] = bc2s[count];
00128 br2[b2c] = br2s[count];
00129 ++b2c;
00130 }
00131 }
00132 }
00133 same(this, nn, bc1, bc2);
00134 same(this, nn, br1, br2);
00135 }
00136 }
00137
00138
00139
00140
00141
00142
00143
00144 IntSet is0(0,0);
00145 SetVar dummySet0(this, is0, is0);
00146 IntVar dummyInt0(this, 0, 0);
00147 SetVarArgs xs(nn+1);
00148 xs[0] = dummySet0;
00149 for (int i=0; i<nn; i++)
00150 xs[i+1] = x[i];
00151 IntVarArgs ys(nn*nn+1);
00152 ys[0] = dummyInt0;
00153 for (int i=0; i<nn*nn; i++)
00154 ys[i+1] = y[i];
00155
00156 channel(this, ys, xs);
00157
00158 gcc(this, y, 9, ICL_DOM);
00159
00160
00161
00162
00163
00164
00165
00166
00167 IntSet row[9];
00168 IntSet col[9];
00169 IntSet block[9];
00170
00171
00172 for (int i=0; i<9; i++) {
00173 IntSet dsr((i*nn)+1, (i*nn)+9);
00174 row[i] = dsr;
00175
00176 int dsc_arr[9] = { 1+i, 10+i, 19+i, 28+i, 37+i, 46+i, 55+i, 64+i, 73+i };
00177 IntSet dsc(dsc_arr, 9);
00178
00179 col[i] = dsc;
00180 }
00181
00182
00183 for (int i=0; i<3; i++)
00184 for (int j=0; j<3; j++) {
00185 int dsb_arr[9] = {
00186 (j*27)+(i*3)+1, (j*27)+(i*3)+2, (j*27)+(i*3)+3,
00187 (j*27)+(i*3)+10, (j*27)+(i*3)+11, (j*27)+(i*3)+12,
00188 (j*27)+(i*3)+19, (j*27)+(i*3)+20, (j*27)+(i*3)+21
00189 };
00190 IntSet dsb(dsb_arr, 9);
00191 block[i*3+j]=dsb;
00192 }
00193
00194
00195 for (int i=0; i<nn-1; i++)
00196 for (int j=i+1; j<nn; j++)
00197 rel(this, x[i], SRT_DISJ, x[j]);
00198 distinct(this, x, nn);
00199
00200
00201
00202 for (int i=0; i<nn; i++)
00203 for (int j=0; j<nn; j++) {
00204 SetVar inter_row(this, IntSet::empty, 1, 9*9, 1, 1);
00205 rel(this, x[i], SOT_INTER, row[j], SRT_EQ, inter_row);
00206 SetVar inter_col(this, IntSet::empty, 1, 9*9, 1, 1);
00207 rel(this, x[i], SOT_INTER, col[j], SRT_EQ, inter_col);
00208 SetVar inter_block(this, IntSet::empty, 1, 9*9, 1, 1);
00209 rel(this, x[i], SOT_INTER, block[j], SRT_EQ, inter_block);
00210 }
00211
00212
00213 for (int i=0; i<nn; i++)
00214 for (int j=0; j<nn; j++)
00215 if (int idx = value_at(examples[opt.size], nn, i, j))
00216 dom(this, x[idx-1], SRT_SUP, (i+1)+(j*nn) );
00217
00218 branch(this, x, SETBVAR_NONE, SETBVAL_MIN);
00219 }
00220
00222 SudokuMixed(bool share, SudokuMixed& s) : Example(share,s), n(s.n) {
00223 x.update(this, share, s.x);
00224 }
00225
00227 virtual Space*
00228 copy(bool share) {
00229 return new SudokuMixed(share,*this);
00230 }
00231
00233 virtual void
00234 print(void) {
00235 std::cout << '\t';
00236 for (int i = 0; i<n*n*n*n; i++) {
00237 for (int j=0; j<n*n; j++) {
00238 if (x[j].contains(i+1)) {
00239 if (j+1<10)
00240 std::cout << j+1 << " ";
00241 else
00242 std::cout << (char)(j+1+'A'-10) << " ";
00243 break;
00244 }
00245 }
00246 if((i+1)%(n*n) == 0)
00247 std::cout << std::endl << '\t';
00248 }
00249 std::cout << std::endl;
00250 }
00251
00252 };
00253
00254
00258 int
00259 main(int argc, char** argv) {
00260 Options opt("Sudoku (Mixed Model)");
00261 opt.iterations = 200;
00262 opt.size = 0;
00263 opt.icl = ICL_DOM;
00264 opt.solutions = 1;
00265 opt.naive = true;
00266 opt.parse(argc,argv);
00267 if (opt.size >= n_examples) {
00268 std::cerr << "Error: size must be between 0 and "
00269 << n_examples-1 << std::endl;
00270 return 1;
00271 }
00272 if (example_size(examples[opt.size]) != 3) {
00273 std::cerr << "Set-based version only available with exmples of size 9*9"
00274 << std::endl;
00275 return 2;
00276 }
00277 Example::run<SudokuMixed,DFS>(opt);
00278 return 0;
00279 }
00280
00281
00282