main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 14 2013 20:59:22 for Gecode by
doxygen
1.8.3.1
examples
magic-square.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, 2001
8
*
9
* Last modified:
10
* $Date: 2010-10-07 20:52:01 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
11
* $Revision: 11473 $
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
54
class
MagicSquare
:
public
Script
{
55
private
:
57
const
int
n;
59
IntVarArray
x;
60
61
public
:
63
MagicSquare
(
const
SizeOptions
&
opt
)
64
: n(opt.
size
()), x(*this,n*n,1,n*n) {
65
// Number of fields on square
66
const
int
nn = n*n;
67
68
// Sum of all a row, column, or diagonal
69
const
int
s = nn*(nn+1) / (2*n);
70
71
// Matrix-wrapper for the square
72
Matrix<IntVarArray>
m
(x, n, n);
73
74
for
(
int
i
= n;
i
--; ) {
75
linear
(*
this
, m.
row
(
i
),
IRT_EQ
, s, opt.
icl
());
76
linear
(*
this
, m.
col
(
i
),
IRT_EQ
, s, opt.
icl
());
77
}
78
// Both diagonals must have sum s
79
{
80
IntVarArgs
d1y(n);
81
IntVarArgs
d2y(n);
82
for
(
int
i
= n;
i
--; ) {
83
d1y[
i
] =
m
(
i
,
i
);
84
d2y[
i
] =
m
(n-
i
-1,
i
);
85
}
86
linear
(*
this
, d1y,
IRT_EQ
, s, opt.
icl
());
87
linear
(*
this
, d2y,
IRT_EQ
, s, opt.
icl
());
88
}
89
90
// All fields must be distinct
91
distinct
(*
this
, x, opt.
icl
());
92
93
// Break some (few) symmetries
94
rel
(*
this
,
m
(0,0),
IRT_GR
,
m
(0,n-1));
95
rel
(*
this
,
m
(0,0),
IRT_GR
,
m
(n-1,0));
96
97
branch
(*
this
, x,
INT_VAR_SIZE_MIN
,
INT_VAL_SPLIT_MIN
);
98
}
99
101
MagicSquare
(
bool
share,
MagicSquare
& s) :
Script
(share,s), n(s.n) {
102
x.update(*
this
, share, s.x);
103
}
104
106
virtual
Space
*
107
copy
(
bool
share) {
108
return
new
MagicSquare
(share,*
this
);
109
}
111
virtual
void
112
print
(std::ostream& os)
const
{
113
// Matrix-wrapper for the square
114
Matrix<IntVarArray>
m
(x, n, n);
115
for
(
int
i
= 0;
i
<n;
i
++) {
116
os <<
"\t"
;
117
for
(
int
j = 0; j<n; j++) {
118
os.width(2);
119
os <<
m
(
i
,j) <<
" "
;
120
}
121
os << std::endl;
122
}
123
}
124
125
};
126
130
int
131
main
(
int
argc,
char
* argv[]) {
132
SizeOptions
opt
(
"MagicSquare"
);
133
opt.
iterations
(1);
134
opt.
size
(7);
135
opt.
parse
(argc,argv);
136
Script::run<MagicSquare,DFS,SizeOptions>(
opt
);
137
return
0;
138
}
139
140
// STATISTICS: example-any
141