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

sudoku-set.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-10-20 15:28:46 +0200 (Thu, 20 Oct 2005) $ by $Author: zayenz $
00010  *     $Revision: 2391 $
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 "set.hh"
00023 #include "examples/support.hh"
00024 #include "minimodel.hh"
00025 
00026 #include "examples/sudoku.icc"
00027 
00036 class SudokuSet : public Example {
00037 protected:
00038   static const int n = 3;
00039   SetVarArray x;
00040 public:
00042   SudokuSet(const Options& opt)
00043     : x(this,n*n,IntSet::empty,1,n*n*n*n,9,9) {
00044 
00045     const int nn = n*n;
00046 
00047     IntSet row[9];
00048     IntSet col[9];
00049     IntSet block[9];
00050 
00051     // Set up the row and column set constants
00052     for (int i=0; i<9; i++) {
00053       IntSet dsr((i*nn)+1, (i*nn)+9);
00054       row[i] = dsr;
00055 
00056       int dsc_arr[9] = { 1+i, 10+i, 19+i, 28+i, 37+i, 46+i, 55+i, 64+i, 73+i };
00057       IntSet dsc(dsc_arr, 9);
00058 
00059       col[i] = dsc;
00060     }
00061 
00062     // Set up the block set constants
00063     for (int i=0; i<3; i++)
00064       for (int j=0; j<3; j++) {
00065         int dsb_arr[9] = {
00066           (j*27)+(i*3)+1, (j*27)+(i*3)+2, (j*27)+(i*3)+3,
00067           (j*27)+(i*3)+10, (j*27)+(i*3)+11, (j*27)+(i*3)+12,
00068           (j*27)+(i*3)+19, (j*27)+(i*3)+20, (j*27)+(i*3)+21
00069         };
00070         IntSet dsb(dsb_arr, 9);
00071         block[i*3+j]=dsb;
00072       }
00073 
00074     // All x must be pairwise disjoint
00075     for (int i=0; i<nn-1; i++)
00076       for (int j=i+1; j<nn; j++)
00077         rel(this, x[i], SRT_DISJ, x[j]);
00078     distinct(this, x, nn);
00079 
00080     // The x must intersect in exactly one element with each
00081     // row, column, and block
00082     for (int i=0; i<nn; i++)
00083       for (int j=0; j<nn; j++) {
00084         SetVar inter_row(this, IntSet::empty, 1, 9*9, 1, 1);
00085         rel(this, x[i], SOT_INTER, row[j], SRT_EQ, inter_row);
00086         SetVar inter_col(this, IntSet::empty, 1, 9*9, 1, 1);
00087         rel(this, x[i], SOT_INTER, col[j], SRT_EQ, inter_col);
00088         SetVar inter_block(this, IntSet::empty, 1, 9*9, 1, 1);
00089         rel(this, x[i], SOT_INTER, block[j], SRT_EQ, inter_block);
00090       }
00091 
00092     // Fill-in predefined fields
00093     for (int i=0; i<nn; i++)
00094       for (int j=0; j<nn; j++)
00095         if (examples[opt.size][i][j] != 0) {
00096           int idx = examples[opt.size][i][j]-1;
00097           dom(this, x[idx], SRT_SUP, (i+1)+(j*nn) );
00098         }
00099     
00100     branch(this, x, SETBVAR_NONE, SETBVAL_MIN);
00101   }
00102   
00104   SudokuSet(bool share, SudokuSet& s) : Example(share,s) {
00105     x.update(this, share, s.x);
00106   }
00107   
00109   virtual Space*
00110   copy(bool share) {
00111     return new SudokuSet(share,*this);
00112   }
00113   
00115   virtual void
00116   print(void) {
00117     std::cout << '\t';
00118     for (int i = 0; i<n*n*n*n; i++) {
00119       for (int j=0; j<n*n; j++) {
00120         if (x[j].contains(i+1)) {
00121           std::cout << j+1 << " ";
00122           break;
00123         }
00124       }
00125       if((i+1)%(n*n) == 0)
00126         std::cout << std::endl << '\t';
00127     }
00128     std::cout << std::endl;
00129   }
00130 };
00131 
00132 
00136 int
00137 main(int argc, char** argv) {
00138   Options opt("Sudoku (Set)");
00139   opt.iterations = 100;
00140   opt.size       = 0;
00141   opt.icl        = ICL_DOM;
00142   opt.solutions  = 1;
00143   opt.naive      = true;
00144   opt.parse(argc,argv);
00145   if (opt.size >= n_examples) {
00146     std::cerr << "Error: size must be between 0 and " 
00147               << n_examples-1 << std::endl;
00148     return 1;
00149   }
00150   Example::run<SudokuSet,DFS>(opt);
00151   return 0;
00152 }
00153 
00154 // STATISTICS: example-any
00155