00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
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
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
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
00081
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
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
00155