00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 #include <gecode/driver.hh>
00041 #include <gecode/int.hh>
00042 #include <gecode/minimodel.hh>
00043 #include <gecode/graph.hh>
00044
00045 using namespace Gecode;
00046
00047
00056 class Warnsdorff : public Brancher {
00057 protected:
00059 ViewArray<Int::IntView> x;
00061 mutable int start;
00063 class Choice : public Gecode::Choice {
00064 public:
00066 int pos;
00068 int val;
00072 Choice(const Brancher& b, int pos0, int val0)
00073 : Gecode::Choice(b,2), pos(pos0), val(val0) {}
00075 virtual size_t size(void) const {
00076 return sizeof(Choice);
00077 }
00078 };
00079
00081 Warnsdorff(Space& home, ViewArray<Int::IntView>& xv)
00082 : Brancher(home), x(xv), start(0) {}
00084 Warnsdorff(Space& home, bool share, Warnsdorff& b)
00085 : Brancher(home, share, b), start(b.start) {
00086 x.update(home, share, b.x);
00087 }
00088 public:
00090 virtual bool status(const Space&) const {
00091
00092 while (true) {
00093 if (!x[start].assigned())
00094 return true;
00095 start = x[start].val();
00096 if (start == 0)
00097 return false;
00098 }
00099 }
00101 virtual Gecode::Choice* choice(Space&) {
00102 Int::ViewValues<Int::IntView> iv(x[start]);
00103 int n = iv.val();
00104 unsigned int min = x[n].size();
00105 ++iv;
00106
00107 while (iv()) {
00108 if (x[iv.val()].size() < min) {
00109 n = iv.val();
00110 min = x[n].size();
00111 }
00112 ++iv;
00113 }
00114 return new Choice(*this, start, n);
00115 }
00117 virtual ExecStatus commit(Space& home, const Gecode::Choice& _c,
00118 unsigned int a) {
00119 const Choice& c = static_cast<const Choice&>(_c);
00120 if (a == 0)
00121 return me_failed(x[c.pos].eq(home, c.val)) ? ES_FAILED : ES_OK;
00122 else
00123 return me_failed(x[c.pos].nq(home, c.val)) ? ES_FAILED : ES_OK;
00124 }
00126 virtual Actor* copy(Space& home, bool share) {
00127 return new (home) Warnsdorff(home, share, *this);
00128 }
00130 static void post(Space& home, const IntVarArgs& x) {
00131 ViewArray<Int::IntView> xv(home, x);
00132 (void) new (home) Warnsdorff(home, xv);
00133 }
00135 virtual size_t dispose(Space&) {
00136 return sizeof(*this);
00137 }
00138 };
00139
00140
00142 class Knights : public Script {
00143 protected:
00145 const int n;
00147 IntVarArray succ;
00148 public:
00150 enum {
00151 PROP_REIFIED,
00152 PROP_CIRCUIT
00153 };
00155 enum {
00156 BRANCH_NAIVE,
00157 BRANCH_WARNSDORFF,
00158 };
00160 int
00161 field(int x, int y) const {
00162 return x*n+y;
00163 }
00165 void
00166 neighbours(int f, int nbs[8], int& n_nbs) {
00167 n_nbs=0;
00168 int x = f / n;
00169 int y = f % n;
00170 for (int i=0;i<8;i++) {
00171 static const int moves[8][2] = {
00172 {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1}
00173 };
00174 int nx=x+moves[i][0];
00175 int ny=y+moves[i][1];
00176 if ((nx >= 0) && (nx < n) && (ny >= 0) && (ny < n))
00177 nbs[n_nbs++]=field(nx,ny);
00178 }
00179 }
00181 Knights(const SizeOptions& opt)
00182 : n(opt.size()), succ(*this,n*n,0,n*n-1) {
00183 switch (opt.branching()) {
00184 case BRANCH_NAIVE:
00185 branch(*this, succ, INT_VAR_NONE, INT_VAL_MIN);
00186 break;
00187 case BRANCH_WARNSDORFF:
00188 Warnsdorff::post(*this, succ);
00189 break;
00190 }
00191 }
00193 Knights(bool share, Knights& s) : Script(share,s), n(s.n) {
00194 succ.update(*this, share, s.succ);
00195 }
00197 virtual void
00198 print(std::ostream& os) const {
00199 int* jump = new int[n*n];
00200 {
00201 int j=0;
00202 for (int i=0; i<n*n; i++) {
00203 jump[j]=i; j=succ[j].min();
00204 }
00205 }
00206 os << "\t";
00207 for (int i = 0; i < n; i++) {
00208 for (int j = 0; j < n; j++) {
00209 os.width(3);
00210 os << jump[field(i,j)] << " ";
00211 }
00212 os << std::endl << "\t";
00213 }
00214 os << std::endl;
00215 delete [] jump;
00216 }
00217 };
00218
00229 class KnightsReified : public Knights {
00230 public:
00231 KnightsReified(const SizeOptions& opt) : Knights(opt) {
00232 const int nn = n*n;
00233
00234
00235 IntVarArgs jump(nn);
00236 IntVarArgs pred(nn);
00237
00238 for (int i = nn; i--; ) {
00239 IntVar p(*this,0,nn-1); pred[i]=p;
00240 IntVar j(*this,0,nn-1); jump[i]=j;
00241 }
00242
00243
00244 rel(*this, jump[field(0,0)], IRT_EQ, 0);
00245 rel(*this, jump[field(1,2)], IRT_EQ, 1);
00246
00247 distinct(*this, jump, opt.icl());
00248 channel(*this, succ, pred, opt.icl());
00249
00250 for (int f = 0; f < nn; f++) {
00251
00252 int nbs[8]; int n_nbs = 0;
00253 neighbours(f, nbs, n_nbs);
00254 for (int i=n_nbs; i--; )
00255 rel(*this,
00256 post(*this, ~(jump[nbs[i]]-jump[f] == 1)),
00257 BOT_XOR,
00258 post(*this, ~(jump[nbs[i]]-jump[f] == 1-nn)),
00259 post(*this, ~(succ[f] == nbs[i])));
00260
00261 IntSet ds(nbs, n_nbs);
00262 dom(*this, pred[f], ds);
00263 dom(*this, succ[f], ds);
00264 rel(*this, succ[f], IRT_NQ, pred[f]);
00265 }
00266 }
00268 KnightsReified(bool share, KnightsReified& s) : Knights(share,s) {}
00270 virtual Space*
00271 copy(bool share) {
00272 return new KnightsReified(share,*this);
00273 }
00274 };
00275
00286 class KnightsCircuit : public Knights {
00287 public:
00288 KnightsCircuit(const SizeOptions& opt) : Knights(opt) {
00289
00290 rel(*this, succ[0], IRT_EQ, field(1,2));
00291
00292 circuit(*this, succ, opt.icl());
00293
00294 for (int f = 0; f < n*n; f++) {
00295
00296 int nbs[8]; int n_nbs = 0;
00297 neighbours(f, nbs, n_nbs);
00298 IntSet ds(nbs, n_nbs);
00299 dom(*this, succ[f], ds);
00300 }
00301 }
00303 KnightsCircuit(bool share, KnightsCircuit& s) : Knights(share,s) {}
00305 virtual Space*
00306 copy(bool share) {
00307 return new KnightsCircuit(share,*this);
00308 }
00309 };
00310
00314 int
00315 main(int argc, char* argv[]) {
00316 SizeOptions opt("Knights");
00317 opt.iterations(100);
00318 opt.size(8);
00319 opt.propagation(Knights::PROP_CIRCUIT);
00320 opt.propagation(Knights::PROP_REIFIED, "reified");
00321 opt.propagation(Knights::PROP_CIRCUIT, "circuit");
00322 opt.branching(Knights::BRANCH_NAIVE);
00323 opt.branching(Knights::BRANCH_NAIVE, "reified");
00324 opt.branching(Knights::BRANCH_WARNSDORFF, "warnsdorff");
00325 opt.parse(argc,argv);
00326 if (opt.propagation() == Knights::PROP_REIFIED) {
00327 Script::run<KnightsReified,DFS,SizeOptions>(opt);
00328 } else {
00329 Script::run<KnightsCircuit,DFS,SizeOptions>(opt);
00330 }
00331 return 0;
00332 }
00333
00334
00335