domino.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
* Mikael Lagerkvist <lagerkvist@gecode.org>
*
* Copyright:
* Guido Tack, 2006
* Mikael Lagerkvist, 2006
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
using namespace Gecode;
namespace {
extern const int *specs[];
extern const unsigned int n_examples;
}
class Domino : public Script {
private:
const int *spec;
int width;
int height;
IntVarArray x;
public:
enum {
PROP_ELEMENT,
PROP_EXTENSIONAL
};
Domino(const SizeOptions& opt)
: Script(opt),
spec(specs[opt.size()]),
width(spec[0]), height(spec[1]),
x(*this, (width+1)*height, 0, 28) {
spec+=2; // skip board size information
// Copy spec information to the board
IntArgs board((width+1)*height);
for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
board[j*(width+1)+i] = spec[j*width+i];
// Initialize the separator column in the board
for (int i=0; i<height; i++) {
board[i*(width+1)+8] = -1;
rel(*this, x[i*(width+1)+8]==28);
}
// Variables representing the coordinates of the first
// and second half of a domino piece
IntVarArgs p1(*this, 28, 0, (width+1)*height-1);
IntVarArgs p2(*this, 28, 0, (width+1)*height-1);
if (opt.propagation() == PROP_ELEMENT) {
int dominoCount = 0;
int possibleDiffsA[] = {1, width+1};
IntSet possibleDiffs(possibleDiffsA, 2);
for (int i=0; i<=6; i++)
for (int j=i; j<=6; j++) {
// The two coordinates must be adjacent.
// I.e., they may differ by 1 or by the width.
// The separator column makes sure that a field
// at the right border is not adjacent to the first field
// in the next row.
IntVar diff(*this, possibleDiffs);
abs(*this, expr(*this, p1[dominoCount]-p2[dominoCount]),
diff, IPL_DOM);
// If the piece is symmetrical, order the locations
if (i == j)
rel(*this, p1[dominoCount], IRT_LE, p2[dominoCount]);
// Link the current piece to the board
element(*this, board, p1[dominoCount], i);
element(*this, board, p2[dominoCount], j);
// Link the current piece to the array where its
// number is stored.
element(*this, x, p1[dominoCount], dominoCount);
element(*this, x, p2[dominoCount], dominoCount);
dominoCount++;
}
} else {
int dominoCount = 0;
for (int i=0; i<=6; i++)
for (int j=i; j<=6; j++) {
// Find valid placements for piece i-j
// Extensional is used as a table-constraint listing all valid
// tuples.
// Note that when i == j, only one of the orientations are used.
REG valids;
for (int pos = 0; pos < (width+1)*height; ++pos) {
if ((pos+1) % (width+1) != 0) { // not end-col
if (board[pos] == i && board[pos+1] == j)
valids |= REG(pos) + REG(pos+1);
if (board[pos] == j && board[pos+1] == i && i != j)
valids |= REG(pos+1) + REG(pos);
}
if (pos/(width+1) < height-1) { // not end-row
if (board[pos] == i && board[pos+width+1] == j)
valids |= REG(pos) + REG(pos+width+1);
if (board[pos] == j && board[pos+width+1] == i && i != j)
valids |= REG(pos+width+1) + REG(pos);
}
}
extensional(*this, IntVarArgs({p1[dominoCount],p2[dominoCount]}),
valids);
// Link the current piece to the array where its
// number is stored.
element(*this, x, p1[dominoCount], dominoCount);
element(*this, x, p2[dominoCount], dominoCount);
dominoCount++;
}
}
// Branch by piece
IntVarArgs ps(28*2);
for (int i=0; i<28; i++) {
ps[2*i] = p1[i];
ps[2*i+1] = p2[i];
}
branch(*this, ps, INT_VAR_NONE(), INT_VAL_MIN());
}
virtual void
print(std::ostream& os) const {
for (int h = 0; h < height; ++h) {
os << "\t";
for (int w = 0; w < width; ++w) {
int val = x[h*(width+1)+w].min();
char c = val < 10 ? '0'+val : 'A' + (val-10);
os << c;
}
os << std::endl;
}
os << std::endl;
}
Domino(Domino& s) :
Script(s), spec(s.spec), width(s.width), height(s.height) {
x.update(*this, s.x);
}
virtual Space*
copy(void) {
return new Domino(*this);
}
};
int
main(int argc, char* argv[]) {
SizeOptions opt("Domino");
opt.size(0);
opt.propagation(Domino::PROP_ELEMENT);
opt.propagation(Domino::PROP_ELEMENT, "element");
opt.propagation(Domino::PROP_EXTENSIONAL, "extensional");
opt.parse(argc,argv);
if (opt.size() >= n_examples) {
std::cerr << "Error: size must be between 0 and "
<< n_examples-1 << std::endl;
return 1;
}
Script::run<Domino,DFS,SizeOptions>(opt);
return 0;
}
namespace {
const int domino0[] =
{ // width*height of the board
8,7,
// the board itself
2,1,0,3,0,4,5,5,
6,2,0,6,3,1,4,0,
3,2,3,6,2,5,4,3,
5,4,5,1,1,2,1,2,
0,0,1,5,0,5,4,4,
4,6,2,1,3,6,6,1,
4,2,0,6,5,3,3,6
};
const int domino1[] =
{ // width*height of the board
8,7,
// the board itself
5,1,2,4,6,2,0,5,
6,6,4,3,5,0,1,5,
2,0,4,0,4,0,5,0,
6,1,3,6,3,5,4,3,
3,1,0,1,2,2,1,4,
3,6,6,2,4,0,5,4,
1,3,6,1,2,3,5,2
};
const int domino2[] =
{ // width*height of the board
8,7,
// the board itself
4,4,5,4,0,3,6,5,
1,6,0,1,5,3,4,1,
2,6,2,2,5,3,6,0,
1,3,0,6,4,4,2,3,
3,5,5,2,4,2,2,1,
2,1,3,3,5,6,6,1,
5,1,6,0,0,0,4,0
};
const int domino3[] =
{ // width*height of the board
8,7,
// the board itself
3,0,2,3,3,4,4,3,
6,5,3,4,2,0,2,1,
6,5,1,2,3,0,2,0,
4,5,4,1,6,6,2,5,
4,3,6,1,0,4,5,5,
1,3,2,5,6,0,0,1,
0,5,4,6,2,1,6,1
};
const int domino4[] =
{ // width*height of the board
8,7,
// the board itself
4,1,5,2,4,4,6,2,
2,5,6,1,4,6,0,2,
6,5,1,1,0,1,4,3,
6,2,1,1,3,2,0,6,
3,6,3,3,5,5,0,5,
3,0,1,0,0,5,4,3,
3,2,4,5,4,2,6,0
};
const int domino5[] =
{ // width*height of the board
8,7,
// the board itself
4,1,2,1,0,2,4,4,
5,5,6,6,0,4,6,3,
6,0,5,1,1,0,5,3,
3,4,2,2,0,3,1,2,
3,6,5,6,1,2,3,2,
2,5,0,6,6,3,3,5,
4,1,0,0,4,1,4,5
};
const int *specs[] =
{domino0,domino1,domino2,domino3,domino4,domino5};
const unsigned n_examples = sizeof(specs)/sizeof(int*);
}
// STATISTICS: example-any
Domino::main
int main(int argc, char *argv[])
Main-function.
Definition domino.cpp:223
Domino::copy
virtual Space * copy(void)
Copy space during cloning.
Definition domino.cpp:212
Domino::n_examples
const unsigned int n_examples
Number of board specifications.
Definition domino.cpp:53
Domino::Domino
Domino(Domino &s)
Constructor for cloning s.
Definition domino.cpp:206
Domino::domino1
const int domino1[]
Example 1
Definition domino.cpp:263
Domino::domino3
const int domino3[]
Example 3
Definition domino.cpp:291
Domino::domino0
const int domino0[]
Example 0
Definition domino.cpp:249
Domino::print
virtual void print(std::ostream &os) const
Print solution.
Definition domino.cpp:193
Domino::domino5
const int domino5[]
Example 5
Definition domino.cpp:319
Domino::domino2
const int domino2[]
Example 2
Definition domino.cpp:277
Domino::PROP_EXTENSIONAL
@ PROP_EXTENSIONAL
Use extensional constraints.
Definition domino.cpp:84
Domino::PROP_ELEMENT
@ PROP_ELEMENT
Use element constraints.
Definition domino.cpp:83
Domino::domino4
const int domino4[]
Example 4
Definition domino.cpp:305
Domino::Domino
Domino(const SizeOptions &opt)
Actual model.
Definition domino.cpp:88
Domino::specs
const int * specs[]
Board specifications.
Definition domino.cpp:48
Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >::run
static void run(const Options &opt, Script *s=NULL)
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::IntSet
Integer sets.
Definition int.hh:174
Gecode::IntVarArgs
Passing integer variables.
Definition int.hh:656
Gecode::IntVarArray
Integer variable array.
Definition int.hh:763
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::REG
Regular expressions over integer values.
Definition minimodel.hh:1625
Gecode::SizeOptions
Options for scripts with additional size parameter
Definition driver.hh:675
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Test::Options::parse
void parse(int argc, char *argv[])
Parse commandline arguments.
Definition test.cpp:120
driver.hh
int.hh
Gecode::Script
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:801
Gecode::branch
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
Gecode::rel
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
Gecode::extensional
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
Definition extensional-regular.cpp:39
Gecode::IRT_LE
@ IRT_LE
Less ( ).
Definition int.hh:929
Gecode::IPL_DOM
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
minimodel.hh
Gecode
Gecode toplevel namespace
Gecode::expr
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::INT_VAR_NONE
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
Gecode::abs
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition arithmetic.cpp:41
Gecode::element
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
Gecode::INT_VAL_MIN
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55