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