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
00036 class SudokuSet : public Example {
00037 protected:
00038 const int n;
00039 SetVarArray x;
00040 public:
00042 SudokuSet(const Options& opt)
00043 : n(example_size(examples[opt.size])),
00044 x(this,n*n,IntSet::empty,1,n*n*n*n,9,9) {
00045
00046 const int nn = n*n;
00047
00048 IntSet row[9];
00049 IntSet col[9];
00050 IntSet block[9];
00051
00052
00053 for (int i=0; i<9; i++) {
00054 IntSet dsr((i*nn)+1, (i*nn)+9);
00055 row[i] = dsr;
00056
00057 int dsc_arr[9] = { 1+i, 10+i, 19+i, 28+i, 37+i, 46+i, 55+i, 64+i, 73+i };
00058 IntSet dsc(dsc_arr, 9);
00059
00060 col[i] = dsc;
00061 }
00062
00063
00064 for (int i=0; i<3; i++)
00065 for (int j=0; j<3; j++) {
00066 int dsb_arr[9] = {
00067 (j*27)+(i*3)+1, (j*27)+(i*3)+2, (j*27)+(i*3)+3,
00068 (j*27)+(i*3)+10, (j*27)+(i*3)+11, (j*27)+(i*3)+12,
00069 (j*27)+(i*3)+19, (j*27)+(i*3)+20, (j*27)+(i*3)+21
00070 };
00071 IntSet dsb(dsb_arr, 9);
00072 block[i*3+j]=dsb;
00073 }
00074
00075
00076 for (int i=0; i<nn-1; i++)
00077 for (int j=i+1; j<nn; j++)
00078 rel(this, x[i], SRT_DISJ, x[j]);
00079 distinct(this, x, nn);
00080
00081
00082
00083 for (int i=0; i<nn; i++)
00084 for (int j=0; j<nn; j++) {
00085 SetVar inter_row(this, IntSet::empty, 1, 9*9, 1, 1);
00086 rel(this, x[i], SOT_INTER, row[j], SRT_EQ, inter_row);
00087 SetVar inter_col(this, IntSet::empty, 1, 9*9, 1, 1);
00088 rel(this, x[i], SOT_INTER, col[j], SRT_EQ, inter_col);
00089 SetVar inter_block(this, IntSet::empty, 1, 9*9, 1, 1);
00090 rel(this, x[i], SOT_INTER, block[j], SRT_EQ, inter_block);
00091 }
00092
00093
00094 for (int i=0; i<nn; i++)
00095 for (int j=0; j<nn; j++)
00096 if (int idx = value_at(examples[opt.size], nn, i, j))
00097 dom(this, x[idx-1], SRT_SUP, (i+1)+(j*nn) );
00098
00099 branch(this, x, SETBVAR_NONE, SETBVAL_MIN);
00100 }
00101
00103 SudokuSet(bool share, SudokuSet& s) : Example(share,s), n(s.n) {
00104 x.update(this, share, s.x);
00105 }
00106
00108 virtual Space*
00109 copy(bool share) {
00110 return new SudokuSet(share,*this);
00111 }
00112
00114 virtual void
00115 print(void) {
00116 std::cout << '\t';
00117 for (int i = 0; i<n*n*n*n; i++) {
00118 for (int j=0; j<n*n; j++) {
00119 if (x[j].contains(i+1)) {
00120 if (j+1<10)
00121 std::cout << j+1 << " ";
00122 else
00123 std::cout << (char)(j+1+'A'-10) << " ";
00124 break;
00125 }
00126 }
00127 if((i+1)%(n*n) == 0)
00128 std::cout << std::endl << '\t';
00129 }
00130 std::cout << std::endl;
00131 }
00132 };
00133
00134
00138 int
00139 main(int argc, char** argv) {
00140 Options opt("Sudoku (Set)");
00141 opt.iterations = 100;
00142 opt.size = 0;
00143 opt.icl = ICL_DOM;
00144 opt.solutions = 1;
00145 opt.naive = true;
00146 opt.parse(argc,argv);
00147 if (opt.size >= n_examples) {
00148 std::cerr << "Error: size must be between 0 and "
00149 << n_examples-1 << std::endl;
00150 return 1;
00151 }
00152 if (example_size(examples[opt.size]) != 3) {
00153 std::cerr << "Set-based version only available with exmples of size 9*9"
00154 << std::endl;
00155 return 2;
00156 }
00157 Example::run<SudokuSet,DFS>(opt);
00158 return 0;
00159 }
00160
00161
00162