dominating-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
00057 class DominatingQueens : public IntMinimizeScript {
00058 protected:
00060 const int n;
00062 IntVarArray b;
00064 IntVar q;
00066 int xy(int x, int y) const {
00067 return y*n + x;
00068 }
00070 int x(int xy) const {
00071 return xy % n;
00072 }
00074 int y(int xy) const {
00075 return xy / n;
00076 }
00078 IntSet attacked(int xy) {
00079 IntArgs a;
00080 for (int i=0; i<n; i++)
00081 for (int j=0; j<n; j++)
00082 if ((i == x(xy)) ||
00083 (j == y(xy)) ||
00084 (abs(i-x(xy)) == abs(j-y(xy))))
00085 a << DominatingQueens::xy(i,j);
00086 return IntSet(a);
00087 }
00088 public:
00090 DominatingQueens(const SizeOptions& opt)
00091 : IntMinimizeScript(opt),
00092 n(opt.size()), b(*this,n*n,0,n*n-1), q(*this,1,n) {
00093
00094
00095 for (int i=0; i<n*n; i++)
00096 dom(*this, b[i], attacked(i));
00097
00098
00099 nvalues(*this, b, IRT_LQ, q);
00100
00101
00102
00103
00104
00105
00106
00107 if (n <= 120)
00108 dom(*this, q, (n+1)/2, (n+1)/2 + 1);
00109
00110 branch(*this, b, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
00111
00112 branch(*this, q, INT_VAL_MAX());
00113 }
00114
00116 virtual IntVar cost(void) const {
00117 return q;
00118 }
00119
00121 DominatingQueens(bool share, DominatingQueens& s)
00122 : IntMinimizeScript(share,s), n(s.n) {
00123 b.update(*this, share, s.b);
00124 q.update(*this, share, s.q);
00125 }
00126
00128 virtual Space*
00129 copy(bool share) {
00130 return new DominatingQueens(share,*this);
00131 }
00132
00134 virtual void
00135 print(std::ostream& os) const {
00136 os << "\tNumber of Queens: " << q << std::endl;
00137 os << "\tBoard: " << b << std::endl;
00138 if (b.assigned()) {
00139
00140 bool* placed = new bool[n*n];
00141 for (int i=0; i<n*n; i++)
00142 placed[i] = false;
00143 for (int i=0; i<n*n; i++)
00144 placed[b[i].val()] = true;
00145 for (int j=0; j<n; j++) {
00146 std::cout << "\t\t";
00147 for (int i=0; i<n; i++)
00148 std::cout << (placed[xy(i,j)] ? 'Q' : '.') << ' ';
00149 std::cout << std::endl;
00150 }
00151 delete [] placed;
00152 }
00153 os << std::endl;
00154 }
00155 };
00156
00160 int
00161 main(int argc, char* argv[]) {
00162 SizeOptions opt("DominatingQueens");
00163 opt.size(7);
00164 opt.solutions(0);
00165 opt.parse(argc,argv);
00166 IntMinimizeScript::run<DominatingQueens,BAB,SizeOptions>(opt);
00167 return 0;
00168 }
00169
00170
00171