main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Mar 13 2014 04:39:27 for Gecode by
doxygen
1.8.1.2
examples
dominating-queens.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Christian Schulte <schulte@gecode.org>
5
*
6
* Copyright:
7
* Christian Schulte, 2011
8
*
9
* Last modified:
10
* $Date: 2011-08-18 06:25:49 +1000 (Thu, 18 Aug 2011) $ by $Author: schulte $
11
* $Revision: 12308 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
#include <
gecode/driver.hh
>
39
#include <
gecode/int.hh
>
40
#include <
gecode/minimodel.hh
>
41
42
using namespace
Gecode;
43
57
class
DominatingQueens
:
public
MinimizeScript
{
58
protected
:
60
const
int
n
;
62
IntVarArray
b
;
64
IntVar
q
;
66
int
xy
(
int
x,
int
y)
const
{
67
return
y*n + x;
68
}
70
int
x
(
int
xy)
const
{
71
return
xy % n;
72
}
74
int
y
(
int
xy)
const
{
75
return
xy / n;
76
}
78
IntSet
attacked
(
int
xy) {
79
IntArgs
a
;
80
for
(
int
i
=0;
i
<n;
i
++)
81
for
(
int
j=0; j<n; j++)
82
if
((
i
== x(xy)) ||
// Same row
83
(j == y(xy)) ||
// Same column
84
(
abs
(
i
-x(xy)) ==
abs
(j-y(xy))))
// Same diagonal
85
a <<
DominatingQueens::xy
(
i
,j);
86
return
IntSet
(a);
87
}
88
public
:
90
DominatingQueens
(
const
SizeOptions
&
opt
)
91
: n(opt.
size
()),
b
(*this,n*n,0,n*n-1), q(*this,1,n) {
92
93
// Constrain field to the fields that can attack a field
94
for
(
int
i
=0;
i
<n*n;
i
++)
95
dom
(*
this
,
b
[
i
], attacked(i));
96
97
// At most q queens can be placed
98
nvalues
(*
this
,
b
,
IRT_LQ
, q);
99
100
/*
101
* According to: P. R. J. Östergard and W. D. Weakley, Values
102
* of Domination Numbers of the Queen's Graph, Electronic Journal
103
* of Combinatorics, 8:1-19, 2001, for n <= 120, the minimal number
104
* of queens is either ceil(n/2) or ceil(n/2 + 1).
105
*/
106
if
(n <= 120)
107
dom
(*
this
, q, (n+1)/2, (n+1)/2 + 1);
108
109
branch
(*
this
,
b
,
INT_VAR_SIZE_MIN
,
INT_VAL_MIN
);
110
// Try the easier solution first
111
branch
(*
this
, q,
INT_VAL_MAX
);
112
}
113
115
virtual
IntVar
cost
(
void
)
const
{
116
return
q;
117
}
118
120
DominatingQueens
(
bool
share,
DominatingQueens
& s)
121
:
MinimizeScript
(share,s), n(s.n) {
122
b
.
update
(*
this
, share, s.
b
);
123
q.update(*
this
, share, s.
q
);
124
}
125
127
virtual
Space
*
128
copy
(
bool
share) {
129
return
new
DominatingQueens
(share,*
this
);
130
}
131
133
virtual
void
134
print
(std::ostream& os)
const
{
135
os <<
"\tNumber of Queens: "
<< q << std::endl;
136
os <<
"\tBoard: "
<<
b
<< std::endl;
137
if
(
b
.assigned()) {
138
// Print a nice board
139
bool
* placed =
new
bool
[n*n];
140
for
(
int
i
=0;
i
<n*n;
i
++)
141
placed[
i
] =
false
;
142
for
(
int
i
=0;
i
<n*n;
i
++)
143
placed[
b
[
i
].val()] =
true
;
144
for
(
int
j=0; j<n; j++) {
145
std::cout <<
"\t\t"
;
146
for
(
int
i
=0;
i
<n;
i
++)
147
std::cout << (placed[xy(
i
,j)] ?
'Q'
:
'.'
) <<
' '
;
148
std::cout << std::endl;
149
}
150
delete
[] placed;
151
}
152
os << std::endl;
153
}
154
};
155
159
int
160
main
(
int
argc,
char
* argv[]) {
161
SizeOptions
opt
(
"DominatingQueens"
);
162
opt.
size
(7);
163
opt.
solutions
(0);
164
opt.
parse
(argc,argv);
165
MinimizeScript::run<DominatingQueens,BAB,SizeOptions>(
opt
);
166
return
0;
167
}
168
169
// STATISTICS: example-any
170