Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

sudoku.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2005
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-11-28 13:56:08 +0100 (Mon, 28 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2654 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
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 // include the example specifications
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     // Constraints for rows and columns
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     // Constraints for squares
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       // Implied constraints linking squares and rows
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     // Fill-in predefined fields
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 // STATISTICS: example-any
00176