77 extern const int examples_size[];
97 int pos(
int h,
int w,
int h1,
int w1);
99 typedef void (*tsymmfunc)(
const char*, int, int,
char*,
int&,
int&);
101 typedef void (*bsymmfunc)(
const IntVarArgs, int, int, IntVarArgs&,
int&,
int&);
103 template<
class CArray,
class Array>
104 void id(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int&h2);
106 template<
class CArray,
class Array>
107 void rot90(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
109 template<
class CArray,
class Array>
110 void rot180(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
112 template<
class CArray,
class Array>
113 void rot270(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
115 template<
class CArray,
class Array>
116 void flipx(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
118 template<
class CArray,
class Array>
119 void flipy(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
121 template<
class CArray,
class Array>
122 void flipd1(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
124 template<
class CArray,
class Array>
125 void flipd2(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
293 int compute_number_of_tiles(
const TileSpec* ts,
int nspecs) {
295 for (
int i = nspecs;
i--; ) {
303 REG tile_reg(
int twidth,
int theight,
const char* tile,
305 REG oe = other | eol;
307 REG color[] = {other, mark};
308 for (
int h = 0; h < theight; ++h) {
309 for (
int w = 0; w < twidth; ++w) {
310 int which = tile[h*twidth + w] ==
'X';
314 res += oe(width-twidth, width-twidth);
326 char *t2 =
new char[width*height];
328 tsymmfunc syms[] = {id, flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
329 int symscnt =
sizeof(syms)/
sizeof(tsymmfunc);
330 for (
int i = 0;
i < symscnt; ++
i) {
332 res = res | tile_reg(w2, h2, t2, mark, other, eol);
343 : spec(examples[opt.
size()]),
344 width(spec[0].width+1),
345 height(spec[0].height),
346 filled(spec[0].amount),
347 nspecs(examples_size[opt.
size()]-1),
348 ntiles(compute_number_of_tiles(spec+1, nspecs)),
349 board(*this, width*height, filled,ntiles+1) {
353 for (
int h = 0; h < height; ++h) {
354 for (
int w = 0; w < width-1; ++w)
355 rel(*
this, board[h*width + w],
IRT_NQ, ntiles+1);
356 rel(*
this, board[h*width + width - 1],
IRT_EQ, ntiles+1);
362 for (
int i = 0;
i < nspecs; ++
i) {
363 for (
int j = 0; j < spec[
i].
amount; ++j) {
371 for (
int j = filled; j <= ntiles; ++j) {
372 if (j == col)
continue;
382 extensional(*
this, board, get_constraint(
i, mark, other, eol));
387 int ncolors = ntiles + 2;
392 for (
int i=board.
size();
i--; ) {
394 for (
int j=ncolors; j--; )
404 for (
int i = 0;
i < nspecs; ++
i) {
405 for (
int j = 0; j < spec[
i].
amount; ++j) {
410 for (
int k = board.
size(); k--; ) {
411 c[k] =
p[k*ncolors+col];
414 extensional(*
this,
c, get_constraint(
i, mark, other, other));
420 if (opt.
symmetry() == SYMMETRY_FULL) {
424 for (
int i = 0;
i < board.
size(); ++
i) {
425 if ((
i+1)%width==0)
continue;
426 orig[pos++] = board[
i];
430 bsymmfunc syms[] = {flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
431 int symscnt =
sizeof(syms)/
sizeof(bsymmfunc);
432 for (
int i = 0;
i < symscnt; ++
i) {
433 syms[
i](orig, width-1, height, symm,
w2, h2);
434 if (width-1 == w2 && height == h2)
445 Script(share,s), spec(s.spec), width(s.width), height(s.height),
446 filled(s.filled), nspecs(s.nspecs) {
447 board.
update(*
this, share, s.board);
459 for (
int h = 0; h < height; ++h) {
461 for (
int w = 0; w < width-1; ++w) {
462 int val = board[h*width + w].val();
463 char c = val < 10 ?
'0'+val :
'A' + (val-10);
482 "none",
"do not remove symmetric solutions");
484 "full",
"remove symmetric solutions");
488 "int",
"use integer propagators");
490 "bool",
"use Boolean propagators");
492 opt.
parse(argc,argv);
493 if (opt.
size() >= n_examples) {
494 std::cerr <<
"Error: size must be between 0 and "
495 << n_examples-1 << std::endl;
498 Script::run<Pentominoes,DFS,SizeOptions>(
opt);
868 const TileSpec *examples[] = {puzzle0, puzzle1, square2, square3,
869 pentomino6x10,pentomino5x12,
870 pentomino4x15,pentomino3x20};
871 const int examples_size[] = {
sizeof(puzzle0)/
sizeof(
TileSpec),
875 sizeof(pentomino6x10)/
sizeof(
TileSpec),
876 sizeof(pentomino5x12)/
sizeof(
TileSpec),
877 sizeof(pentomino4x15)/
sizeof(
TileSpec),
878 sizeof(pentomino3x20)/
sizeof(
TileSpec)};
881 const unsigned n_examples =
sizeof(examples)/
sizeof(
TileSpec*);
886 int pos(
int h,
int w,
int h1,
int w1) {
887 if (!(0 <= h && h < h1) ||
888 !(0 <= w && w < w1)) {
889 std::cerr <<
"Cannot place (" << h <<
"," << w
890 <<
") on board of size " << h1 <<
"x" << w1 << std::endl;
894 template<
class CArray,
class Array>
895 void id(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int&h2) {
897 for (
int h = 0; h < h1; ++h)
898 for (
int w = 0; w <
w1; ++w)
899 t2[
pos(h, w, h2, w2)] = t1[
pos(h, w, h1, w1)];
901 template<
class CArray,
class Array>
902 void rot90(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
904 for (
int h = 0; h < h1; ++h)
905 for (
int w = 0; w <
w1; ++w)
906 t2[
pos(w, w2-h-1, h2, w2)] = t1[
pos(h, w, h1, w1)];
908 template<
class CArray,
class Array>
909 void rot180(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
911 for (
int h = 0; h < h1; ++h)
912 for (
int w = 0; w <
w1; ++w)
913 t2[
pos(h2-h-1, w2-w-1, h2, w2)] = t1[
pos(h, w, h1, w1)];
915 template<
class CArray,
class Array>
916 void rot270(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
918 for (
int h = 0; h < h1; ++h)
919 for (
int w = 0; w <
w1; ++w)
920 t2[
pos(h2-w-1, h, h2, w2)] = t1[
pos(h, w, h1, w1)];
922 template<
class CArray,
class Array>
923 void flipx(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
925 for (
int h = 0; h < h1; ++h)
926 for (
int w = 0; w <
w1; ++w)
927 t2[
pos(h, w2-w-1, h2, w2)] = t1[
pos(h, w, h1, w1)];
929 template<
class CArray,
class Array>
930 void flipy(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
932 for (
int h = 0; h < h1; ++h)
933 for (
int w = 0; w <
w1; ++w)
934 t2[
pos(h2-h-1, w, h2, w2)] = t1[
pos(h, w, h1, w1)];
936 template<
class CArray,
class Array>
937 void flipd1(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
939 for (
int h = 0; h < h1; ++h)
940 for (
int w = 0; w <
w1; ++w)
941 t2[
pos(w, h, h2, w2)] = t1[
pos(h, w, h1, w1)];
943 template<
class CArray,
class Array>
944 void flipd2(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
946 for (
int h = 0; h < h1; ++h)
947 for (
int w = 0; w <
w1; ++w)
948 t2[
pos(h2-w-1, w2-h-1, h2, w2)] = t1[
pos(h, w, h1, w1)];
void size(unsigned int s)
Set default size.
int amount
Number of tiles.
Options for scripts with additional size parameter
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
void propagation(int v)
Set default propagation value.
Regular expressions over integer values.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
bool pos(const View &x)
Test whether x is postive.
int height
Height of tile.
void * mark(void *p)
Return marked pointer for p.
int main(int argc, char *argv[])
Main-function.
Parametric base-class for scripts.
Pentominoes(const SizeOptions &opt)
Construction of the model.
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Do not remove symmetric solutions.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Pentominoes(bool share, Pentominoes &s)
Constructor for cloning s.
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual void print(std::ostream &os) const
Print solution.
Remove symmetric solutions.
const unsigned int n_examples
Number of board specifications.
Passing integer variables.
Passing Boolean variables.
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntConLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
const char * tile
Picture of tile.
void symmetry(int v)
Set default symmetry value.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
virtual Space * copy(bool share)
Copy space during cloning.
Gecode toplevel namespace
BrancherHandle branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
int size(void) const
Return size of array (number of elements)
Specification of one tile.