this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Lagerkvist <lagerkvist@gecode.org>
5 *
6 * Contributing authors:
7 * Guido Tack <tack@gecode.org>
8 *
9 * Copyright:
10 * Mikael Lagerkvist, 2006
11 * Guido Tack, 2006
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/driver.hh>
39#include <gecode/int.hh>
40#include <gecode/minimodel.hh>
41
42using namespace Gecode;
43
44/** \brief Specification of one tile
45 *
46 * This structure can be used to specify a tile with specified width
47 * and height, number of such tiles (all with unique values), and a
48 * char-array tile showing the tile in row-major order.
49 *
50 * \relates Pentominoes
51 */
52class TileSpec {
53public:
54 int width; ///< Width of tile
55 int height; ///< Height of tile
56 int amount; ///< Number of tiles
57 const char *tile; ///< Picture of tile
58};
59
60/** \brief Board specifications
61 *
62 * Each board specification repurposes the first two TileSpecs to
63 * record width and height of the board (TileSpec 0) as well as the
64 * number of tiles and whether the board is filled (TileSpec 1).
65 *
66 * \relates Pentominoes
67 */
68extern const TileSpec *examples[];
69/** \brief Board specification sizes
70 *
71 * \relates Pentominoes
72 */
73extern const int examples_size[];
74/** \brief Number of board specifications
75 *
76 * \relates Pentominoes
77 */
78extern const unsigned int n_examples;
79
80namespace {
81 /** \name Symmetry functions
82 *
83 * These functions implement the 8 symmetries of 2D planes. The
84 * functions are templatized so that they can be used both for the
85 * pieces (defined using C-strings) and for arrays of variables.
86 *
87 * \relates Pentominoes
88 */
89 //@{
90 /** Return index of (\a h, \a w) in the row-major layout of a matrix with
91 * width \a w1 and height \a h1.
92 */
93 int pos(int h, int w, int h1, int w1);
94 /// Type for tile symmetry functions
95 typedef void (*tsymmfunc)(const char*, int, int, char*, int&, int&);
96 /// Type for board symmetry functions
97 typedef void (*bsymmfunc)(const IntVarArgs, int, int, IntVarArgs&, int&, int&);
98 /// Identity symmetry
99 template<class CArray, class Array>
100 void id(CArray t1, int w1, int h1, Array t2, int& w2, int&h2);
101 /// Rotate 90 degrees
102 template<class CArray, class Array>
103 void rot90(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
104 /// Rotate 180 degrees
105 template<class CArray, class Array>
106 void rot180(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
107 /// Rotate 270 degrees
108 template<class CArray, class Array>
109 void rot270(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
110 /// Flip x-wise
111 template<class CArray, class Array>
112 void flipx(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
113 /// Flip y-wise
114 template<class CArray, class Array>
115 void flipy(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
116 /// Flip diagonal 1
117 template<class CArray, class Array>
118 void flipd1(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
119 /// Flip diagonal 2
120 template<class CArray, class Array>
121 void flipd2(CArray t1, int w1, int h1, Array t2, int& w2, int& h2);
122 //@}
123}
124
125/**
126 * \brief %Example: %Pentominoes
127 *
128 * \section ScriptPentominoesProblem The Problem
129 *
130 * This example places pieces of a puzzle, where each piece is
131 * composed of a collection of squares, onto a grid. The pieces may
132 * all be rotated and flipped freely. The goal is to place all the
133 * pieces on the grid, without any overlaps. An example piece to be
134 * placed looks like
135 * \code
136 * XXX
137 * X
138 * XXX
139 * \endcode
140 * in one of its rotations.
141 *
142 * The most famous instance of such a puzzle is the Pentominoes
143 * puzzle, where the pieces are all pieces formed by 5 four-connected
144 * squares.
145 *
146 *
147 * \section ScriptPentominoesVariables The Variables
148 *
149 * The variables for the model is the grid of squares that the pieces
150 * are placed on, where each of the variables for the squares takes
151 * the value of the number of the piece which is placed overonto it.
152 *
153 *
154 * \section ScriptPentominoesOnePiece Placing one piece
155 *
156 * The constraint for each piece placement uses regular expressions
157 * (and consequently the extensional constraint) for expressing
158 * placement of (rotated) pieces on the grid. Consider the simple
159 * example of placing the piece
160 * \code
161 * XX
162 * X
163 * X
164 * \endcode
165 * onto the 4 by 4 board
166 * \code
167 * 0123
168 * 4567
169 * 89AB
170 * CDEF
171 * \endcode
172 *
173 * Let the variables 0-F be 0/1-variables indicating if the piece is
174 * placed on that position or not. First consider placing the piece on
175 * some location, say covering 1,2,6, and A. Then, writing the
176 * sequence of values for the variables 0-F out, we get the string
177 * 0110001000100000. This string and all other strings corresponding
178 * to placing the above piece in that particular rotation can be
179 * described using the regular expression \f$0^*11000100010^*\f$. The
180 * expression indicates that first comes some number of zeroes, then
181 * two ones in a row (covering places 1 and 2 in our example
182 * placement), then comes exactly three 0's (not covering places 3, 4,
183 * and 5), and so on. The variable number of 0's at the beginning and at the end
184 * makes the expression match any placement of the piece on the board.
185 *
186 * There is one problem with the above constraint, since it allows
187 * placing the piece covering places 3, 4, 8, and C. That is, the
188 * piece may wrap around the board. To prohibit this, we add a new
189 * dummy-column to the board, so that it looks like
190 * \code
191 * 0123G
192 * 4567H
193 * 89ABI
194 * CDEFJ
195 * \endcode
196 * The variables for places G to J are all set to zero initially, and the
197 * regular expression for the placement of the piece is modified to
198 * include the extra column, \f$0^*1100001000010^*\f$.
199 *
200 *
201 * \section ScriptPentominoesRotatingPiece Rotating pieces
202 *
203 * To handle rotations of the piece, we can use disjunctions of
204 * regular expressions for all the relevant rotations. Consider the
205 * rotated version of the above piece, depicted below.
206 * \code
207 * X
208 * XXX
209 * \endcode
210 * The corresponding regular expression for this piece is
211 * \f$0^*1001110^*\f$. To combine these two regular expressions, we
212 * can simply use disjunction of regular expressions, arriving at the
213 * expression \f$0^*1100001000010^*|0^*1001110^*\f$ for enforcing
214 * the placement of the piece in one of the above two rotations.
215 *
216 * There are 8 symmetries for the pieces in general. The 8 disjuncts
217 * for a particular piece might, however, contain less than 8 distinct
218 * expressions (for example, any square has only one distinct
219 * disjunct). This is removed when then automaton for the expression
220 * is computed, since it is minimized.
221 *
222 *
223 * \section ScriptPentominoesSeveral Placing several pieces
224 *
225 * To generalize the above model to several pieces, we let the
226 * variables range from 0 to n, where n is the number of pieces to
227 * place. Given that we place three pieces, and that the above shown
228 * piece is number one, we will replace each \f$0\f$-expression with
229 * the expression \f$(0|2|3)\f$. Thus, the second regular expression
230 * becomes \f$(0|2|3)^*1(0|2|3)(0|2|3)111(0|2|3)^*\f$. Additionaly,
231 * the end of line marker gets its own value.
232 *
233 * This generalization suffers from the fact that the automata become
234 * much more complex. This problem can be solved by instead
235 * projecting out each component, which gives a new board of
236 * 0/1-variables for each piece to place.
237 *
238 *
239 * \section ScriptPentominoesHeuristic The Branching
240 *
241 * This model does not use any advanced heuristic for the
242 * branching. The variables selection is simply in order, and the
243 * value selection is minimum value first.
244 *
245 * The static value selection allows us to order the pieces in the
246 * specification of the problem. The pieces are approximately ordered by
247 * largness or hardness to place.
248 *
249 *
250 * \section ScriptPentominoesSymmetries Removing board symmetries
251 *
252 * Especially when searching for all solutions of a puzzle instance,
253 * we might want to remove the symmetrical boards from the
254 * solutions-space. This is done using the same symmetry functions as
255 * for the piece symmetries and lexicographical order constraints.
256 *
257 *
258 * \ingroup Example
259 *
260 */
261class Pentominoes : public Script {
262public:
263 /// Choice of propagators
264 enum {
265 PROPAGATION_INT, ///< Use integer propagators
266 PROPAGATION_BOOLEAN, ///< Use Boolean propagators
267 };
268 /// Choice of symmetry breaking
269 enum {
270 SYMMETRY_NONE, ///< Do not remove symmetric solutions
271 SYMMETRY_FULL, ///< Remove symmetric solutions
272 };
273private:
274 /// Specification of the tiles to place.
275 const TileSpec *spec;
276 /// Width and height of the board
277 int width, height;
278 /// Whether the board is filled or not
279 bool filled;
280 /// Number of specifications of tiles to place
281 int nspecs;
282 /// Number of tiles to place
283 int ntiles;
284
285 /// The variables for the board.
286 IntVarArray board;
287
288 /// Compute number of tiles
289 int compute_number_of_tiles(const TileSpec* ts, int nspecs) const {
290 int res = 0;
291 for (int i=0; i<nspecs; i++)
292 res += ts[i].amount;
293 return res;
294 }
295
296 /// Returns the regular expression for placing a specific tile \a
297 /// tile in a specific rotation.
298 REG tile_reg(int twidth, int theight, const char* tile,
299 REG mark, REG other, REG eol) const {
300 REG oe = other | eol;
301 REG res = *oe;
302 REG color[] = {other, mark};
303 for (int h = 0; h < theight; ++h) {
304 for (int w = 0; w < twidth; ++w) {
305 int which = tile[h*twidth + w] == 'X';
306 res += color[which];
307 }
308 if (h < theight-1) {
309 res += oe(width-twidth, width-twidth);
310 }
311 }
312 res += *oe + oe;
313 return res;
314 }
315
316 /// Returns the regular expression for placing tile number \a t in
317 /// any rotation.
318 REG get_constraint(int t, REG mark, REG other, REG eol) {
319 // This should be done for all rotations
320 REG res;
321 char *t2 = new char[width*height];
322 int w2, h2;
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) {
326 syms[i](spec[t].tile, spec[t].width, spec[t].height, t2, w2, h2);
327 res = res | tile_reg(w2, h2, t2, mark, other, eol);
328 }
329 delete [] t2;
330
331 return res;
332 }
333
334
335public:
336 /// Construction of the model.
337 Pentominoes(const SizeOptions& opt)
338 : Script(opt), spec(examples[opt.size()]),
339 width(spec[0].width+1), // Add one for extra row at end.
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) {
345 spec += 1; // No need for the specification-part any longer
346
347 // Set end-of-line markers
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);
352 }
353
354 // Post constraints
355 if (opt.propagation() == PROPAGATION_INT) {
356 int tile = 0;
357 for (int i = 0; i < nspecs; ++i) {
358 for (int j = 0; j < spec[i].amount; ++j) {
359 // Color
360 int col = tile+1;
361 // Expression for color col
362 REG mark(col);
363 // Build expression for complement to color col
364 REG other;
365 bool first = true;
366 for (int j = filled; j <= ntiles; ++j) {
367 if (j == col) continue;
368 if (first) {
369 other = REG(j);
370 first = false;
371 } else {
372 other |= REG(j);
373 }
374 }
375 // End of line marker
376 REG eol(ntiles+1);
377 extensional(*this, board, get_constraint(i, mark, other, eol));
378 ++tile;
379 }
380 }
381 } else { // opt.propagation() == PROPAGATION_BOOLEAN
382 int ncolors = ntiles + 2;
383 // Boolean variables for channeling
384 BoolVarArgs p(*this,ncolors * board.size(),0,1);
385
386 // Post channel constraints
387 for (int i=board.size(); i--; ) {
388 BoolVarArgs c(ncolors);
389 for (int j=ncolors; j--; )
390 c[j]=p[i*ncolors+j];
391 channel(*this, c, board[i]);
392 }
393
394 // For placing tile i, we construct the expression over
395 // 0/1-variables and apply it to the projection of
396 // the board on the color for the tile.
397 REG other(0), mark(1);
398 int tile = 0;
399 for (int i = 0; i < nspecs; ++i) {
400 for (int j = 0; j < spec[i].amount; ++j) {
401 int col = tile+1;
402 // Projection for color col
403 BoolVarArgs c(board.size());
404
405 for (int k = board.size(); k--; ) {
406 c[k] = p[k*ncolors+col];
407 }
408
409 extensional(*this, c, get_constraint(i, mark, other, other));
410 ++tile;
411 }
412 }
413 }
414
415 if (opt.symmetry() == SYMMETRY_FULL) {
416 // Remove symmetrical boards
417 IntVarArgs orig(board.size()-height), symm(board.size()-height);
418 int pos = 0;
419 for (int i = 0; i < board.size(); ++i) {
420 if ((i+1)%width==0) continue;
421 orig[pos++] = board[i];
422 }
423
424 int w2, h2;
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)
430 rel(*this, orig, IRT_LQ, symm);
431 }
432 }
433
434 // Install branching
435 branch(*this, board, INT_VAR_NONE(), INT_VAL_MIN());
436 }
437
438 /// Constructor for cloning \a s
439 Pentominoes(Pentominoes& s) :
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);
443 }
444
445 /// Copy space during cloning
446 virtual Space*
447 copy(void) {
448 return new Pentominoes(*this);
449 }
450
451 /// Print solution
452 virtual void
453 print(std::ostream& os) const {
454 for (int h = 0; h < height; ++h) {
455 os << "\t";
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);
459 os << c;
460 }
461 os << std::endl;
462 }
463 os << std::endl;
464 }
465};
466
467
468/** \brief Main-function
469 * \relates Pentominoes
470 */
471int
472main(int argc, char* argv[]) {
473 SizeOptions opt("Pentominoes");
474 opt.size(1);
475 opt.symmetry(Pentominoes::SYMMETRY_FULL);
476 opt.symmetry(Pentominoes::SYMMETRY_NONE,
477 "none", "do not remove symmetric solutions");
478 opt.symmetry(Pentominoes::SYMMETRY_FULL,
479 "full", "remove symmetric solutions");
480
481 opt.propagation(Pentominoes::PROPAGATION_BOOLEAN);
482 opt.propagation(Pentominoes::PROPAGATION_INT,
483 "int", "use integer propagators");
484 opt.propagation(Pentominoes::PROPAGATION_BOOLEAN,
485 "bool", "use Boolean propagators");
486
487 opt.parse(argc,argv);
488 if (opt.size() >= n_examples) {
489 std::cerr << "Error: size must be between 0 and "
490 << n_examples-1 << std::endl;
491 return 1;
492 }
493 Script::run<Pentominoes,DFS,SizeOptions>(opt);
494 return 0;
495}
496
497
498/** \name Puzzle specifications
499 *
500 * \relates Pentominoes
501 */
502//@{
503/// Small specification
504static const TileSpec puzzle0[] =
505 {
506 // Width and height of board
507 {4, 4, true, ""},
508 {2, 3, 1,
509 "XX"
510 "X "
511 "X "},
512 {2, 1, 1,
513 "XX"},
514 {3, 3, 1,
515 " XX"
516 " X"
517 "XXX"},
518 {1, 1, 1,
519 "X"},
520 {3, 1, 1,
521 "XXX"}
522 };
523/// Standard specification
524static const TileSpec puzzle1[] =
525 {
526 // Width and height of board
527 {8, 8, true, ""},
528 {3, 3, 1,
529 "XXX"
530 "XXX"
531 "XX "},
532 {5, 3, 1,
533 " XXX"
534 " X "
535 "XXX "},
536 {3, 4, 1,
537 "XXX"
538 "XXX"
539 " X"
540 " X"},
541 {3, 4, 1,
542 "XXX"
543 " X"
544 " X"
545 " X"},
546 {2, 5, 1,
547 " X"
548 " X"
549 " X"
550 "XX"
551 "XX"},
552 {4, 2, 1,
553 "XX "
554 "XXXX"},
555 {3, 3, 1,
556 "XXX"
557 " X"
558 " X"},
559 {2, 3, 1,
560 "XX"
561 "X "
562 "X "},
563 {2, 4, 1,
564 "XX"
565 "XX"
566 "XX"
567 "XX"},
568 {3, 2, 1,
569 "XX "
570 "XXX"}
571 };
572
573// Perfect square number 2 from examples/perfect-square.cc
574static const TileSpec square2[] =
575 {
576 // Width and height of board
577 {10, 10, true, ""},
578 {6, 6, 1,
579 "XXXXXX"
580 "XXXXXX"
581 "XXXXXX"
582 "XXXXXX"
583 "XXXXXX"
584 "XXXXXX"
585 },
586 {4, 4, 3,
587 "XXXX"
588 "XXXX"
589 "XXXX"
590 "XXXX"},
591 {2, 2, 4,
592 "XX"
593 "XX"}
594 };
595
596// Perfect square number 3 from examples/perfect-square.cc
597static const TileSpec square3[] =
598 {
599 // Width and height of board
600 {20, 20, true, ""},
601 {9, 9, 1,
602 "XXXXXXXXX"
603 "XXXXXXXXX"
604 "XXXXXXXXX"
605 "XXXXXXXXX"
606 "XXXXXXXXX"
607 "XXXXXXXXX"
608 "XXXXXXXXX"
609 "XXXXXXXXX"
610 "XXXXXXXXX"
611 },
612 {8, 8, 2,
613 "XXXXXXXX"
614 "XXXXXXXX"
615 "XXXXXXXX"
616 "XXXXXXXX"
617 "XXXXXXXX"
618 "XXXXXXXX"
619 "XXXXXXXX"
620 "XXXXXXXX"
621 },
622 {7, 7, 1,
623 "XXXXXXX"
624 "XXXXXXX"
625 "XXXXXXX"
626 "XXXXXXX"
627 "XXXXXXX"
628 "XXXXXXX"
629 "XXXXXXX"
630 },
631 {5, 5, 1,
632 "XXXXX"
633 "XXXXX"
634 "XXXXX"
635 "XXXXX"
636 "XXXXX"
637 },
638 {4, 4, 5,
639 "XXXX"
640 "XXXX"
641 "XXXX"
642 "XXXX"},
643 {3, 3, 3,
644 "XXX"
645 "XXX"
646 "XXX"},
647 {2, 2, 2,
648 "XX"
649 "XX"},
650 {1, 1, 2,
651 "X"}
652 };
653
654static const TileSpec pentomino6x10[] =
655 {
656 // Width and height of board
657 {10, 6, true, ""},
658 {2, 4, 1,
659 "X "
660 "X "
661 "X "
662 "XX"},
663 {3,3, 1,
664 "XX "
665 " XX"
666 " X "},
667 {3,3, 1,
668 "XXX"
669 " X "
670 " X "},
671 {3,3, 1,
672 " X"
673 " XX"
674 "XX "},
675 {2,4, 1,
676 " X"
677 "XX"
678 " X"
679 " X"},
680 {5,1, 1,
681 "XXXXX"},
682 {3,3, 1,
683 "X "
684 "XXX"
685 " X"},
686 {4,2, 1,
687 " XXX"
688 "XX "},
689 {2,3, 1,
690 "XX"
691 "XX"
692 " X"},
693 {3,2, 1,
694 "X X"
695 "XXX"},
696 {3,3, 1,
697 " X "
698 "XXX"
699 " X "},
700 {3,3, 1,
701 " X"
702 " X"
703 "XXX"}
704 };
705
706static const TileSpec pentomino5x12[] =
707 {
708 // Width and height of board
709 {12, 5, true, ""},
710 {2, 4, 1,
711 "X "
712 "X "
713 "X "
714 "XX"},
715 {3,3, 1,
716 "XX "
717 " XX"
718 " X "},
719 {3,3, 1,
720 "XXX"
721 " X "
722 " X "},
723 {3,3, 1,
724 " X"
725 " XX"
726 "XX "},
727 {2,4, 1,
728 " X"
729 "XX"
730 " X"
731 " X"},
732 {5,1, 1,
733 "XXXXX"},
734 {3,3, 1,
735 "X "
736 "XXX"
737 " X"},
738 {4,2, 1,
739 " XXX"
740 "XX "},
741 {2,3, 1,
742 "XX"
743 "XX"
744 " X"},
745 {3,2, 1,
746 "X X"
747 "XXX"},
748 {3,3, 1,
749 " X "
750 "XXX"
751 " X "},
752 {3,3, 1,
753 " X"
754 " X"
755 "XXX"}
756 };
757
758static const TileSpec pentomino4x15[] =
759 {
760 // Width and height of board
761 {15, 4, true, ""},
762 {2, 4, 1,
763 "X "
764 "X "
765 "X "
766 "XX"},
767 {3,3, 1,
768 "XX "
769 " XX"
770 " X "},
771 {3,3, 1,
772 "XXX"
773 " X "
774 " X "},
775 {3,3, 1,
776 " X"
777 " XX"
778 "XX "},
779 {2,4, 1,
780 " X"
781 "XX"
782 " X"
783 " X"},
784 {5,1, 1,
785 "XXXXX"},
786 {3,3, 1,
787 "X "
788 "XXX"
789 " X"},
790 {4,2, 1,
791 " XXX"
792 "XX "},
793 {2,3, 1,
794 "XX"
795 "XX"
796 " X"},
797 {3,2, 1,
798 "X X"
799 "XXX"},
800 {3,3, 1,
801 " X "
802 "XXX"
803 " X "},
804 {3,3, 1,
805 " X"
806 " X"
807 "XXX"}
808 };
809
810static const TileSpec pentomino3x20[] =
811 {
812 // Width and height of board
813 {20, 3, true, ""},
814 {2, 4, 1,
815 "X "
816 "X "
817 "X "
818 "XX"},
819 {3,3, 1,
820 "XX "
821 " XX"
822 " X "},
823 {3,3, 1,
824 "XXX"
825 " X "
826 " X "},
827 {3,3, 1,
828 " X"
829 " XX"
830 "XX "},
831 {2,4, 1,
832 " X"
833 "XX"
834 " X"
835 " X"},
836 {5,1, 1,
837 "XXXXX"},
838 {3,3, 1,
839 "X "
840 "XXX"
841 " X"},
842 {4,2, 1,
843 " XXX"
844 "XX "},
845 {2,3, 1,
846 "XX"
847 "XX"
848 " X"},
849 {3,2, 1,
850 "X X"
851 "XXX"},
852 {3,3, 1,
853 " X "
854 "XXX"
855 " X "},
856 {3,3, 1,
857 " X"
858 " X"
859 "XXX"}
860 };
861
862/// List of specifications
863const TileSpec *examples[] = {puzzle0, puzzle1, square2, square3,
864 pentomino6x10,pentomino5x12,
865 pentomino4x15,pentomino3x20};
866const int examples_size[] = {sizeof(puzzle0)/sizeof(TileSpec),
867 sizeof(puzzle1)/sizeof(TileSpec),
868 sizeof(square2)/sizeof(TileSpec),
869 sizeof(square3)/sizeof(TileSpec),
870 sizeof(pentomino6x10)/sizeof(TileSpec),
871 sizeof(pentomino5x12)/sizeof(TileSpec),
872 sizeof(pentomino4x15)/sizeof(TileSpec),
873 sizeof(pentomino3x20)/sizeof(TileSpec)};
874
875/// Number of specifications
876const unsigned n_examples = sizeof(examples)/sizeof(TileSpec*);
877//@}
878
879// Symmetry functions
880namespace {
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;
886 }
887 return h * w1 + w;
888 }
889 template<class CArray, class Array>
890 void id(CArray t1, int w1, int h1, Array t2, int& w2, int&h2) {
891 w2 = w1; h2 = h1;
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)];
895 }
896 template<class CArray, class Array>
897 void rot90(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
898 w2 = h1; h2 = w1;
899 for (int h = 0; h < h1; ++h)
900 for (int w = 0; w < w1; ++w)
901 t2[pos(w, w2-h-1, h2, w2)] = t1[pos(h, w, h1, w1)];
902 }
903 template<class CArray, class Array>
904 void rot180(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
905 w2 = w1; h2 = h1;
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)];
909 }
910 template<class CArray, class Array>
911 void rot270(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
912 w2 = h1; h2 = w1;
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)];
916 }
917 template<class CArray, class Array>
918 void flipx(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
919 w2 = w1; h2 = h1;
920 for (int h = 0; h < h1; ++h)
921 for (int w = 0; w < w1; ++w)
922 t2[pos(h, w2-w-1, h2, w2)] = t1[pos(h, w, h1, w1)];
923 }
924 template<class CArray, class Array>
925 void flipy(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
926 w2 = w1; h2 = h1;
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)];
930 }
931 template<class CArray, class Array>
932 void flipd1(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
933 w2 = h1; h2 = w1;
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)];
937 }
938 template<class CArray, class Array>
939 void flipd2(CArray t1, int w1, int h1, Array t2, int& w2, int& h2) {
940 w2 = h1; h2 = w1;
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)];
944 }
945}
946
947// STATISTICS: example-any