42 using namespace Gecode;
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&);
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)
const {
291 for (
int i=0;
i<nspecs;
i++)
298 REG tile_reg(
int twidth,
int theight,
const char* tile,
300 REG oe = other | eol;
303 for (
int h = 0; h < theight; ++h) {
304 for (
int w = 0; w < twidth; ++w) {
305 int which = tile[h*twidth + w] ==
'X';
309 res += oe(width-twidth, width-twidth);
321 char *t2 =
new char[width*height];
323 tsymmfunc syms[] = {id, flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
324 int symscnt =
sizeof(syms)/
sizeof(tsymmfunc);
325 for (
int i = 0;
i < symscnt; ++
i) {
327 res = res | tile_reg(
w2, h2, t2,
mark, other, eol);
339 width(spec[0].width+1),
340 height(spec[0].height),
341 filled(spec[0].amount),
342 nspecs(examples_size[
opt.
size()]-1),
343 ntiles(compute_number_of_tiles(spec+1, nspecs)),
344 board(*this, width*height, filled,ntiles+1) {
348 for (
int h = 0; h < height; ++h) {
349 for (
int w = 0; w < width-1; ++w)
350 rel(*
this, board[h*width + w],
IRT_NQ, ntiles+1);
351 rel(*
this, board[h*width + width - 1],
IRT_EQ, ntiles+1);
355 if (
opt.propagation() == PROPAGATION_INT) {
357 for (
int i = 0;
i < nspecs; ++
i) {
358 for (
int j = 0; j < spec[
i].
amount; ++j) {
366 for (
int j = filled; j <= ntiles; ++j) {
367 if (j == col)
continue;
382 int ncolors = ntiles + 2;
387 for (
int i=board.
size();
i--; ) {
389 for (
int j=ncolors; j--; )
399 for (
int i = 0;
i < nspecs; ++
i) {
400 for (
int j = 0; j < spec[
i].
amount; ++j) {
405 for (
int k = board.
size(); k--; ) {
406 c[k] =
p[k*ncolors+col];
415 if (
opt.symmetry() == SYMMETRY_FULL) {
419 for (
int i = 0;
i < board.
size(); ++
i) {
420 if ((
i+1)%width==0)
continue;
421 orig[
pos++] = board[
i];
425 bsymmfunc syms[] = {flipx, flipy, flipd1, flipd2, rot90, rot180, rot270};
426 int symscnt =
sizeof(syms)/
sizeof(bsymmfunc);
427 for (
int i = 0;
i < symscnt; ++
i) {
428 syms[
i](orig, width-1, height, symm,
w2, h2);
429 if (width-1 ==
w2 && height == h2)
440 Script(s), spec(s.spec), width(s.width), height(s.height),
441 filled(s.filled), nspecs(s.nspecs) {
442 board.
update(*
this, s.board);
454 for (
int h = 0; h < height; ++h) {
456 for (
int w = 0; w < width-1; ++w) {
457 int val = board[h*width + w].val();
458 char c = val < 10 ?
'0'+val :
'A' + (val-10);
477 "none",
"do not remove symmetric solutions");
479 "full",
"remove symmetric solutions");
483 "int",
"use integer propagators");
485 "bool",
"use Boolean propagators");
488 if (
opt.size() >= n_examples) {
489 std::cerr <<
"Error: size must be between 0 and "
490 << n_examples-1 << std::endl;
493 Script::run<Pentominoes,DFS,SizeOptions>(
opt);
863 const TileSpec *examples[] = {puzzle0, puzzle1, square2, square3,
864 pentomino6x10,pentomino5x12,
865 pentomino4x15,pentomino3x20};
866 const int examples_size[] = {
sizeof(puzzle0)/
sizeof(
TileSpec),
870 sizeof(pentomino6x10)/
sizeof(
TileSpec),
871 sizeof(pentomino5x12)/
sizeof(
TileSpec),
872 sizeof(pentomino4x15)/
sizeof(
TileSpec),
873 sizeof(pentomino3x20)/
sizeof(
TileSpec)};
876 const unsigned n_examples =
sizeof(examples)/
sizeof(
TileSpec*);
881 int pos(
int h,
int w,
int h1,
int w1) {
882 if (!(0 <= h && h < h1) ||
883 !(0 <= w && w <
w1)) {
884 std::cerr <<
"Cannot place (" << h <<
"," << w
885 <<
") on board of size " << h1 <<
"x" <<
w1 << std::endl;
889 template<
class CArray,
class Array>
890 void id(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int&h2) {
892 for (
int h = 0; h < h1; ++h)
893 for (
int w = 0; w <
w1; ++w)
894 t2[
pos(h, w, h2,
w2)] = t1[
pos(h, w, h1,
w1)];
896 template<
class CArray,
class Array>
897 void rot90(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2) {
899 for (
int h = 0; h < h1; ++h)
900 for (
int w = 0; w <
w1; ++w)
903 template<
class CArray,
class Array>
904 void rot180(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2) {
906 for (
int h = 0; h < h1; ++h)
907 for (
int w = 0; w <
w1; ++w)
908 t2[
pos(h2-h-1,
w2-w-1, h2,
w2)] = t1[
pos(h, w, h1,
w1)];
910 template<
class CArray,
class Array>
911 void rot270(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2) {
913 for (
int h = 0; h < h1; ++h)
914 for (
int w = 0; w <
w1; ++w)
915 t2[
pos(h2-w-1, h, h2,
w2)] = t1[
pos(h, w, h1,
w1)];
917 template<
class CArray,
class Array>
918 void flipx(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2) {
920 for (
int h = 0; h < h1; ++h)
921 for (
int w = 0; w <
w1; ++w)
924 template<
class CArray,
class Array>
925 void flipy(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2) {
927 for (
int h = 0; h < h1; ++h)
928 for (
int w = 0; w <
w1; ++w)
929 t2[
pos(h2-h-1, w, h2,
w2)] = t1[
pos(h, w, h1,
w1)];
931 template<
class CArray,
class Array>
932 void flipd1(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2) {
934 for (
int h = 0; h < h1; ++h)
935 for (
int w = 0; w <
w1; ++w)
936 t2[
pos(w, h, h2,
w2)] = t1[
pos(h, w, h1,
w1)];
938 template<
class CArray,
class Array>
939 void flipd2(CArray t1,
int w1,
int h1, Array t2,
int&
w2,
int& h2) {
941 for (
int h = 0; h < h1; ++h)
942 for (
int w = 0; w <
w1; ++w)
943 t2[
pos(h2-w-1,
w2-h-1, h2,
w2)] = t1[
pos(h, w, h1,
w1)];
int p
Number of positive literals for node type.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Passing Boolean variables.
Parametric base-class for scripts.
Passing integer variables.
void propagation(int v)
Set default propagation value.
void symmetry(int v)
Set default symmetry value.
Regular expressions over integer values.
Options for scripts with additional size parameter
int size(void) const
Return size of array (number of elements)
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
int main(int argc, char *argv[])
Main-function.
@ PROPAGATION_BOOLEAN
Use Boolean propagators.
@ PROPAGATION_INT
Use integer propagators.
const unsigned int n_examples
Number of board specifications.
void flipy(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Flip y-wise.
void flipx(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Flip x-wise.
void flipd2(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Flip diagonal 2.
void rot180(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Rotate 180 degrees.
void rot90(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Rotate 90 degrees.
virtual Space * copy(void)
Copy space during cloning.
void rot270(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Rotate 270 degrees.
@ SYMMETRY_NONE
Do not remove symmetric solutions.
@ SYMMETRY_FULL
Remove symmetric solutions.
int pos(int h, int w, int h1, int w1)
Pentominoes(Pentominoes &s)
Constructor for cloning s.
void id(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Identity symmetry.
void flipd1(CArray t1, int w1, int h1, Array t2, int &w2, int &h2)
Flip diagonal 1.
Pentominoes(const SizeOptions &opt)
Construction of the model.
virtual void print(std::ostream &os) const
Print solution.
Specification of one tile.
int amount
Number of tiles.
const char * tile
Picture of tile.
int height
Height of tile.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
void extensional(Home home, const IntVarArgs &x, DFA dfa, IntPropLevel)
Post domain consistent propagator for extensional constraint described by a DFA.
@ IRT_LQ
Less or equal ( )
IntValBranch INT_VAL_MIN(void)
Select smallest value.
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
bool pos(const View &x)
Test whether x is postive.
unsigned int size(I &i)
Size of all ranges of range iterator i.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})