this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
5 *
6 * Copyright:
7 * Vincent Barichard, 2013
8 *
9 * Last modified:
10 * $Date$ by $Author$
11 * $Revision$
12 *
13 * This file is part of Quacode:
14 * http://quacode.barichard.com
15 *
16 * Permission is hereby granted, free of charge, to any person obtaining
17 * a copy of this software and associated documentation files (the
18 * "Software"), to deal in the Software without restriction, including
19 * without limitation the rights to use, copy, modify, merge, publish,
20 * distribute, sublicense, and/or sell copies of the Software, and to
21 * permit persons to whom the Software is furnished to do so, subject to
22 * the following conditions:
23 *
24 * The above copyright notice and this permission notice shall be
25 * included in all copies or substantial portions of the Software.
26 *
27 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
28 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
29 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
30 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
31 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
32 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
33 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
34 *
35 */
36
37#include <iostream>
38#include <vector>
39#include <string>
40
41#include <quacode/qspaceinfo.hh>
42#include <gecode/minimodel.hh>
43#include <gecode/driver.hh>
44
45
46using namespace Gecode;
47
48#ifdef GECODE_HAS_GIST
49namespace Gecode { namespace Driver {
50 /// Specialization for QDFS
51 template<typename S>
52 class GistEngine<QDFS<S> > {
53 public:
54 static void explore(S* root, const Gist::Options& opt) {
55 (void) Gist::explore(root, false, opt);
56 }
57 };
58}}
59#endif
60
61/**
62 * \brief Options taking one additional parameter
63 */
64class ConnectFourOptions : public Options {
65protected:
66 /// Print strategy or not
67 Gecode::Driver::BoolOption _printStrategy;
68 /// Model name
69 Gecode::Driver::StringOption _QCSPmodel;
70 /// Heuristic in branching
71 Gecode::Driver::BoolOption _heuristic;
72 /// File name of recorded moves
73 Gecode::Driver::StringValueOption _file;
74 /// Optional number of rows
75 Gecode::Driver::UnsignedIntOption _row;
76 /// Optional number of cols
77 Gecode::Driver::UnsignedIntOption _col;
78public:
79 /// Initialize options for example with name \a s
80 ConnectFourOptions(const char* s)
81 : Options(s),
82 _printStrategy("-printStrategy","Print strategy",false),
83 _QCSPmodel("-QCSPmodel","Name of the model used for modeling problem",3),
84 _heuristic("-heuristic","Use heuristic when branching (only for model + and ++)",true),
85 _file("-file","File name of recorded moves"),
86 _row("-row","Number of rows (minimum 4)",6),
87 _col("-col","Number of cols (minimum 4)",7) {
88 _QCSPmodel.add(1,"AllState","Model with all states as defined by P. Nightingale. Without Pure Value and heuristic setup.");
89 _QCSPmodel.add(2,"AllState+","Model with all states as defined by P. Nightingale. With cut.");
90 _QCSPmodel.add(3,"AllState++","Model with all states as defined by P. Nightingale. With cut and additional constraints.");
91 add(_printStrategy);
92 add(_QCSPmodel);
93 add(_heuristic);
94 add(_file);
95 add(_row);
96 add(_col);
97 }
98 /// Return true if the strategy must be printed
99 bool printStrategy(void) const {
100 return _printStrategy.value();
101 }
102 /// Return model name
103 int QCSPmodel(void) const {
104 return _QCSPmodel.value();
105 }
106 /// Return if heuristic must be used
107 bool heuristic(void) const {
108 return _heuristic.value();
109 }
110 /// Return file name
111 const char *file(void) const {
112 return _file.value();
113 }
114 /// Return number of rows
115 int row(void) const {
116 return _row.value();
117 }
118 /// Return number of cols
119 int col(void) const {
120 return _col.value();
121 }
122};
123
124/// Succeed the space
125static void gf_success(Space& home) {
126 Space::Branchers b(home);
127 while (b()) {
128 BrancherHandle bh(b.brancher());
129 ++b;
130 bh.kill(home);
131 }
132}
133
134/// Dummy function
135static void gf_dummy(Space& ) { }
136
137/// Adding cut
138static void cut(Space& home, const BoolExpr& expr) {
139 BoolVar o(home,0,1);
140 rel(home, o == expr);
141 when(home, o, &gf_success, &gf_dummy);
142}
143
144template <int N>
145struct c4Heuristic {
146 static int value(const Space& _home, IntVar x, int);
147};
148
149// Template loop to avoid to write a hundred lines of code
150template <int N>
151struct FOR {
152 static void go(IntBranchVal t[]) {
153 t[N] = &c4Heuristic<N>::value;
154 FOR<N-1>::go(t);
155 }
156};
157template <>
158struct FOR<0> {
159 static void go(IntBranchVal t[]) {
160 t[0] = &c4Heuristic<0>::value;
161 }
162};
163
164class ConnectFourAllState : public Script, public QSpaceInfo {
165 static const int Red = 0;
166 static const int Black = 1;
167 static const int Nil = 2;
168
169 IntVarArray M; // Move variables (the column played)
170 IntVarArray U; // Additional move variables (the column played) only usefull for simple model
171 IntVarArray board; // State of board
172 IntVarArray h; // Number of token in col c
173 BoolVarArray mh; // Representing if the move i was made in column c (move-here)
174 IntVarArray gameWinner; // Representing winner 0 = player red wins, 1 = player black wins
175 BoolVarArray line; // Indicating the presence of line in each row, column or diagonal (numbered)
176 BoolVarArray lineMove; // Indicating the presence of line for a move
177 BoolVarArray pos; // Indicating the presence of empty slots
178 BoolVarArray moveDone; // Is true if the move k has been done
179
180 int row;
181 int col;
182 int kOffset;
183
184 const ConnectFourOptions& opt;
185
186public:
187 ConnectFourAllState(const ConnectFourOptions& _opt) : Script(_opt), QSpaceInfo(), opt(_opt)
188 {
189 std::cout << "Loading problem" << std::endl;
190 if (!opt.printStrategy()) strategyMethod(0); // disable build and print strategy
191 using namespace Int;
192 // Define constants
193 row = opt.row();
194 col = opt.col();
195 kOffset = 0;
196 int nbDecisionVar = row*col;
197
198 // Create array of heuristics, one for each brancher
199 assert(nbDecisionVar <= 100);
200 IntBranchVal heuristicArray[100];
201 FOR<100>::go(heuristicArray);
202
203 // Create board variables
204 M = IntVarArray(*this,nbDecisionVar,0,col-1);
205 if (opt.QCSPmodel() == 1) U = IntVarArray(*this,nbDecisionVar/2,0,col-1);
206 board = IntVarArray(*this, nbDecisionVar*row*col, 0, 2);
207 pos = BoolVarArray(*this, nbDecisionVar*row*col, 0, 1);
208 h = IntVarArray(*this, nbDecisionVar*col, 0, row);
209 mh = BoolVarArray(*this, nbDecisionVar*col, 0, 1);
210 lineMove = BoolVarArray(*this, nbDecisionVar, 0, 1);
211 gameWinner = IntVarArray(*this, nbDecisionVar, 0, 2);
212 moveDone = BoolVarArray(*this, nbDecisionVar, 0, 1);
213
214 // Test if a file was given in argument
215 // We will update kOffset according to the file number of moves
216 IntArgs rMoves;
217 if (opt.file()) {
218 std::ifstream f(opt.file());
219
220 if (!f)
221 throw Gecode::Exception("Connect four",
222 "Unable to open file");
223 int move;
224 while (f >> move) {
225 rMoves << move;
226 kOffset++;
227 }
228
229 f.close();
230 assert((kOffset%2) == 0);
231 }
232
233 // Defining the player variables
234 IntVarArgs m, uWm;
235 for (int k=0; k<nbDecisionVar; k++)
236 {
237 // Post brancher
238 if (k >= kOffset) {
239 if ((k%2) == 1) setForAll(*this, M[k]);
240 if (opt.QCSPmodel() == 1)
241 branch(*this, M[k], INT_VAR_NONE(), INT_VALUES_MIN());
242 else if (opt.heuristic())
243 branch(*this, M[k], INT_VAR_NONE(), INT_VAL(heuristicArray[k]));
244 else
245 branch(*this, M[k], INT_VAR_NONE(), INT_VAL_MIN());
246 }
247
248 if (opt.QCSPmodel() == 1) {
249 // Model from P. Nightingale without Pure Value and heuristic setup
250 if ((k%2) == 0) m << M[k];
251 else {
252 if (k >= kOffset) {
253 // With this simple model, we link some new existential variables to
254 // the universal one if the move is legal.
255 // As a result, we increase the number of branched variable and the search space
256 branch(*this, U[k/2], INT_VAR_NONE(), INT_VALUES_MIN());
257 }
258 m << U[k/2];
259 for (int i=0; i < col; i++)
260 rel(*this, ((gameWinner[k-1] == Nil) && (h[(k-1)*col+i] < row) && (M[k] == i)) >> (U[k/2] == i), IPL_DOM); // Forbid illegal move
261 }
262 } else {
263 // Model from P. Nightingale but we add cut and prune universal in order
264 // to achieve same work as Pure Value. To compare with Queso, disable the
265 // heurisitic has we do not have one here.
266 m << M[k];
267 }
268
269 // We build the array of unwatched variables
270 if (((k%2)==0) || (k<kOffset)) uWm << M[k];
271 else uWm << getUnWatched(M[k]);
272
273 // Some moves has been recorded, we play them here
274 if (rMoves.size() > k) rel(*this, uWm[k] == rMoves[k], IPL_DOM);
275
276 // Set the move-here variables
277 if (k==0)
278 for (int i=0; i < col; i++)
279 rel(*this, (m[0] == i) == (mh[0*col+i] && moveDone[0]), IPL_DOM);
280 else {
281 for (int i=0; i < col; i++) {
282 if (opt.QCSPmodel() <= 1) {
283 // Not exactly as the article, we have drop the part with !lineMove[k-1].
284 // We have to do this because it is not compatible with the constraints
285 // which force the last board to be full
286 // rel(*this, (!lineMove[k-1] && (h[(k-1)*col+i] < row) && (m[k] == i)) == mh[k*col+i], IPL_DOM);
287 rel(*this, ((h[(k-1)*col+i] < row) && (m[k] == i)) == mh[k*col+i], IPL_DOM);
288 } else { // opt.QCSPmodel() > 1
289 // rel(*this, (!lineMove[k-1] && (h[(k-1)*col+i] < row) && (m[k] == i)) == (mh[k*col+i] && moveDone[k]), IPL_DOM);
290 rel(*this, ((h[(k-1)*col+i] < row) && (m[k] == i)) == (mh[k*col+i] && moveDone[k]), IPL_DOM);
291 // Prune for universal
292 rel(*this, (h[(k-1)*col+i] == row) >> (uWm[k] != i), IPL_DOM); // Prune illegal move from universal
293
294 // Add cut
295 if ((k%2) == 1) cut(*this, (gameWinner[k-1] == Red) && moveDone[k-1]);
296 }
297 }
298 }
299 }
300
301 // Fill the holes
302 for (int k=0, offSet = 0; k<nbDecisionVar; k++, offSet += row*col)
303 for (int i=0; i < col; i++)
304 for (int j=0; j < row-1; j++) {
305 BoolExpr be;
306 be = expr(*this, board[offSet+i*row+j] != (((k%2)==0)?Black:Red));
307 for (int jj=j+1; jj < row; jj++)
308 be = expr(*this, be && (board[offSet+i*row+jj] == Nil));
309 rel(*this, pos[offSet+i*row+j] == be, IPL_DOM);
310 }
311
312 for (int k=0, offSet = 0; k<nbDecisionVar; k++, offSet += row*col)
313 if (k == 0) {
314 for (int i=0; i < col; i++) {
315 rel(*this, pos[offSet+i*row], IPL_DOM);
316 rel(*this, pos[offSet+i*row+row-1], IPL_DOM);
317 rel(*this, !mh[0*col+i] >> (board[offSet+i*row] == Nil), IPL_DOM);
318 rel(*this, mh[0*col+i] >> (board[offSet+i*row] == Red), IPL_DOM);
319 }
320 } else {
321 for (int i=0; i < col; i++) {
322 rel(*this, (h[(k-1)*col+i] == row) == !pos[offSet+i*row+row-1], IPL_DOM);
323 for (int j=0; j < row; j++) {
324 rel(*this, (h[(k-1)*col+i] == j) >> pos[offSet+i*row+j], IPL_DOM);
325 rel(*this, (!mh[k*col+i] && (h[(k-1)*col+i] == j)) >> (board[offSet+i*row+j] == Nil), IPL_DOM);
326 rel(*this, ( mh[k*col+i] && (h[(k-1)*col+i] == j)) >> (board[offSet+i*row+j] == (((k%2)==0)?Red:Black)), IPL_DOM);
327 }
328 }
329 }
330
331 // Map pieces from board at move i-1 to board at move k
332 for (int k=1, offSet = row*col; k<nbDecisionVar; k++, offSet += row*col)
333 for (int i=0; i < col; i++)
334 for (int j=0; j < row; j++) {
335 rel(*this, (board[(offSet-row*col)+i*row+j] == Black) >> (board[offSet+i*row+j] == Black), IPL_DOM);
336 rel(*this, (board[(offSet-row*col)+i*row+j] == Red) >> (board[offSet+i*row+j] == Red), IPL_DOM);
337 }
338
339 // Link height and board state
340 for (int k=0, offSet = 0; k<nbDecisionVar; k++, offSet += row*col)
341 for (int i=0; i < col; i++)
342 for (int j=0; j < row+1; j++)
343 if (j==0)
344 rel(*this, (board[offSet+i*row] == Nil) >> (h[k*col+i] == 0), IPL_DOM);
345 else if (j==row)
346 rel(*this, (board[offSet+i*row+j-1] != Nil) >> (h[k*col+i] == row), IPL_DOM);
347 else
348 rel(*this, ((board[offSet+i*row+j-1] != Nil) && (board[offSet+i*row+j] == Nil)) >> (h[k*col+i] == j), IPL_DOM);
349
350 // Detect lines
351 BoolVarArgs l;
352 // Detect winning blocks
353 for (int k=0, offSet = 0; k<nbDecisionVar; k++, offSet += row*col) {
354 BoolVarArgs lk;
355 for (int z=0; z<4; z++) { // Row(0) / Col(1) / Diag1(2) / Diag2(3)
356 for (int i=0; i < col; i++) {
357 for (int j=0; j < row; j++) {
358 bool post = false;
359 IntVarArgs x;
360 if (((z%4)==0) && (i+3) < col) { // Line in row
361 x << board[offSet+i*row+j] << board[offSet+(i+1)*row+j] << board[offSet+(i+2)*row+j] << board[offSet+(i+3)*row+j];
362 post = true;
363 }
364 if (((z%4)==1) && (j+3) < row) {// Line in column
365 x << board[offSet+i*row+j] << board[offSet+i*row+j+1] << board[offSet+i*row+j+2] << board[offSet+i*row+j+3];
366 post = true;
367 }
368 if (((z%4)==2) && ((i+3) < col) && ((j+3) < row)) { // Line in diag1
369 x << board[offSet+i*row+j] << board[offSet+(i+1)*row+j+1] << board[offSet+(i+2)*row+j+2] << board[offSet+(i+3)*row+j+3];
370 post = true;
371 }
372 if (((z%4)==3) && ((i-3) >= 0) && ((j+3) < row)) { // Line in diag2
373 x << board[offSet+i*row+j] << board[offSet+(i-1)*row+j+1] << board[offSet+(i-2)*row+j+2] << board[offSet+(i-3)*row+j+3];
374 post = true;
375 }
376 if (post) {
377 if ((k%2) == 0) {
378 BoolVar bRed(*this,0,1);
379 lk << bRed;
380 l << bRed;
381 if (k>0)
382 rel(*this,(lineMove[k-1] || (x[0] != Red) || (x[1] != Red) || (x[2] != Red) || (x[3] != Red)) == !bRed, IPL_DOM);
383 else
384 rel(*this,((x[0] != Red) || (x[1] != Red) || (x[2] != Red) || (x[3] != Red)) == !bRed, IPL_DOM);
385 } else {
386 BoolVar bBlack(*this,0,1);
387 lk << bBlack;
388 l << bBlack;
389 rel(*this,(lineMove[k-1] || (x[0] != Black) || (x[1] != Black) || (x[2] != Black) || (x[3] != Black)) == !bBlack, IPL_DOM);
390 }
391 }
392 }
393 }
394 }
395 if (k>0) lk << lineMove[k-1];
396 rel(*this, BOT_OR, lk, lineMove[k], IPL_DOM);
397 }
398 line = BoolVarArray(*this, l);
399
400 // Set GameState variables
401 rel(*this, gameWinner[0] == Nil, IPL_DOM);
402 for (int k=1; k < nbDecisionVar; k++) {
403 rel(*this, (gameWinner[k-1] == Black) >> (gameWinner[k] == Black), IPL_DOM);
404 rel(*this, (gameWinner[k-1] == Red) >> (gameWinner[k] == Red), IPL_DOM);
405 rel(*this, ((gameWinner[k-1] == Nil) && !lineMove[k]) >> (gameWinner[k] == Nil), IPL_DOM);
406 if ((k%2) == 0)
407 rel(*this, ((gameWinner[k-1] == Nil) && lineMove[k]) >> (gameWinner[k] == Red), IPL_DOM);
408 else
409 rel(*this, ((gameWinner[k-1] == Nil) && lineMove[k]) >> (gameWinner[k] == Black), IPL_DOM);
410
411 if (opt.QCSPmodel() == 3) {
412 // If not winner before, only current player have a chance to win
413 // the game at this move -- NOT IN INITIAL MODEL
414 if ((k%2) == 0)
415 rel(*this, (gameWinner[k-1] == Nil) >> (gameWinner[k] != Black), IPL_DOM);
416 else
417 rel(*this, (gameWinner[k-1] == Nil) >> (gameWinner[k] != Red), IPL_DOM);
418 }
419 }
420
421 // For first move, symmetry is broken by removing the rightmost (upper): col - (col div 2)
422 if (kOffset == 0) rel(*this, m[0], IRT_LE, col - (col / 2), IPL_DOM);
423
424 // Force a winner at the end of the game
425 rel(*this, gameWinner[nbDecisionVar-1], IRT_EQ, Red, IPL_DOM);
426
427 if (opt.QCSPmodel() == 1) {
428 // Set the last board full.
429 // Useless if we prune universal, but needed for the simple model.
430 // Notice that it is not compatible with the -depth argument as all board
431 // doesn't have to be filled.
432 for (int i=0; i < col; i++)
433 for (int j=0; j < row; j++)
434 rel(*this, board[(nbDecisionVar-1)*row*col+i*row+j] != Nil, IPL_DOM);
435 }
436 }
437
438 ConnectFourAllState(bool share, ConnectFourAllState& p)
439 : Script(share,p), QSpaceInfo(*this,share,p), row(p.row), col(p.col), kOffset(p.kOffset), opt(p.opt)
440 {
441 M.update(*this,share,p.M);
442 if (opt.QCSPmodel() == 1) U.update(*this,share,p.U);
443 board.update(*this,share,p.board);
444 h.update(*this,share,p.h);
445 mh.update(*this,share,p.mh);
446 line.update(*this,share,p.line);
447 lineMove.update(*this,share,p.lineMove);
448 pos.update(*this,share,p.pos);
449 gameWinner.update(*this,share,p.gameWinner);
450 moveDone.update(*this,share,p.moveDone);
451 }
452
453 virtual Space* copy(bool share) { return new ConnectFourAllState(share,*this); }
454
455
456 int c4Heuristic(IntVar x, int k) const {
457 if (k == 0) return x.max();
458 std::vector<int> boardBefore(row*col);
459 int offSet = row*col*(k-1);
460 for (int i=row-1; i>=0; i--)
461 for (int j=0; j<col; j++) {
462 assert(board[offSet+j*row+i].assigned());
463 boardBefore[j*row+i] = board[offSet+j*row+i].val();
464 }
465
466 // now we have move number and
467 // previous board state
468 int bestScore=0;
469 int bestMove=x.min();
470
471 for (IntVarValues vv(x); vv(); ++vv) {
472 int j = vv.val();
473 assert(h[(k-1)*col+j].assigned());
474 int i = h[(k-1)*col+j].val();
475
476 if ((i = h[(k-1)*col+j].val()) < row) { // The column is not full
477 boardBefore[j*row+i] = ((k%2)==0)?Red:Black;
478
479 if (((k%2) == 0) && checklines<Red>(boardBefore)) return j; // Leftmost winning move
480 else if (((k%2) == 1) && checklines<Black>(boardBefore)) return j; // Leftmost winning move
481
482 int score;
483 if ((k%2) == 0) { // Red player
484 score = check3lines<Red>(boardBefore);
485 } else { // Black player
486 score = check3lines<Black>(boardBefore);
487 }
488
489 if (score > bestScore) {
490 bestScore = score;
491 bestMove = j;
492 }
493 boardBefore[j*row+i] = Nil;
494 }
495 }
496
497 return bestMove;
498 }
499
500 template <int Player>
501 int check3lines(std::vector<int>& board) const {
502 int lines = 0;
503 // Detect winning blocks
504 for (int z=0; z<4; z++) { // Row(0) / Col(1) / Diag1(2) / Diag2(3)
505 for (int i=0; i < col; i++) {
506 for (int j=0; j < row; j++) {
507 if (((z%4)==0) && (i+3) < col) { // Line in row
508 if (check4for3<Player>(board[i*row+j], board[(i+1)*row+j], board[(i+2)*row+j], board[(i+3)*row+j]))
509 lines++;
510 }
511 if (((z%4)==1) && (j+3) < row) {// Line in column
512 if (check4for3<Player>(board[i*row+j], board[i*row+j+1], board[i*row+j+2], board[i*row+j+3]))
513 lines++;
514 }
515 if (((z%4)==2) && ((i+3) < col) && ((j+3) < row)) { // Line in diag1
516 if (check4for3<Player>(board[i*row+j], board[(i+1)*row+j+1], board[(i+2)*row+j+2], board[(i+3)*row+j+3]))
517 lines++;
518 }
519 if (((z%4)==3) && ((i-3) >= 0) && ((j+3) < row)) { // Line in diag2
520 if (check4for3<Player>(board[i*row+j], board[(i-1)*row+j+1], board[(i-2)*row+j+2], board[(i-3)*row+j+3]))
521 lines++;
522 }
523 }
524 }
525 }
526 return lines;
527 }
528
529 template <int Player>
530 bool check4for3(int a, int b, int c, int d) const {
531 if ((a == Player) && (b == Player) && (c == Player)) return (d == Nil);
532 else if ((a == Player) && (b == Player) && (d == Player)) return (c == Nil);
533 else if ((a == Player) && (c == Player) && (d == Player)) return (b == Nil);
534 else if ((b == Player) && (c == Player) && (d == Player)) return (a == Nil);
535 else return false;
536 }
537
538 template <int Player>
539 bool checklines(std::vector<int>& board) const {
540 // Detect winning blocks
541 for (int z=0; z<4; z++) { // Row(0) / Col(1) / Diag1(2) / Diag2(3)
542 for (int i=0; i < col; i++) {
543 for (int j=0; j < row; j++) {
544 if (((z%4)==0) && (i+3) < col) { // Line in row
545 if ((board[i*row+j] == Player) && (board[(i+1)*row+j] == Player) && (board[(i+2)*row+j] == Player) && (board[(i+3)*row+j] == Player)) return true;
546 }
547 if (((z%4)==1) && (j+3) < row) {// Line in column
548 if ((board[i*row+j] == Player) && (board[i*row+j+1] == Player) && (board[i*row+j+2] == Player) && (board[i*row+j+3] == Player)) return true;
549 }
550 if (((z%4)==2) && ((i+3) < col) && ((j+3) < row)) { // Line in diag1
551 if ((board[i*row+j] == Player) && (board[(i+1)*row+j+1] == Player) && (board[(i+2)*row+j+2] == Player) && (board[(i+3)*row+j+3] == Player)) return true;
552 }
553 if (((z%4)==3) && ((i-3) >= 0) && ((j+3) < row)) { // Line in diag2
554 if ((board[i*row+j] == Player) && (board[(i-1)*row+j+1] == Player) && (board[(i-2)*row+j+2] == Player) && (board[(i-3)*row+j+3] == Player)) return true;
555 }
556 }
557 }
558 }
559 return false;
560 }
561
562 void print(std::ostream& os) const {
563 strategyPrint(os);
564 }
565};
566
567template <int N> int
568c4Heuristic<N>::value(const Space& _home, IntVar x, int) {
569 const ConnectFourAllState& home = static_cast<const ConnectFourAllState&>(_home);
570 return home.c4Heuristic(x,N);
571}
572
573const int ConnectFourAllState::Red;
574const int ConnectFourAllState::Black;
575const int ConnectFourAllState::Nil;
576
577int main(int argc, char* argv[])
578{
579
580 ConnectFourOptions opt("QCSP Connect-Four-Game");
581 opt.parse(argc,argv);
582 Script::run<ConnectFourAllState,QDFS,ConnectFourOptions>(opt);
583
584 return 0;
585}