The actual problem
| 84 | public: |
| 85 | /// The actual problem |
| 86 | DominatingQueens(const SizeOptions& opt) |
| 87 | : IntMinimizeScript(opt), |
| 88 | n(opt.size()), b(*this,n*n,0,n*n-1), q(*this,1,n) { |
| 89 | |
| 90 | // Constrain field to the fields that can attack a field |
| 91 | for (int i=0; i<n*n; i++) |
| 92 | dom(*this, b[i], attacked(i)); |
| 93 | |
| 94 | // At most q queens can be placed |
| 95 | nvalues(*this, b, IRT_LQ, q); |
| 96 | |
| 97 | /* |
| 98 | * According to: P. R. J. Östergard and W. D. Weakley, Values |
| 99 | * of Domination Numbers of the Queen's Graph, Electronic Journal |
| 100 | * of Combinatorics, 8:1-19, 2001, for n <= 120, the minimal number |
| 101 | * of queens is either ceil(n/2) or ceil(n/2 + 1). |
| 102 | */ |
| 103 | if (n <= 120) |
| 104 | dom(*this, q, (n+1)/2, (n+1)/2 + 1); |
| 105 | |
| 106 | branch(*this, b, INT_VAR_SIZE_MIN(), INT_VAL_MIN()); |
| 107 | // Try the easier solution first |
| 108 | branch(*this, q, INT_VAL_MAX()); |
| 109 | } |
| 110 | |
| 111 | /// Return cost |
| 112 | virtual IntVar cost(void) const { |
nothing calls this directly
no test coverage detected