queens.cc
Go to the documentation of this file.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 #include "examples/support.hh"
00039 #include "gecode/minimodel.hh"
00040
00050 class Queens : public Example {
00051 protected:
00053 IntVarArray q;
00054 public:
00056 enum {
00057 PROP_BINARY,
00058 PROP_MIXED,
00059 PROP_DISTINCT
00060 };
00062 Queens(const SizeOptions& opt)
00063 : q(this,opt.size(),0,opt.size()-1) {
00064 const int n = q.size();
00065 switch (opt.propagation()) {
00066 case PROP_BINARY:
00067 for (int i = 0; i<n; i++)
00068 for (int j = i+1; j<n; j++) {
00069 post(this, q[i] != q[j]);
00070 post(this, q[i]+i != q[j]+j);
00071 post(this, q[i]-i != q[j]-j);
00072 }
00073 break;
00074 case PROP_MIXED:
00075 for (int i = 0; i<n; i++)
00076 for (int j = i+1; j<n; j++) {
00077 post(this, q[i]+i != q[j]+j);
00078 post(this, q[i]-i != q[j]-j);
00079 }
00080 distinct(this, q, opt.icl());
00081 break;
00082 case PROP_DISTINCT:
00083 {
00084 IntArgs c(n);
00085 for (int i = n; i--; ) c[i] = i;
00086 distinct(this, c, q, opt.icl());
00087 for (int i = n; i--; ) c[i] = -i;
00088 distinct(this, c, q, opt.icl());
00089 }
00090 distinct(this, q, opt.icl());
00091 break;
00092 }
00093 branch(this, q, INT_VAR_SIZE_MIN, INT_VAL_MIN);
00094 }
00095
00097 Queens(bool share, Queens& s) : Example(share,s) {
00098 q.update(this, share, s.q);
00099 }
00100
00102 virtual Space*
00103 copy(bool share) {
00104 return new Queens(share,*this);
00105 }
00106
00108 virtual void
00109 print(std::ostream& os) {
00110 os << "\t";
00111 for (int i = 0; i < q.size(); i++) {
00112 os << q[i] << ", ";
00113 if ((i+1) % 10 == 0)
00114 os << std::endl << "\t";
00115 }
00116 os << std::endl;
00117 }
00118
00120 virtual void
00121 getVars(Gecode::Reflection::VarMap& vm, bool registerOnly) {
00122 vm.putArray(this,q,"q", registerOnly);
00123 }
00124 };
00125
00129 int
00130 main(int argc, char* argv[]) {
00131 SizeOptions opt("Queens");
00132 opt.iterations(500);
00133 opt.size(100);
00134 opt.propagation(Queens::PROP_DISTINCT);
00135 opt.propagation(Queens::PROP_BINARY, "binary",
00136 "only binary disequality constraints");
00137 opt.propagation(Queens::PROP_MIXED, "mixed",
00138 "single distinct and binary disequality constraints");
00139 opt.propagation(Queens::PROP_DISTINCT, "distinct",
00140 "three distinct constraints");
00141 opt.parse(argc,argv);
00142 Example::run<Queens,DFS,SizeOptions>(opt);
00143 return 0;
00144 }
00145
00146
00147