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