41 using namespace Gecode;
47 vector<vector<int> > layout;
49 vector<int> layer, pile;
57 void generate(
int seed) {
59 layout = vector<vector<int> >(17, vector<int>(3));
62 for (
int i = 51;
i--; ) deck[
i] =
i+1;
64 std::random_shuffle(deck.begin(), deck.end(), rnd);
68 for (
int i = 17;
i--; )
69 for (
int j = 3; j--; )
70 layout[
i][j] = deck[
pos++];
73 layer = vector<int>(52);
74 pile = vector<int>(52);
75 for (
int i = 17;
i--; ) {
76 for (
int j = 3; j--; ) {
77 layer[layout[
i][j]] = j;
78 pile[ layout[
i][j]] =
i;
108 const char* suit =
"SCHD";
109 std::ostringstream o;
110 o << std::setw(2) << (1 + (val%13)) << suit[val/13];
124 PROPAGATION_TUPLE_SET
128 :
Script(
opt),
x(*this, 52, 0,51),
y(*this, 52, 0,51) {
137 if (
opt.propagation() == PROPAGATION_REIFIED) {
140 for (
int i = 0;
i < 52; ++
i) {
143 for (
int i = 0;
i < 51; ++
i) {
144 IntVar x1(*
this, 0, 12), x2(*
this, 0, 12);
147 const int dr[2] = {1, 12};
151 }
else if (
opt.propagation() == PROPAGATION_DFA) {
154 for (
int r = 13;
r--; ) {
155 for (
int s1 = 4; s1--; ) {
156 for (
int s2 = 4; s2--; ) {
157 for (
int i = -1;
i <= 1;
i+=2) {
166 DFA table(expression);
168 for (
int i = 51;
i--; )
174 for (
int r = 13;
r--; )
175 for (
int s1 = 4; s1--; )
176 for (
int s2 = 4; s2--; )
177 for (
int i = -1;
i <= 1;
i+=2)
178 ts.
add({r+13*s1, (r+i+52+13*s2)%52});
181 for (
int i = 51;
i--; )
186 for (
int i = 17;
i--; )
187 for (
int j = 2; j--; )
188 rel(*
this,
y[layout[
i][j]] <
y[layout[
i][j+1]]);
195 if (
opt.symmetry() == SYMMETRY_CONDITIONAL) {
197 for (
int r = 13;
r--; ) {
199 for (
int s1 = 4; s1--; ) {
200 for (
int s2 = s1; s2--; ) {
204 if (c1 == 0 || c2 == 0)
continue;
206 if (pile[c1] == pile[c2])
continue;
208 int o1 = c1, o2 = c2;
209 if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
214 for (
int i = 0;
i < layer[o1]; ++
i)
215 ba <<
expr(*
this, (
y[layout[pile[o1]][
i]] <
y[o2]));
216 for (
int i = 0;
i < layer[o2]; ++
i)
217 ba <<
expr(*
this, (
y[layout[pile[o2]][
i]] <
y[o1]));
219 for (
int i = layer[o1]+1;
i < 3; ++
i)
220 ba <<
expr(*
this, (
y[o2] <
y[layout[pile[o1]][
i]]));
221 for (
int i = layer[o2]+1;
i < 3; ++
i)
222 ba <<
expr(*
this, (
y[o1] <
y[layout[pile[o2]][
i]]));
229 rel(*
this, !cond || (
y[o1] <
y[o2]));
243 if (layer[vals.val()] < w) {
245 if ((w = layer[vals.val()]) == 0)
248 assert(
v >= 1 &&
v < 52);
254 os <<
"Layout:" << std::endl;
255 for (
int i = 0;
i < 17;
i++) {
256 for (
int j = 0; j < 3; j++)
257 os <<
card(layout[
i][j]) <<
" ";
263 os << std::endl << std::endl;
265 os <<
"Solution:" << std::endl;
266 for (
int i = 0;
i < 52; ++
i) {
268 os <<
card(
x[
i].val()) <<
" ";
271 if ((
i + 1) % 13 == 0)
280 x.update(*
this, s.
x);
298 "no symmetry breaking");
300 "break conditional symmetries");
303 "reified",
"use reified propagation");
305 "dfa",
"use DFA-based extensional propagation");
307 "tuple-set",
"use TupleSet-based extensional propagation");
311 generate(
opt.size());
312 Script::run<BlackHole,DFS,SizeOptions>(
opt);
BoolVar expr(Home home, const BoolExpr &e, const IntPropLevels &ipls)
Post Boolean expression and return its value.
Node * x
Pointer to corresponding Boolean expression node.
Example: Black hole patience
int main(int argc, char *argv[])
Main-function.
BlackHole(BlackHole &s)
Constructor for cloning s.
IntVarArray x
Card at position.
@ SYMMETRY_CONDITIONAL
Breaking conditional symmetries.
@ SYMMETRY_NONE
No symmetry breaking.
std::string card(int val) const
Return a string representing the card of value val.
BlackHole(const SizeOptions &opt)
Actual model.
virtual Space * copy(void)
Copy during cloning.
static int val(const Space &, IntVar x, int)
Value selection function for branching.
IntVarArray y
Position of card.
@ PROPAGATION_REIFIED
Reified propagation.
@ PROPAGATION_DFA
Extensional propagation using automatons.
@ PROPAGATION_TUPLE_SET
Extensional propagation using tables.
virtual void print(std::ostream &os) const
Print instance and solution.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Passing Boolean variables.
Boolean integer variables.
Deterministic finite automaton (DFA)
Parametric base-class for scripts.
Passing integer arguments.
Passing integer variables.
Value iterator for integer variables.
void propagation(int v)
Set default propagation value.
void symmetry(int v)
Set default symmetry value.
void ipl(IntPropLevel i)
Set default integer propagation level.
Regular expressions over integer values.
Options for scripts with additional size parameter
Template for linear congruential generators.
Class represeting a set of tuples.
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
void finalize(void)
Finalize tuple set.
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
void element(Home home, IntSharedArray c, IntVar x0, IntVar x1, IntPropLevel)
Post domain consistent propagator for .
Post propagator for SetVar SetOpType SetVar y
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
IntValBranch INT_VAL(IntBranchVal v, IntBranchCommit c)
Select value as defined by the value function v and commit function c Uses a commit function as defau...
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
bool pos(const View &x)
Test whether x is postive.
bool assigned(View x, int v)
Whether x is assigned to value v.
const unsigned int card
Maximum cardinality of an integer set.
Gecode::IntArgs i({1, 2, 3, 4})