main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 31 2012 16:20:40 for Gecode by
doxygen
1.8.1.2
examples
word-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
* Håkan Kjellerstrand <hakank@bonetmail.com>
5
* Mikael Lagerkvist <lagerkvist@gecode.org>
6
* Christian Schulte <schulte@gecode.org>
7
*
8
* Copyright:
9
* Håkan Kjellerstrand, 2009
10
* Mikael Lagerkvist, 2009
11
* Christian Schulte, 2009
12
*
13
* Last modified:
14
* $Date: 2010-10-07 20:52:01 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
15
* $Revision: 11473 $
16
*
17
* This file is part of Gecode, the generic constraint
18
* development environment:
19
* http://www.gecode.org
20
*
21
* Permission is hereby granted, free of charge, to any person obtaining
22
* a copy of this software and associated documentation files (the
23
* "Software"), to deal in the Software without restriction, including
24
* without limitation the rights to use, copy, modify, merge, publish,
25
* distribute, sublicense, and/or sell copies of the Software, and to
26
* permit persons to whom the Software is furnished to do so, subject to
27
* the following conditions:
28
*
29
* The above copyright notice and this permission notice shall be
30
* included in all copies or substantial portions of the Software.
31
*
32
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39
*
40
*/
41
42
#include <
gecode/driver.hh
>
43
44
#include <
gecode/int.hh
>
45
#include <
gecode/minimodel.hh
>
46
47
#include "
examples/scowl.hpp
"
48
49
using namespace
Gecode;
50
63
class
WordSquare
:
public
Script
{
64
protected
:
66
const
int
w_l
;
68
IntVarArray
letters
;
69
public
:
71
enum
{
72
BRANCH_WORDS
,
73
BRANCH_LETTERS
,
74
};
76
WordSquare
(
const
SizeOptions
&
opt
)
77
: w_l(opt.
size
()), letters(*this, w_l*w_l) {
78
79
// Initialize letters
80
Matrix<IntVarArray>
ml(letters, w_l, w_l);
81
for
(
int
i
=0;
i
<w_l;
i
++)
82
for
(
int
j=
i
; j<w_l; j++)
83
ml(
i
,j) = ml(j,
i
) =
IntVar
(*
this
,
'a'
,
'z'
);
84
85
// Number of words with that length
86
const
int
n_w =
dict
.
words
(w_l);
87
88
// Initialize word array
89
IntVarArgs
words(*
this
, w_l, 0, n_w-1);
90
91
// All words must be different
92
distinct
(*
this
, words);
93
94
// Link words with letters
95
for
(
int
i
=0;
i
<w_l;
i
++) {
96
// Map each word to i-th letter in that word
97
IntSharedArray
w2l(n_w);
98
for
(
int
n=n_w; n--; )
99
w2l[n]=
dict
.
word
(w_l,n)[
i
];
100
for
(
int
j=0; j<w_l; j++)
101
element
(*
this
, w2l, words[j], ml(
i
,j));
102
}
103
104
// Symmetry breaking: the last word must be later in the wordlist
105
rel
(*
this
, words[0],
IRT_LE
, words[w_l-1]);
106
107
switch
(opt.
branching
()) {
108
case
BRANCH_WORDS:
109
// Branch by assigning words
110
branch
(*
this
, words,
INT_VAR_SIZE_MIN
,
INT_VAL_SPLIT_MIN
);
111
break
;
112
case
BRANCH_LETTERS:
113
// Branch by assigning letters
114
branch
(*
this
, letters,
INT_VAR_SIZE_AFC_MIN
,
INT_VAL_MIN
);
115
break
;
116
}
117
}
119
WordSquare
(
bool
share,
WordSquare
& s)
120
:
Script
(share,s), w_l(s.w_l) {
121
letters.update(*
this
, share, s.
letters
);
122
}
124
virtual
Space
*
125
copy
(
bool
share) {
126
return
new
WordSquare
(share,*
this
);
127
}
129
virtual
void
130
print
(std::ostream& os)
const
{
131
Matrix<IntVarArray>
ml(letters, w_l, w_l);
132
for
(
int
i
=0;
i
<w_l;
i
++) {
133
os <<
"\t\t"
;
134
for
(
int
j=0; j<w_l; j++)
135
if
(ml(
i
,j).
assigned
()) {
136
os << static_cast<char>(ml(
i
,j).val());
137
}
else
{
138
os <<
"."
;
139
}
140
os << std::endl;
141
}
142
os << std::endl;
143
}
144
};
145
146
150
int
151
main
(
int
argc,
char
* argv[]) {
152
FileSizeOptions
opt
(
"WordSquare"
);
153
opt
.size(6);
154
opt
.
branching
(
WordSquare::BRANCH_LETTERS
);
155
opt
.
branching
(
WordSquare::BRANCH_WORDS
,
"words"
);
156
opt
.
branching
(
WordSquare::BRANCH_LETTERS
,
"letters"
);
157
opt
.
parse
(argc,argv);
158
dict
.
init
(
opt
.file());
159
if
(
opt
.size() >
static_cast<
unsigned
int
>
(
dict
.
len
())) {
160
std::cerr <<
"Error: size must be between 0 and "
161
<<
dict
.
len
() << std::endl;
162
return
1;
163
}
164
Script::run<WordSquare,DFS,SizeOptions>(
opt
);
165
return
0;
166
}
167
168
// STATISTICS: example-any