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 "gecode/set.hh"
00026 #endif
00027
00028 #include "gecode/minimodel.hh"
00029
00030
00031 #include "examples/sudoku.icc"
00032
00033 #ifdef GECODE_HAVE_SET_VARS
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 IntVarArgs
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 IntVarArgs
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 #endif
00052
00061 class Sudoku : public Example {
00062 protected:
00063 const int n;
00064 IntVarArray x;
00065 public:
00066
00068 Sudoku(const Options& opt)
00069 : n(example_size(examples[opt.size])),
00070 x(this,n*n*n*n,1,n*n) {
00071 const int nn = n*n;
00072 MiniModel::Matrix<IntVarArray> m(x, nn, nn);
00073
00074
00075 for (int i=0; i<nn; i++) {
00076 distinct(this, m.row(i), opt.icl);
00077 distinct(this, m.col(i), opt.icl);
00078 }
00079
00080
00081 for (int i=0; i<nn; i+=n)
00082 for (int j=0; j<nn; j+=n) {
00083 distinct(this, m.slice(i, i+n, j, j+n), opt.icl);
00084 }
00085
00086 #ifdef GECODE_HAVE_SET_VARS
00087 if (!opt.naive) {
00088
00089 for (int b=0; b<n; b++) {
00090 int b1c = 0;
00091 int b2c = 0;
00092 IntVarArgs bc1(nn-n);
00093 IntVarArgs bc2(nn-n);
00094 IntVarArgs br1(nn-n);
00095 IntVarArgs br2(nn-n);
00096 for (int i=0; i<n; i++)
00097 for (int j=0; j<n; j++) {
00098 b1c = 0; b2c = 0;
00099 for (int k=0; k<n; k++) {
00100 if (k != j) {
00101 IntVarArgs bc1s = block_col(m, n, b, i, k);
00102 IntVarArgs br1s = block_row(m, n, b, i, k);
00103 for (int count=0; count<n; count++) {
00104 bc1[b1c] = bc1s[count];
00105 br1[b1c] = br1s[count];
00106 ++b1c;
00107 }
00108 }
00109 if (k != i) {
00110 IntVarArgs bc2s = block_col(m, n, b, k, j);
00111 IntVarArgs br2s = block_row(m, n, b, k, j);
00112 for (int count=0; count<n; count++) {
00113 bc2[b2c] = bc2s[count];
00114 br2[b2c] = br2s[count];
00115 ++b2c;
00116 }
00117 }
00118 }
00119 same(this, nn, bc1, bc2);
00120 same(this, nn, br1, br2);
00121 }
00122 }
00123 }
00124 #endif
00125
00126
00127 for (int i=0; i<nn; i++)
00128 for (int j=0; j<nn; j++)
00129 if (int v = value_at(examples[opt.size], nn, i, j))
00130 rel(this, m(i,j), IRT_EQ, v );
00131
00132 branch(this, x, BVAR_SIZE_MIN, BVAL_SPLIT_MIN);
00133 }
00134
00136 Sudoku(bool share, Sudoku& s) : Example(share,s), n(s.n) {
00137 x.update(this, share, s.x);
00138 }
00139
00141 virtual Space*
00142 copy(bool share) {
00143 return new Sudoku(share,*this);
00144 }
00145
00147 virtual void
00148 print(void) {
00149 std::cout << " ";
00150 for (int i = 0; i<n*n*n*n; i++) {
00151 if (x[i].assigned()) {
00152 if (x[i].val()<10)
00153 std::cout << x[i] << " ";
00154 else
00155 std::cout << (char)(x[i].val()+'A'-10) << " ";
00156 }
00157 else
00158 std::cout << ". ";
00159 if((i+1)%(n*n) == 0)
00160 std::cout << std::endl << " ";
00161 }
00162 std::cout << std::endl;
00163 }
00164 };
00165
00166
00170 int
00171 main(int argc, char** argv) {
00172 Options opt("Sudoku");
00173 opt.size = 0;
00174 opt.icl = ICL_DOM;
00175 opt.solutions = 1;
00176 opt.naive = true;
00177 opt.parse(argc,argv);
00178 if (opt.size >= n_examples) {
00179 std::cerr << "Error: size must be between 0 and "
00180 << n_examples-1 << std::endl;
00181 return 1;
00182 }
00183 Example::run<Sudoku,DFS>(opt);
00184 return 0;
00185 }
00186
00187
00188