73 extern const int examples_size[];
93 int pos(
int h,
int w,
int h1,
int w1);
95 typedef void (*tsymmfunc)(
const char*, int, int,
char*,
int&,
int&);
97 typedef void (*bsymmfunc)(
const IntVarArgs, int, int, IntVarArgs&,
int&,
int&);
99 template<
class CArray,
class Array>
100 void id(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int&h2);
102 template<
class CArray,
class Array>
103 void rot90(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
105 template<
class CArray,
class Array>
106 void rot180(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
108 template<
class CArray,
class Array>
109 void rot270(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
111 template<
class CArray,
class Array>
112 void flipx(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
114 template<
class CArray,
class Array>
115 void flipy(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
117 template<
class CArray,
class Array>
118 void flipd1(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
120 template<
class CArray,
class Array>
121 void flipd2(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2);
289 int compute_number_of_tiles(
const TileSpec* ts,
int nspecs) {
291 for (
int i = nspecs;
i--; ) {
299 REG tile_reg(
int twidth,
int theight,
const char* tile,
301 REG oe = other | eol;
303 REG color[] = {other, mark};
304 for (
int h = 0; h < theight; ++h) {
305 for (
int w = 0; w < twidth; ++w) {
306 int which = tile[h*twidth + w] ==
'X';
310 res += oe(width-twidth, width-twidth);
322 char *t2 =
new char[width*height];
324 tsymmfunc syms[] = {id, flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
325 int symscnt =
sizeof(syms)/
sizeof(tsymmfunc);
326 for (
int i = 0;
i < symscnt; ++
i) {
328 res = res | tile_reg(w2, h2, t2, mark, other, eol);
340 width(spec[0].width+1),
341 height(spec[0].height),
342 filled(spec[0].amount),
343 nspecs(examples_size[opt.
size()]-1),
344 ntiles(compute_number_of_tiles(spec+1, nspecs)),
345 board(*this, width*height, filled,ntiles+1) {
349 for (
int h = 0; h < height; ++h) {
350 for (
int w = 0; w < width-1; ++w)
351 rel(*
this, board[h*width + w],
IRT_NQ, ntiles+1);
352 rel(*
this, board[h*width + width - 1],
IRT_EQ, ntiles+1);
358 for (
int i = 0;
i < nspecs; ++
i) {
359 for (
int j = 0; j < spec[
i].
amount; ++j) {
367 for (
int j = filled; j <= ntiles; ++j) {
368 if (j == col)
continue;
378 extensional(*
this, board, get_constraint(
i, mark, other, eol));
383 int ncolors = ntiles + 2;
388 for (
int i=board.
size();
i--; ) {
390 for (
int j=ncolors; j--; )
400 for (
int i = 0;
i < nspecs; ++
i) {
401 for (
int j = 0; j < spec[
i].
amount; ++j) {
406 for (
int k = board.
size(); k--; ) {
407 c[k] =
p[k*ncolors+col];
410 extensional(*
this,
c, get_constraint(
i, mark, other, other));
416 if (opt.
symmetry() == SYMMETRY_FULL) {
420 for (
int i = 0;
i < board.
size(); ++
i) {
421 if ((
i+1)%width==0)
continue;
422 orig[pos++] = board[
i];
426 bsymmfunc syms[] = {flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
427 int symscnt =
sizeof(syms)/
sizeof(bsymmfunc);
428 for (
int i = 0;
i < symscnt; ++
i) {
429 syms[
i](orig, width-1, height, symm,
w2, h2);
430 if (width-1 == w2 && height == h2)
441 Script(s), spec(s.spec), width(s.width), height(s.height),
442 filled(s.filled), nspecs(s.nspecs) {
443 board.
update(*
this, s.board);
455 for (
int h = 0; h < height; ++h) {
457 for (
int w = 0; w < width-1; ++w) {
458 int val = board[h*width + w].val();
459 char c = val < 10 ?
'0'+val :
'A' + (val-10);
478 "none",
"do not remove symmetric solutions");
480 "full",
"remove symmetric solutions");
484 "int",
"use integer propagators");
486 "bool",
"use Boolean propagators");
488 opt.
parse(argc,argv);
489 if (opt.
size() >= n_examples) {
490 std::cerr <<
"Error: size must be between 0 and " 491 << n_examples-1 << std::endl;
494 Script::run<Pentominoes,DFS,SizeOptions>(
opt);
864 const TileSpec *examples[] = {puzzle0, puzzle1, square2, square3,
865 pentomino6x10,pentomino5x12,
866 pentomino4x15,pentomino3x20};
867 const int examples_size[] = {
sizeof(puzzle0)/
sizeof(
TileSpec),
871 sizeof(pentomino6x10)/
sizeof(
TileSpec),
872 sizeof(pentomino5x12)/
sizeof(
TileSpec),
873 sizeof(pentomino4x15)/
sizeof(
TileSpec),
874 sizeof(pentomino3x20)/
sizeof(
TileSpec)};
877 const unsigned n_examples =
sizeof(examples)/
sizeof(
TileSpec*);
882 int pos(
int h,
int w,
int h1,
int w1) {
883 if (!(0 <= h && h < h1) ||
884 !(0 <= w && w < w1)) {
885 std::cerr <<
"Cannot place (" << h <<
"," << w
886 <<
") on board of size " << h1 <<
"x" << w1 << std::endl;
890 template<
class CArray,
class Array>
891 void id(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int&h2) {
893 for (
int h = 0; h < h1; ++h)
894 for (
int w = 0; w <
w1; ++w)
895 t2[
pos(h, w, h2, w2)] = t1[
pos(h, w, h1, w1)];
897 template<
class CArray,
class Array>
898 void rot90(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
900 for (
int h = 0; h < h1; ++h)
901 for (
int w = 0; w <
w1; ++w)
902 t2[
pos(w, w2-h-1, h2, w2)] = t1[
pos(h, w, h1, w1)];
904 template<
class CArray,
class Array>
905 void rot180(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
907 for (
int h = 0; h < h1; ++h)
908 for (
int w = 0; w <
w1; ++w)
909 t2[
pos(h2-h-1, w2-w-1, h2, w2)] = t1[
pos(h, w, h1, w1)];
911 template<
class CArray,
class Array>
912 void rot270(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
914 for (
int h = 0; h < h1; ++h)
915 for (
int w = 0; w <
w1; ++w)
916 t2[
pos(h2-w-1, h, h2, w2)] = t1[
pos(h, w, h1, w1)];
918 template<
class CArray,
class Array>
919 void flipx(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
921 for (
int h = 0; h < h1; ++h)
922 for (
int w = 0; w <
w1; ++w)
923 t2[
pos(h, w2-w-1, h2, w2)] = t1[
pos(h, w, h1, w1)];
925 template<
class CArray,
class Array>
926 void flipy(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
928 for (
int h = 0; h < h1; ++h)
929 for (
int w = 0; w <
w1; ++w)
930 t2[
pos(h2-h-1, w, h2, w2)] = t1[
pos(h, w, h1, w1)];
932 template<
class CArray,
class Array>
933 void flipd1(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
935 for (
int h = 0; h < h1; ++h)
936 for (
int w = 0; w <
w1; ++w)
937 t2[
pos(w, h, h2, w2)] = t1[
pos(h, w, h1, w1)];
939 template<
class CArray,
class Array>
940 void flipd2(CArray t1,
int w1,
int h1, Array t2,
int& w2,
int& h2) {
942 for (
int h = 0; h < h1; ++h)
943 for (
int w = 0; w <
w1; ++w)
944 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 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.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
int size(void) const
Return size of array (number of elements)
void propagation(int v)
Set default propagation value.
Do not remove symmetric solutions.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
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.
virtual void print(std::ostream &os) const
Print solution.
int height
Height of tile.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
int main(int argc, char *argv[])
Main-function.
Parametric base-class for scripts.
Pentominoes(const SizeOptions &opt)
Construction of the model.
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual Space * copy(void)
Copy space during cloning.
const unsigned int n_examples
Number of board specifications.
Passing integer variables.
Passing Boolean variables.
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 .
Pentominoes(Pentominoes &s)
Constructor for cloning s.
Gecode toplevel namespace
Specification of one tile.
Remove symmetric solutions.