this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Lagerkvist <lagerkvist@gecode.org>
5 *
6 * Copyright:
7 * Mikael Lagerkvist, 2006
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36
37#include <vector>
38#include <algorithm>
39#include <sstream>
40
41using namespace Gecode;
42
43namespace {
44
45 using std::vector;
46
47 /// Layout of the cards
48 vector<vector<int> > layout;
49 /// information for locating particular cards in the layout
50 vector<int> layer, pile;
51
52 /** \brief Generates\ref layout.
53 *
54 * This function generates the layeout and intializes \ref layer and
55 * \ref pile from it. The layout is randomly generated from the
56 * supplied seed.
57 */
58 void generate(int seed) {
59 // The layout consists of 17 piles of 3 cards each
60 layout = vector<vector<int> >(17, vector<int>(3));
61 // Deck without the Ace of Spades
62 vector<int> deck(51);
63 for (int i = 51; i--; ) deck[i] = i+1;
64 Support::RandomGenerator rnd(seed+1);
65 std::random_shuffle(deck.begin(), deck.end(), rnd);
66
67 // Place cards from deck
68 int pos = 0;
69 for (int i = 17; i--; )
70 for (int j = 3; j--; )
71 layout[i][j] = deck[pos++];
72
73 // Location-information for each card
74 layer = vector<int>(52);
75 pile = vector<int>(52);
76 for (int i = 17; i--; ) {
77 for (int j = 3; j--; ) {
78 layer[layout[i][j]] = j;
79 pile[ layout[i][j]] = i;
80 }
81 }
82 }
83}
84
85/**
86 * \brief %Example: Black hole patience
87 *
88 * This example solves instances of the black-hole patience game.
89 *
90 * The model of the problem is mostly taken from "Search in the
91 * Patience Game 'Black Hole'", by Ian P. Gent, Chris Jefferson, Tom
92 * Kelsey, Inês Lynce, Ian Miguel, Peter Nightingale, Barbara
93 * M. Smith, and S. Armagan Tarim.
94 *
95 * The conditional symmetry identified in the above paper can be
96 * eliminated (enabled by default).
97 *
98 * \ingroup Example
99 *
100 */
101class BlackHole : public Script {
102protected:
103 IntVarArray x, ///< Card at position
104 y; ///< Position of card
105
106 /// Return a string representing the card of value val
107 std::string
108 card(int val) const {
109 const char* suit = "SCHD";
110 std::ostringstream o;
111 o << std::setw(2) << (1 + (val%13)) << suit[val/13];
112 return o.str();
113 }
114
115public:
116 /// Symmetry variants
117 enum {
118 SYMMETRY_NONE, ///< No symmetry breaking
119 SYMMETRY_CONDITIONAL ///< Breaking conditional symmetries
120 };
121 /// Propagation of placement-rules
122 enum {
123 PROPAGATION_REIFIED, ///< Reified propagation
124 PROPAGATION_DFA, ///< Extensional propagation using automatons
125 PROPAGATION_TUPLE_SET ///< Extensional propagation using tables
126 };
127 /// Actual model
128 BlackHole(const SizeOptions& opt)
129 : Script(opt), x(*this, 52, 0,51), y(*this, 52, 0,51) {
130 // Black ace at bottom
131 rel(*this, x[0], IRT_EQ, 0);
132
133 // x is order and y is placement
134 channel(*this, x, y, opt.ipl());
135
136 // The placement rules: the absolute value of the difference
137 // between two consecutive cards is 1 or 12.
138 if (opt.propagation() == PROPAGATION_REIFIED) {
139 // Build table for accessing the rank of a card
140 IntArgs modtable(52);
141 for (int i = 0; i < 52; ++i) {
142 modtable[i] = i%13;
143 }
144 for (int i = 0; i < 51; ++i) {
145 IntVar x1(*this, 0, 12), x2(*this, 0, 12);
146 element(*this, modtable, x[i], x1);
147 element(*this, modtable, x[i+1], x2);
148 const int dr[2] = {1, 12};
149 IntVar diff(*this, IntSet(dr, 2));
150 rel(*this, abs(x1-x2) == diff, IPL_DOM);
151 }
152 } else if (opt.propagation() == PROPAGATION_DFA) {
153 // Build table for allowed tuples
154 REG expression;
155 for (int r = 13; r--; ) {
156 for (int s1 = 4; s1--; ) {
157 for (int s2 = 4; s2--; ) {
158 for (int i = -1; i <= 1; i+=2) {
159 REG r1 = REG(r+13*s1);
160 REG r2 = REG((r+i+52+13*s2)%52);
161 REG r = r1 + r2;
162 expression |= r;
163 }
164 }
165 }
166 }
167 DFA table(expression);
168
169 for (int i = 51; i--; )
170 extensional(*this, IntVarArgs({x[i],x[i+1]}), table);
171
172 } else { // opt.propagation() == PROPAGATION_TUPLE_SET)
173 // Build table for allowed tuples
174 TupleSet ts(2);
175 for (int r = 13; r--; )
176 for (int s1 = 4; s1--; )
177 for (int s2 = 4; s2--; )
178 for (int i = -1; i <= 1; i+=2)
179 ts.add({r+13*s1, (r+i+52+13*s2)%52});
180 ts.finalize();
181
182 for (int i = 51; i--; )
183 extensional(*this, IntVarArgs({x[i],x[i+1]}), ts);
184 }
185
186 // A card must be played before the one under it.
187 for (int i = 17; i--; )
188 for (int j = 2; j--; )
189 rel(*this, y[layout[i][j]] < y[layout[i][j+1]]);
190
191 // Compute and break the conditional symmetries that are dependent
192 // on the current layout.
193 // Two cards with the same rank but different suits are symmetric
194 // with respect to their placement in the black hole if changing
195 // their order does not affect any other card.
196 if (opt.symmetry() == SYMMETRY_CONDITIONAL) {
197 // For all ranks
198 for (int r = 13; r--; ) {
199 // For all pairs of suits
200 for (int s1 = 4; s1--; ) {
201 for (int s2 = s1; s2--; ) {
202 int c1 = 13*s1 + r,
203 c2 = 13*s2 + r;
204 // The ace of spades is already placed
205 if (c1 == 0 || c2 == 0) continue;
206 // Piles are handled by the rules of the game
207 if (pile[c1] == pile[c2]) continue;
208 // Fix the right order of the cards
209 int o1 = c1, o2 = c2;
210 if (pile[c1] > pile[c2] && layer[c2] >= layer[c1])
211 std::swap(o1, o2);
212 // cond is the condition for the symmetry
213 BoolVarArgs ba;
214 // Both cards played after the ones on top of them
215 for (int i = 0; i < layer[o1]; ++i)
216 ba << expr(*this, (y[layout[pile[o1]][i]] < y[o2]));
217 for (int i = 0; i < layer[o2]; ++i)
218 ba << expr(*this, (y[layout[pile[o2]][i]] < y[o1]));
219 // Both cards played before the ones under them
220 for (int i = layer[o1]+1; i < 3; ++i)
221 ba << expr(*this, (y[o2] < y[layout[pile[o1]][i]]));
222 for (int i = layer[o2]+1; i < 3; ++i)
223 ba << expr(*this, (y[o1] < y[layout[pile[o2]][i]]));
224 // Cond holds when all the above holds
225 BoolVar cond(*this, 0, 1);
226 rel(*this, BOT_AND, ba, cond);
227
228 // If cond is fulfilled, then we can order the cards
229 // cond -> (y[o1] < y[o2])
230 rel(*this, !cond || (y[o1] < y[o2]));
231 }
232 }
233 }
234 }
235
236 // Install custom brancher
237 branch(*this, x, INT_VAR_NONE(), INT_VAL(&val));
238 }
239 /// Value selection function for branching
240 static int val(const Space&, IntVar x, int) {
241 int v = -1;
242 int w = 4;
243 for (IntVarValues vals(x); vals(); ++vals)
244 if (layer[vals.val()] < w) {
245 v = vals.val();
246 if ((w = layer[vals.val()]) == 0)
247 break;
248 }
249 assert(v >= 1 && v < 52);
250 return v;
251 }
252 /// Print instance and solution
253 virtual void
254 print(std::ostream& os) const {
255 os << "Layout:" << std::endl;
256 for (int i = 0; i < 17; i++) {
257 for (int j = 0; j < 3; j++)
258 os << card(layout[i][j]) << " ";
259 if ((i+1) % 3 == 0)
260 os << std::endl;
261 else
262 os << " \t";
263 }
264 os << std::endl << std::endl;
265
266 os << "Solution:" << std::endl;
267 for (int i = 0; i < 52; ++i) {
268 if (x[i].assigned())
269 os << card(x[i].val()) << " ";
270 else
271 os << " ";
272 if ((i + 1) % 13 == 0)
273 os << std::endl;
274 }
275 os << std::endl;
276 os << std::endl;
277 }
278
279 /// Constructor for cloning \a s
280 BlackHole(BlackHole& s) : Script(s) {
281 x.update(*this, s.x);
282 y.update(*this, s.y);
283 }
284 /// Copy during cloning
285 virtual Space*
286 copy(void) {
287 return new BlackHole(*this);
288 }
289};
290
291/** \brief Main-function
292 * \relates BlackHole
293 */
294int
295main(int argc, char* argv[]) {
296 SizeOptions opt("Black Hole patience");
297 opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL);
298 opt.symmetry(BlackHole::SYMMETRY_NONE,"none",
299 "no symmetry breaking");
300 opt.symmetry(BlackHole::SYMMETRY_CONDITIONAL,"conditional",
301 "break conditional symmetries");
302 opt.propagation(BlackHole::PROPAGATION_TUPLE_SET);
303 opt.propagation(BlackHole::PROPAGATION_REIFIED,
304 "reified", "use reified propagation");
305 opt.propagation(BlackHole::PROPAGATION_DFA,
306 "dfa", "use DFA-based extensional propagation");
307 opt.propagation(BlackHole::PROPAGATION_TUPLE_SET,
308 "tuple-set", "use TupleSet-based extensional propagation");
309 opt.ipl(IPL_DOM);
310 opt.parse(argc,argv);
311 // Generates the new board
312 generate(opt.size());
313 Script::run<BlackHole,DFS,SizeOptions>(opt);
314 return 0;
315}
316
317// STATISTICS: example-any