1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* polyominoes --- Shows attempts to place polyominoes into a rectangle */
5 static const char sccsid[] = "@(#)polyominoes.c 5.01 2000/12/18 xlockmore";
9 * Copyright (c) 2000 by Stephen Montgomery-Smith <stephen@math.missouri.edu>
11 * Permission to use, copy, modify, and distribute this software and its
12 * documentation for any purpose and without fee is hereby granted,
13 * provided that the above copyright notice appear in all copies and that
14 * both that copyright notice and this permission notice appear in
15 * supporting documentation.
17 * This file is provided AS IS with no warranties of any kind. The author
18 * shall have no liability with respect to the infringement of copyrights,
19 * trade secrets or any patents by this file or any part thereof. In no
20 * event will the author be liable for any lost revenue or profits or
21 * other special, indirect and consequential damages.
24 * 07-Jan-2001: Made improvement to the search algorithm for the puzzles
25 * involving identical polyominoes (via the variable
26 * reason_to_not_attach). By Stephen Montgomery-Smith.
27 * 20-Dec-2000: Added more puzzles at David Bagley's request.
28 * 27-Nov-2000: Adapted from euler2d.c Copyright (c) 2000 by Stephen
30 * 05-Jun-2000: Adapted from flow.c Copyright (c) 1996 by Tim Auckland
31 * 18-Jul-1996: Adapted from swarm.c Copyright (c) 1991 by Patrick J. Naughton.
32 * 31-Aug-1990: Adapted from xswarm by Jeff Butterworth. (butterwo@ncsc.org)
36 # define MODE_polyominoes
37 #define DEFAULTS "*delay: 10000 \n" \
40 "*fpsSolid: true \n" \
42 # define polyominoes_handle_event 0
43 # define SMOOTH_COLORS
44 # include "xlockmore.h" /* in xscreensaver distribution */
46 #else /* STANDALONE */
47 # include "xlock.h" /* in xlockmore distribution */
48 #endif /* STANDALONE */
50 #ifdef MODE_polyominoes
51 #define DEF_IDENTICAL "False"
52 #define DEF_PLAIN "False"
54 static Bool identical;
58 #define countof(x) (sizeof((x))/sizeof((*x)))
60 static XrmOptionDescRec opts[] =
62 {"-identical", ".polyominoes.identical", XrmoptionNoArg, "on"},
63 {"+identical", ".polyominoes.identical", XrmoptionNoArg, "off"},
64 {"-plain", ".polyominoes.plain", XrmoptionNoArg, "on"},
65 {"+plain", ".polyominoes.plain", XrmoptionNoArg, "off"}
67 static argtype vars[] =
69 {&identical, "identical", "Identical", DEF_IDENTICAL, t_Bool},
70 {&plain, "plain", "Plain", DEF_PLAIN, t_Bool}
72 static OptionStruct desc[] =
74 {"-/+identical", "turn on/off puzzles where the polyomino pieces are identical"},
75 {"-/+plain", "turn on/off plain pieces"}
78 ENTRYPOINT ModeSpecOpt polyominoes_opts =
79 {sizeof opts / sizeof opts[0], opts,
80 sizeof vars / sizeof vars[0], vars, desc};
83 ModStruct polyominoes_description = {
84 "polyominoes", "init_polyominoes", "draw_polyominoes", "release_polyominoes",
85 "refresh_polyominoes", "init_polyominoes", (char *) NULL, &polyominoes_opts,
86 6000, 1, 8192, 1, 64, 1.0, "",
87 "Shows attempts to place polyominoes into a rectangle", 0, NULL
92 /* Each polyomino is described by several quantities:
93 len: the number of squares in the polyomino;
94 point: the list of points;
95 tranform_len: the number of items in transform_list;
96 transform_list: a list of transformations that need to be done in order
97 to get all rotations and reflections (see the function
99 max_white: the maximum number of white squares covered if polyomino
100 is placed on a chess board;
101 color: it's display color;
102 attached: whether it is currently attached to the rectangle;
103 attach_point: point on rectangle where attached;
104 point_no: the number of the point where it is attached;
105 transform_index: which element of transform_list is currently being used.
108 typedef struct {int x,y;} point_type;
110 typedef struct {int len; point_type *point;
111 int transform_len, transform_list[8], max_white;
114 point_type attach_point;
115 int point_no, transform_index;} polyomino_type;
118 typedef struct _polyominoesstruct{
122 unsigned border_color;
125 polyomino_type *polyomino;
127 Bool identical, use3D;
131 /* The array that tells where the polyominoes are attached. */
132 int *array, *changed_array;
134 /* These specify the dimensions of how things appear on the screen. */
135 int box, x_margin, y_margin;
137 /* These booleans decide in which way to try to attach the polyominoes. */
138 int left_right, top_bottom;
140 /* Bitmaps for display purposes. */
142 XImage *bitmaps[256];
144 /* Structures used for display purposes if there is not enough memory
145 to allocate bitmaps (or if the screen is small). */
147 XRectangle *rectangles;
149 /* A procedure that may be used to see if certain configurations
151 int (*check_ok)(struct _polyominoesstruct *sp);
153 /* Tells program that solutions are invariant under 180 degree
157 /* This is a variable used in the case that all the polyominoes are identical
158 that will further prune the search tree. Essentially it will be
159 int reason_to_not_attach[nr_polynominoes][nr_polynominoes];
160 Let me first explain the effect it is trying to overcome. Often
161 in the search process, the computer will first try to fit shapes into
162 a region (call it A), and then into another region (call it B) that is
163 essentially disjoint from A. But it may be that it just is not possible
164 to fit shapes into region B. So it fits something into A, and then
165 tries to fit something into B. Failing it fits something else into A,
166 and then tried again to fit something into B. Thus the program is trying
167 again and again to fit something into B, when it should have figured out
168 the first time that it was impossible.
170 To overcome this, everytime we try to attach a piece, we collect the reasons
171 why it cannot be attached (a boolean for each piece that got in the way).
172 If we see that a piece cannot be attached, we detach the other pieces until
173 we have detached at least one piece for which the boolean reason_to_not_attach
176 int *reason_to_not_attach;
181 eraser_state *eraser;
185 #define ARRAY(x,y) (sp->array[(x)*sp->height+(y)])
186 #define CHANGED_ARRAY(x,y) (sp->changed_array[(x)*sp->height+(y)])
187 #define ARRAY_P(p) (sp->array[(p).x*sp->height+(p).y])
188 #define CHANGED_ARRAY_P(p) (sp->changed_array[(p).x*sp->height+(p).y])
189 #define ARR(x,y) (((x)<0||(x)>=sp->width||(y)<0||(y)>=sp->height)?-2:ARRAY(x,y))
191 #define REASON_TO_NOT_ATTACH(x,y) (sp->reason_to_not_attach[(x)*sp->nr_polyominoes+(y)])
193 #define ROUND8(n) ((((n)+7)/8)*8)
195 /* Defines to index the bitmaps. A set bit indicates that an edge or
196 corner is required. */
201 #define LEFT_UP (1<<4)
202 #define LEFT_DOWN (1<<5)
203 #define RIGHT_UP (1<<6)
204 #define RIGHT_DOWN (1<<7)
205 #define IS_LEFT(n) ((n) & LEFT)
206 #define IS_RIGHT(n) ((n) & RIGHT)
207 #define IS_UP(n) ((n) & UP)
208 #define IS_DOWN(n) ((n) & DOWN)
209 #define IS_LEFT_UP(n) ((n) & LEFT_UP)
210 #define IS_LEFT_DOWN(n) ((n) & LEFT_DOWN)
211 #define IS_RIGHT_UP(n) ((n) & RIGHT_UP)
212 #define IS_RIGHT_DOWN(n) ((n) & RIGHT_DOWN)
214 /* Defines to access the bitmaps. */
215 #define BITNO(x,y) ((x)+(y)*ROUND8(sp->box))
216 #define SETBIT(n,x,y) {data[BITNO(x,y)/8] |= 1<<(BITNO(x,y)%8);}
217 #define RESBIT(n,x,y) {data[BITNO(x,y)/8] &= ~(1<<(BITNO(x,y)%8));}
218 #define TWOTHIRDSBIT(n,x,y) {if ((x+y-1)%3) SETBIT(n,x,y) else RESBIT(n,x,y)}
219 #define HALFBIT(n,x,y) {if ((x-y)%2) SETBIT(n,x,y) else RESBIT(n,x,y)}
220 #define THIRDBIT(n,x,y) {if (!((x-y-1)%3)) SETBIT(n,x,y) else RESBIT(n,x,y)}
221 #define THREEQUARTERSBIT(n,x,y) \
222 {if ((y%2)||((x+2+y/2+1)%2)) SETBIT(n,x,y) else RESBIT(n,x,y)}
223 #define NOTHALFBIT(n,x,y) {if ((x-y)%2) RESBIT(n,x,y) else SETBIT(n,x,y)}
225 /* Parameters for bitmaps. */
226 #define G ((sp->box/45)+1) /* 1/2 of gap between polyominoes. */
227 #define T ((sp->box<=12)?1:(G*2)) /* Thickness of walls of polyominoes. */
228 #define R ((sp->box<=12)?1:(G*6)) /* Amount of rounding. */
229 #define RT ((sp->box<=12)?1:(G*3)) /* Thickness of wall of rounded parts.
230 Here 3 is an approximation to 2 sqrt(2). */
231 #define RR 0 /* Roof ridge thickness */
234 /* A list of those bitmaps we need to create to display any pentomino. */
235 /* (not used right now because it does not seem to work for hexonimoes.) */
237 static int bitmaps_needed[] =
239 LEFT_UP|LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
241 LEFT|RIGHT_UP|RIGHT_DOWN,
242 RIGHT|LEFT_UP|LEFT_DOWN,
243 UP|LEFT_DOWN|RIGHT_DOWN,
244 DOWN|LEFT_UP|RIGHT_UP,
254 /* These needed for hexonimoes*/
259 LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
260 LEFT_UP|RIGHT_UP|RIGHT_DOWN,
261 LEFT_UP|LEFT_DOWN|RIGHT_DOWN,
262 LEFT_UP|LEFT_DOWN|RIGHT_UP,
284 static int bitmap_needed(int n)
288 for (i=0;bitmaps_needed[i]!=-1;i++)
289 if (n == bitmaps_needed[i])
296 /* Some debugging routines.
298 static void print_board(polyominoesstruct *sp)
301 for (y=0;y<sp->height;y++) {
302 for (x=0;x<sp->width;x++)
303 if (ARRAY(x,y) == -1)
306 fprintf(stderr,"%c",'a'+ARRAY(x,y));
307 fprintf(stderr,"\n");
309 fprintf(stderr,"\n");
312 static void print_points(point_type *point, int len)
317 fprintf(stderr,"(%d %d) ",point[i].x,point[i].y);
320 static void print_polyomino(polyomino_type poly)
324 print_points(poly.point,poly.len);
325 fprintf(stderr,"\n");
326 for (i=0;i<poly.transform_len;i++)
327 fprintf(stderr,"%d ",poly.transform_list[i]);
328 fprintf(stderr,"\n");
332 static polyominoesstruct *polyominoeses = (polyominoesstruct *) NULL;
335 void random_permutation(int n, int a[])
339 for (i=0;i<n;i++) a[i] = -1;
353 /************************************************************
354 These are the routines for manipulating the polyominoes and
355 attaching and detaching them from the rectangle.
356 ************************************************************/
358 static void transform(point_type in, point_type offset, int transform_no,
359 point_type attach_point, point_type *out) {
360 switch (transform_no) {
361 case 0: out->x=in.x-offset.x+attach_point.x;
362 out->y=in.y-offset.y+attach_point.y;
364 case 1: out->x=-(in.y-offset.y)+attach_point.x;
365 out->y=in.x-offset.x+attach_point.y;
367 case 2: out->x=-(in.x-offset.x)+attach_point.x;
368 out->y=-(in.y-offset.y)+attach_point.y;
370 case 3: out->x=in.y-offset.y+attach_point.x;
371 out->y=-(in.x-offset.x)+attach_point.y;
373 case 4: out->x=-(in.x-offset.x)+attach_point.x;
374 out->y=in.y-offset.y+attach_point.y;
376 case 5: out->x=in.y-offset.y+attach_point.x;
377 out->y=in.x-offset.x+attach_point.y;
379 case 6: out->x=in.x-offset.x+attach_point.x;
380 out->y=-(in.y-offset.y)+attach_point.y;
382 case 7: out->x=-(in.y-offset.y)+attach_point.x;
383 out->y=-(in.x-offset.x)+attach_point.y;
388 static int first_poly_no(polyominoesstruct *sp)
393 while(poly_no<sp->nr_polyominoes && sp->polyomino[poly_no].attached)
398 static void next_poly_no(polyominoesstruct *sp, int *poly_no)
402 *poly_no = sp->nr_polyominoes;
406 } while (*poly_no<sp->nr_polyominoes && sp->polyomino[*poly_no].attached);
410 /* check_all_regions_multiple_of looks for connected regions of
411 blank spaces, and returns 0 if it finds a connected region containing
412 a number of blanks that is not a multiple of n.
415 static void count_adjacent_blanks(polyominoesstruct *sp, int *count, int x, int y, int blank_mark)
418 if (ARRAY(x,y) == -1) {
420 ARRAY(x,y) = blank_mark;
421 if (x>=1) count_adjacent_blanks(sp, count,x-1,y,blank_mark);
422 if (x<sp->width-1) count_adjacent_blanks(sp, count,x+1,y,blank_mark);
423 if (y>=1) count_adjacent_blanks(sp, count,x,y-1,blank_mark);
424 if (y<sp->height-1) count_adjacent_blanks(sp, count,x,y+1,blank_mark);
428 static int check_all_regions_multiple_of(polyominoesstruct *sp, int n)
430 int x,y,count,good = 1;
432 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
434 count_adjacent_blanks(sp, &count,x,y,-2);
438 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
439 if (ARRAY(x,y) == -2)
445 static int check_all_regions_positive_combination_of(polyominoesstruct *sp, int m, int n)
447 int x,y,count,good = 1;
449 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
451 count_adjacent_blanks(sp, &count,x,y,-2);
453 for (;count>=0 && !good;count-=m)
457 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
458 if (ARRAY(x,y) == -2)
464 static int find_smallest_blank_component(polyominoesstruct *sp)
466 int x,y,size,smallest_size,blank_mark,smallest_mark;
468 smallest_mark = blank_mark = -10;
469 smallest_size = 1000000000;
470 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y) == -1) {
472 count_adjacent_blanks(sp, &size,x,y,blank_mark);
473 if (size<smallest_size) {
474 smallest_mark = blank_mark;
475 smallest_size = size;
480 return smallest_mark;
483 /* "Chess board" check - see init_max_whites_list above for more details.
485 /* If the rectangle is alternatively covered by white and black
486 squares (chess board style), then this gives the list of
487 the maximal possible whites covered by each polyomino. It
488 is used by the function whites_ok which makes sure that the
489 array has a valid number of white or black remaining blanks left.
492 static int whites_ok(polyominoesstruct *sp)
494 int x,y,poly_no,whites=0,blacks=0,max_white=0,min_white=0;
496 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
497 if (ARRAY(x,y) == -1 && (x+y)%2) whites++;
498 if (ARRAY(x,y) == -1 && (x+y+1)%2) blacks++;
500 for (poly_no=0;poly_no<sp->nr_polyominoes;poly_no++) if (!sp->polyomino[poly_no].attached) {
501 max_white += sp->polyomino[poly_no].max_white;
502 min_white += sp->polyomino[poly_no].len - sp->polyomino[poly_no].max_white;
504 return (min_white <= blacks && min_white <= whites
505 && blacks <= max_white && whites <= max_white);
508 /* This routine looks at the point (x,y) and sees how many polyominoes
509 and all their various transforms may be attached there.
513 score_point(polyominoesstruct *sp, int x, int y, int min_score_so_far)
515 int poly_no, point_no, transform_index, i, attachable;
516 point_type attach_point, target_point;
519 if (x>=1 && x<sp->width-1 && y>=1 && y<sp->height-1 &&
520 ARRAY(x-1,y-1)<0 && ARRAY(x-1,y)<0 && ARRAY(x-1,y+1)<0 &&
521 ARRAY(x+1,y-1)<0 && ARRAY(x+1,y)<0 && ARRAY(x+1,y+1)<0 &&
522 ARRAY(x,y-1)<0 && ARRAY(x,y+1)<0)
527 for (poly_no=first_poly_no(sp);poly_no<sp->nr_polyominoes;next_poly_no(sp,&poly_no))
528 if (!sp->polyomino[poly_no].attached) {
529 for (point_no=0;point_no<sp->polyomino[poly_no].len;point_no++)
530 for (transform_index=0;transform_index<sp->polyomino[poly_no].transform_len;transform_index++) {
532 for (i=0;i<sp->polyomino[poly_no].len;i++) {
533 transform(sp->polyomino[poly_no].point[i],
534 sp->polyomino[poly_no].point[point_no],
535 sp->polyomino[poly_no].transform_list[transform_index],
536 attach_point, &target_point);
537 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
538 && (target_point.y>=0) && (target_point.y<sp->height)
539 && (ARRAY_P(target_point)<0))) {
546 if (score>=min_score_so_far)
555 static void find_blank(polyominoesstruct *sp, point_type *point)
557 int score, worst_score;
561 blank_mark = find_smallest_blank_component(sp);
563 worst_score = 1000000;
564 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y)==blank_mark) {
565 score = 100*score_point(sp,x,y,worst_score);
567 if (sp->left_right) score += 10*x;
568 else score += 10*(sp->width-1-x);
569 if (sp->top_bottom) score += y;
570 else score += (sp->height-1-y);
572 if (score<worst_score) {
579 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
580 if (ARRAY(x,y)<0) ARRAY(x,y) = -1;
583 /* Detaches the most recently attached polyomino. */
586 void detach(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index, point_type *attach_point, int rot180)
589 point_type target_point;
591 if (sp->nr_attached == 0) return;
593 *poly_no = sp->attach_list[sp->nr_attached];
594 *point_no = sp->polyomino[*poly_no].point_no;
595 *transform_index = sp->polyomino[*poly_no].transform_index;
596 *attach_point = sp->polyomino[*poly_no].attach_point;
597 for (i=0;i<sp->polyomino[*poly_no].len;i++) {
598 transform(sp->polyomino[*poly_no].point[i],
599 sp->polyomino[*poly_no].point[*point_no],
600 sp->polyomino[*poly_no].transform_list[*transform_index]^(rot180<<1),
601 *attach_point, &target_point);
602 ARRAY_P(target_point) = -1;
603 CHANGED_ARRAY_P(target_point) = 1;
606 sp->polyomino[*poly_no].attached = 0;
609 /* Attempts to attach a polyomino at point (x,y) at the
610 point_no-th point of that polyomino, using the transform
611 transform_no. Returns 1 if successful.
615 int attach(polyominoesstruct *sp, int poly_no, int point_no, int transform_index, point_type attach_point, int rot180,
616 int *reason_to_not_attach) {
617 point_type target_point;
619 int attachable = 1, worst_reason_not_to_attach = 1000000000;
622 attach_point.x = sp->width-1-attach_point.x;
623 attach_point.y = sp->height-1-attach_point.y;
626 if (sp->polyomino[poly_no].attached)
629 for (i=0;i<sp->polyomino[poly_no].len;i++) {
630 transform(sp->polyomino[poly_no].point[i],
631 sp->polyomino[poly_no].point[point_no],
632 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
633 attach_point, &target_point);
634 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
635 && (target_point.y>=0) && (target_point.y<sp->height)
636 && (ARRAY_P(target_point) == -1))) {
639 if ((target_point.x>=0) && (target_point.x<sp->width)
640 && (target_point.y>=0) && (target_point.y<sp->height)
641 && (ARRAY_P(target_point) >= 0)
642 && (ARRAY_P(target_point)<worst_reason_not_to_attach))
643 worst_reason_not_to_attach = ARRAY_P(target_point);
650 if (sp->identical && !attachable) {
651 if (worst_reason_not_to_attach < 1000000000)
652 reason_to_not_attach[worst_reason_not_to_attach] = 1;
656 for (i=0;i<sp->polyomino[poly_no].len;i++) {
657 transform(sp->polyomino[poly_no].point[i],
658 sp->polyomino[poly_no].point[point_no],
659 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
660 attach_point, &target_point);
661 ARRAY_P(target_point) = poly_no;
662 CHANGED_ARRAY_P(target_point) = 1;
665 sp->attach_list[sp->nr_attached] = poly_no;
668 sp->polyomino[poly_no].attached = 1;
669 sp->polyomino[poly_no].point_no = point_no;
670 sp->polyomino[poly_no].attach_point = attach_point;
671 sp->polyomino[poly_no].transform_index = transform_index;
673 if (!sp->check_ok(sp)) {
674 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,rot180);
682 int next_attach_try(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index)
685 (*transform_index)++;
686 if (*transform_index>=sp->polyomino[*poly_no].transform_len) {
687 *transform_index = 0;
689 if (*point_no>=sp->polyomino[*poly_no].len) {
691 next_poly_no(sp,poly_no);
692 if (*poly_no>=sp->nr_polyominoes) {
693 *poly_no = first_poly_no(sp);
702 /*******************************************************
704 *******************************************************/
707 draw_without_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
709 Display *display = MI_DISPLAY(mi);
710 Window window = MI_WINDOW(mi);
712 int x,y,poly_no,nr_lines,nr_rectangles;
714 XSetLineAttributes(display,gc,sp->box/10+1,LineSolid,CapRound,JoinRound);
716 for (poly_no=-1;poly_no<sp->nr_polyominoes;poly_no++) {
718 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
719 if (CHANGED_ARRAY(x,y) && ARRAY(x,y) == poly_no) {
720 sp->rectangles[nr_rectangles].x = sp->x_margin + sp->box*x;
721 sp->rectangles[nr_rectangles].y = sp->y_margin + sp->box*y;
722 sp->rectangles[nr_rectangles].width = sp->box;
723 sp->rectangles[nr_rectangles].height = sp->box;
727 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
729 XSetForeground(display, gc, sp->polyomino[poly_no].color);
730 XFillRectangles(display, window, gc, sp->rectangles, nr_rectangles);
733 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
736 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
737 if (ARRAY(x,y) == -1 && ARRAY(x+1,y) == -1
738 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x+1,y))) {
739 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
740 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
741 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
742 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
746 XDrawSegments(display, window, gc, sp->lines, nr_lines);
749 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
750 if (ARRAY(x,y) == -1 && ARRAY(x,y+1) == -1
751 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x,y+1))) {
752 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
753 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
754 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
755 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
759 XDrawSegments(display, window, gc, sp->lines, nr_lines);
761 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
762 XDrawRectangle(display, window, gc, sp->x_margin, sp->y_margin, sp->box*sp->width, sp->box*sp->height);
764 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
767 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
768 if (ARRAY(x+1,y) != ARRAY(x,y)) {
769 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
770 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
771 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
772 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
776 XDrawSegments(display, window, gc, sp->lines, nr_lines);
779 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
780 if (ARRAY(x,y+1) != ARRAY(x,y)) {
781 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
782 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
783 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
784 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
788 XDrawSegments(display, window, gc, sp->lines, nr_lines);
789 XSetLineAttributes(display,gc,1,LineSolid,CapRound,JoinRound);
792 static void create_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
797 for (n=0;n<countof(sp->bitmaps);n++) {
799 /* Avoid duplication of identical bitmaps. */
800 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
801 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_UP];
802 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
803 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_DOWN];
804 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
805 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_UP];
806 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
807 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_DOWN];
809 else /* if (bitmap_needed(n)) */ {
810 data = (char *) malloc(sizeof(char)*(sp->box*ROUND8(sp->box)/8));
816 for (y=0;y<sp->box;y++) for (x=0;x<sp->box;x++) {
818 #ifdef SMALL_BELLYBUTTON
819 if (x >= sp->box / 2 && x <= sp->box / 2 + 1 &&
820 y >= sp->box / 2 && y <= sp->box / 2 + 1)
825 } else if ((x>=y && x<=sp->box-y-1 && IS_UP(n))
826 || (x<=y && x<=sp->box-y-1 && y<sp->box/2 && !IS_LEFT(n))
827 || (x>=y && x>=sp->box-y-1 && y<sp->box/2 && !IS_RIGHT(n)))
829 else if ((x<=y && x<=sp->box-y-1 && IS_LEFT(n))
830 || (x>=y && x<=sp->box-y-1 && x<sp->box/2 && !IS_UP(n))
831 || (x<=y && x>=sp->box-y-1 && x<sp->box/2 && !IS_DOWN(n)))
833 else if ((x>=y && x>=sp->box-y-1 && IS_RIGHT(n))
834 || (x>=y && x<=sp->box-y-1 && x>=sp->box/2 && !IS_UP(n))
835 || (x<=y && x>=sp->box-y-1 && x>=sp->box/2 && !IS_DOWN(n)))
837 else if ((x<=y && x>=sp->box-y-1 && IS_DOWN(n))
838 || (x<=y && x<=sp->box-y-1 && y>=sp->box/2 && !IS_LEFT(n))
839 || (x>=y && x>=sp->box-y-1 && y>=sp->box/2 && !IS_RIGHT(n)))
844 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
847 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
848 SETBIT(n,sp->box-1-x,y)
850 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
853 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
854 SETBIT(n,x,sp->box-1-y)
856 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
859 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
860 RESBIT(n,sp->box-1-x,y)
862 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
865 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
866 RESBIT(n,x,sp->box-1-y)
868 if (IS_LEFT(n) && IS_UP(n))
870 for (y=G;y<=R+2*G-x;y++) {
876 if (IS_LEFT(n) && IS_DOWN(n))
878 for (y=G;y<=R+2*G-x;y++) {
880 SETBIT(n,x,sp->box-1-y)
882 RESBIT(n,x,sp->box-1-y)
884 if (IS_RIGHT(n) && IS_UP(n))
886 for (y=G;y<=R+2*G-x;y++) {
888 SETBIT(n,sp->box-1-x,y)
890 RESBIT(n,sp->box-1-x,y)
892 if (IS_RIGHT(n) && IS_DOWN(n))
894 for (y=G;y<=R+2*G-x;y++) {
896 SETBIT(n,sp->box-1-x,sp->box-1-y)
898 RESBIT(n,sp->box-1-x,sp->box-1-y)
901 if (!IS_LEFT(n) && !IS_UP(n) && IS_LEFT_UP(n)) {
902 for (x=0;x<G;x++) for(y=0;y<G;y++)
904 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
906 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
909 if (!IS_LEFT(n) && !IS_DOWN(n) && IS_LEFT_DOWN(n)) {
910 for (x=0;x<G;x++) for(y=0;y<G;y++)
911 RESBIT(n,x,sp->box-1-y)
912 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
913 SETBIT(n,x,sp->box-1-y)
914 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
915 SETBIT(n,x,sp->box-1-y)
917 if (!IS_RIGHT(n) && !IS_UP(n) && IS_RIGHT_UP(n)) {
918 for (x=0;x<G;x++) for(y=0;y<G;y++)
919 RESBIT(n,sp->box-1-x,y)
920 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
921 SETBIT(n,sp->box-1-x,y)
922 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
923 SETBIT(n,sp->box-1-x,y)
925 if (!IS_RIGHT(n) && !IS_DOWN(n) && IS_RIGHT_DOWN(n)) {
926 for (x=0;x<G;x++) for(y=0;y<G;y++)
927 RESBIT(n,sp->box-1-x,sp->box-1-y)
928 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
929 SETBIT(n,sp->box-1-x,sp->box-1-y)
930 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
931 SETBIT(n,sp->box-1-x,sp->box-1-y)
934 #ifdef LARGE_BELLYBUTTON
936 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
937 for (x=0;x<G+T;x++) for(y=0;y<G+T;y++)
939 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
940 for (x=0;x<G+T;x++) for(y=sp->box-G-T;y<sp->box;y++)
942 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
943 for (x=sp->box-G-T;x<sp->box;x++) for(y=0;y<G+T;y++)
945 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
946 for (x=sp->box-G-T;x<sp->box;x++) for(y=sp->box-G-T;y<sp->box;y++)
953 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
954 for (x=0;x<sp->box/2-RR;x++) for(y=0;y<sp->box/2-RR;y++)
955 THREEQUARTERSBIT(n,x,y)
956 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
957 for (x=0;x<sp->box/2-RR;x++) for(y=sp->box/2+RR;y<sp->box;y++)
958 THREEQUARTERSBIT(n,x,y)
959 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
960 for (x=sp->box/2+RR;x<sp->box;x++) for(y=0;y<sp->box/2-RR;y++)
961 THREEQUARTERSBIT(n,x,y)
962 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
963 for (x=sp->box/2+RR;x<sp->box;x++) for(y=sp->box/2+RR;y<sp->box;y++)
964 THREEQUARTERSBIT(n,x,y)
967 sp->bitmaps[n] = XCreateImage(MI_DISPLAY(mi), MI_VISUAL(mi), 1, XYBitmap,
968 0, data, sp->box, sp->box, 8, 0);
969 if (sp->bitmaps[n] == None) {
974 sp->bitmaps[n]->byte_order = MSBFirst;
975 sp->bitmaps[n]->bitmap_unit = 8;
976 sp->bitmaps[n]->bitmap_bit_order = LSBFirst;
983 static void draw_with_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
985 Display *display = MI_DISPLAY(mi);
986 Window window = MI_WINDOW(mi);
988 int x,y,t,bitmap_index;
990 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
991 if (ARRAY(x,y) == -1) {
992 if (CHANGED_ARRAY(x,y)) {
993 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
994 XFillRectangle(display,window,gc,
995 sp->x_margin + sp->box*x,
996 sp->y_margin + sp->box*y,
1001 XSetForeground(display, gc, sp->polyomino[ARRAY(x,y)].color);
1003 if (ARR(x,y) != ARR(x-1,y)) bitmap_index |= LEFT;
1004 if (ARR(x,y) != ARR(x+1,y)) bitmap_index |= RIGHT;
1005 if (ARR(x,y) != ARR(x,y-1)) bitmap_index |= UP;
1006 if (ARR(x,y) != ARR(x,y+1)) bitmap_index |= DOWN;
1007 if (ARR(x,y) != ARR(x-1,y-1)) bitmap_index |= LEFT_UP;
1008 if (ARR(x,y) != ARR(x-1,y+1)) bitmap_index |= LEFT_DOWN;
1009 if (ARR(x,y) != ARR(x+1,y-1)) bitmap_index |= RIGHT_UP;
1010 if (ARR(x,y) != ARR(x+1,y+1)) bitmap_index |= RIGHT_DOWN;
1011 (void) XPutImage(display,window,gc,
1012 sp->bitmaps[bitmap_index],
1014 sp->x_margin + sp->box*x,
1015 sp->y_margin + sp->box*y,
1020 XSetForeground(display, gc, sp->border_color);
1022 XDrawRectangle(display,window,gc,
1023 sp->x_margin-t-1,sp->y_margin-t-1,
1024 sp->box*sp->width+1+2*t, sp->box*sp->height+1+2*t);
1028 /***************************************************
1029 Routines to initialise and close down polyominoes.
1030 ***************************************************/
1032 static void free_bitmaps(polyominoesstruct *sp)
1036 for (n=0;n<countof(sp->bitmaps);n++)
1037 /* Don't bother to free duplicates */
1038 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
1039 sp->bitmaps[n] = None;
1040 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
1041 sp->bitmaps[n] = None;
1042 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
1043 sp->bitmaps[n] = None;
1044 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
1045 sp->bitmaps[n] = None;
1047 else if (sp->bitmaps[n] != None) {
1048 XDestroyImage(sp->bitmaps[n]);
1049 sp->bitmaps[n] = None;
1053 #define deallocate(p,t) if ((p)!=NULL) {free(p); p=(t*)NULL;}
1055 static void free_polyominoes(polyominoesstruct *sp)
1059 for (n=0;n<sp->nr_polyominoes;n++) {
1060 deallocate(sp->polyomino[n].point, point_type);
1063 deallocate(sp->polyomino, polyomino_type);
1064 deallocate(sp->attach_list, int);
1065 deallocate(sp->rectangles, XRectangle);
1066 deallocate(sp->lines, XSegment);
1067 deallocate(sp->reason_to_not_attach, int);
1068 deallocate(sp->array, int);
1069 deallocate(sp->changed_array, int);
1074 #define set_allocate(p,type,size) p = (type *) malloc(size); \
1075 if ((p)==NULL) {free_polyominoes(sp);return 0;}
1077 #define copy_polyomino(dst,src,new_rand) \
1078 (dst).len=(src).len; \
1079 (dst).max_white = (src).max_white; \
1080 set_allocate((dst).point,point_type,sizeof(point_type)*(src).len); \
1081 (dst).len = (src).len; \
1083 random_permutation((src).len,perm_point); \
1084 for (i=0;i<(src).len;i++) \
1085 (dst).point[i] = (src).point[perm_point[i]]; \
1086 (dst).transform_len = (src).transform_len; \
1088 random_permutation((src).transform_len,perm_transform); \
1089 for (i=0;i<(src).transform_len;i++) \
1090 (dst).transform_list[i] = (src).transform_list[perm_transform[i]]; \
1094 /***************************************************
1095 Puzzle specific initialization routines.
1096 ***************************************************/
1099 int check_pentomino_puzzle(polyominoesstruct *sp)
1101 return check_all_regions_multiple_of(sp, 5) && whites_ok(sp);
1105 int check_hexomino_puzzle(polyominoesstruct *sp)
1107 return check_all_regions_multiple_of(sp, 6) && whites_ok(sp);
1111 int check_tetr_pentomino_puzzle(polyominoesstruct *sp)
1113 return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp);
1117 int check_pent_hexomino_puzzle(polyominoesstruct *sp)
1119 return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp);
1123 int check_heptomino_puzzle(polyominoesstruct *sp)
1125 return check_all_regions_multiple_of(sp, 7) && whites_ok(sp);
1129 int check_octomino_puzzle(polyominoesstruct *sp)
1131 return check_all_regions_multiple_of(sp, 8) && whites_ok(sp);
1135 int check_dekomino_puzzle(polyominoesstruct *sp)
1137 return check_all_regions_multiple_of(sp, 10) && whites_ok(sp);
1141 int check_elevenomino_puzzle(polyominoesstruct *sp)
1143 return check_all_regions_multiple_of(sp, 11) && whites_ok(sp);
1146 static struct {int len; point_type point[4];
1147 int transform_len, transform_list[8], max_white;} tetromino[5] =
1152 {4, {{0,0}, {1,0}, {2,0}, {3,0}},
1153 2, {0, 1, -1, -1, -1, -1, -1, -1}, 2},
1158 {4, {{0,0}, {1,0}, {2,0}, {2,1}},
1159 8, {0, 1, 2, 3, 4, 5, 6, 7}, 2},
1164 {4, {{0,0}, {1,0}, {1,1}, {2,0}},
1165 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1170 {4, {{0,0}, {1,0}, {1,1}, {2,1}},
1171 4, {0, 1, 4, 5, -1, -1, -1, -1}, 2},
1176 {4, {{0,0}, {0,1}, {1,0}, {1,1}},
1177 1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}};
1180 static struct pentomino_struct {int len; point_type point[5];
1181 int transform_len, transform_list[8], max_white;}
1187 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}},
1188 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1193 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}},
1194 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1199 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}},
1200 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1206 {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}},
1207 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1212 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}},
1213 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1218 {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}},
1219 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1225 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}},
1226 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1232 {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}},
1233 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1238 {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}},
1239 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1245 {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}},
1246 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1252 {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}},
1253 1, {0, -1, -1, -1, -1, -1, -1, -1}, 4},
1259 {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}},
1260 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}};
1263 static struct hexomino_struct {int len; point_type point[6];
1264 int transform_len, transform_list[8], max_white;}
1270 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}},
1271 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1276 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}},
1277 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1282 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}},
1283 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1288 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}},
1289 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1295 {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}},
1296 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1301 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}},
1302 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1307 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}},
1308 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1314 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}},
1315 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1321 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}},
1322 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1327 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}},
1328 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1334 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}},
1335 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1340 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}},
1341 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1347 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}},
1348 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1354 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}},
1355 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1360 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}},
1361 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1367 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}},
1368 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1374 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}},
1375 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1381 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}},
1382 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1388 {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1389 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1395 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1396 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1401 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}},
1402 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1408 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}},
1409 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1414 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}},
1415 4, {0, 1, 4, 5, -1, -1, -1, -1}, 4},
1421 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}},
1422 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1428 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}},
1429 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1434 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}},
1435 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1441 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}},
1442 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1448 {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}},
1449 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1454 {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}},
1455 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1461 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}},
1462 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1468 {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}},
1469 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1475 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}},
1476 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1482 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}},
1483 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1489 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}},
1490 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1496 {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}},
1497 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}};
1499 static struct pentomino_struct one_sided_pentomino[60];
1501 static void make_one_sided_pentomino(void)
1506 for (i=0;i<countof(pentomino);i++) {
1507 one_sided_pentomino[j] = pentomino[i];
1509 if (one_sided_pentomino[j].transform_list[t]>=4) {
1510 one_sided_pentomino[j].transform_len = t;
1512 one_sided_pentomino[j] = pentomino[i];
1513 for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u];
1514 one_sided_pentomino[j].transform_len -= t;
1521 static struct hexomino_struct one_sided_hexomino[60];
1523 static void make_one_sided_hexomino(void)
1528 for (i=0;i<countof(hexomino);i++) {
1529 one_sided_hexomino[j] = hexomino[i];
1531 if (one_sided_hexomino[j].transform_list[t]>=4) {
1532 one_sided_hexomino[j].transform_len = t;
1534 one_sided_hexomino[j] = hexomino[i];
1535 for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u];
1536 one_sided_hexomino[j].transform_len -= t;
1544 Find all the ways of placing all twelve pentominoes
1545 into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6.
1549 int set_pentomino_puzzle(polyominoesstruct *sp)
1551 int perm_poly[12], perm_point[5], perm_transform[8], i, p;
1572 sp->nr_polyominoes = 12;
1573 set_allocate(sp->polyomino,polyomino_type,
1574 sp->nr_polyominoes*sizeof(polyomino_type));
1575 random_permutation(sp->nr_polyominoes,perm_poly);
1576 for (p=0;p<sp->nr_polyominoes;p++) {
1577 copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1);
1580 sp->check_ok = check_pentomino_puzzle;
1586 Many of the following puzzles are inspired by
1587 http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
1591 Find all the ways of placing all eighteen one-sided pentominoes
1596 int set_one_sided_pentomino_puzzle(polyominoesstruct *sp)
1598 int perm_poly[18], perm_point[5], perm_transform[8], i, p;
1600 make_one_sided_pentomino();
1621 sp->nr_polyominoes = 18;
1622 set_allocate(sp->polyomino,polyomino_type,
1623 sp->nr_polyominoes*sizeof(polyomino_type));
1624 random_permutation(sp->nr_polyominoes,perm_poly);
1625 for (p=0;p<sp->nr_polyominoes;p++) {
1626 copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1);
1629 sp->check_ok = check_pentomino_puzzle;
1635 Find all the ways of placing all sixty one-sided hexominoes
1640 int set_one_sided_hexomino_puzzle(polyominoesstruct *sp)
1642 int perm_poly[60], perm_point[6], perm_transform[8], i, p;
1644 make_one_sided_hexomino();
1681 sp->nr_polyominoes = 60;
1682 set_allocate(sp->polyomino,polyomino_type,
1683 sp->nr_polyominoes*sizeof(polyomino_type));
1684 random_permutation(sp->nr_polyominoes,perm_poly);
1685 for (p=0;p<sp->nr_polyominoes;p++) {
1686 copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1);
1689 sp->check_ok = check_hexomino_puzzle;
1695 Find all the ways of placing all five tetrominoes and all twelve
1696 pentominoes into a rectangle.
1700 int set_tetr_pentomino_puzzle(polyominoesstruct *sp)
1702 int perm_poly[17], perm_point[5], perm_transform[8], i, p;
1719 sp->nr_polyominoes = 17;
1720 set_allocate(sp->polyomino,polyomino_type,
1721 sp->nr_polyominoes*sizeof(polyomino_type));
1722 random_permutation(sp->nr_polyominoes,perm_poly);
1723 for (p=0;p<countof(tetromino);p++) {
1724 copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1);
1726 for (p=0;p<countof(pentomino);p++) {
1727 copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1);
1730 sp->check_ok = check_tetr_pentomino_puzzle;
1735 Find all the ways of placing all twelve pentominoes and all thirty five
1736 hexominoes into a rectangle whose size is 18x15.
1740 int set_pent_hexomino_puzzle(polyominoesstruct *sp)
1742 int perm_poly[47], perm_point[6], perm_transform[8], i, p;
1767 sp->nr_polyominoes = 47;
1768 set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type));
1769 random_permutation(47,perm_poly);
1770 for (p=0;p<countof(pentomino);p++) {
1771 copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1);
1773 for (p=0;p<countof(hexomino);p++) {
1774 copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1);
1777 sp->check_ok = check_pent_hexomino_puzzle;
1785 Science News September 20, 1986 Vol 130, No 12
1786 Science News November 14, 1987 Vol 132, Pg 310
1792 **** fills a 10x5 rectangle
1796 static struct {int len; point_type point[5];
1797 int transform_len, transform_list[8], max_white;} pentomino1 =
1798 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}},
1799 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3};
1802 int set_pentomino_puzzle1(polyominoesstruct *sp)
1804 int perm_point[5], perm_transform[8], i, p;
1809 sp->nr_polyominoes = 10;
1810 set_allocate(sp->polyomino,polyomino_type,
1811 sp->nr_polyominoes*sizeof(polyomino_type));
1812 for (p=0;p<sp->nr_polyominoes;p++) {
1813 copy_polyomino(sp->polyomino[p],pentomino1,1);
1816 sp->check_ok = check_pentomino_puzzle;
1824 ***** fills a 24x23 rectangle
1828 static struct {int len; point_type point[6];
1829 int transform_len, transform_list[8], max_white;} hexomino1 =
1830 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}},
1831 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1834 int set_hexomino_puzzle1(polyominoesstruct *sp)
1836 int perm_point[6], perm_transform[8], i, p;
1841 sp->nr_polyominoes = 92;
1842 set_allocate(sp->polyomino,polyomino_type,
1843 sp->nr_polyominoes*sizeof(polyomino_type));
1844 for (p=0;p<sp->nr_polyominoes;p++) {
1845 copy_polyomino(sp->polyomino[p],hexomino1,1);
1848 sp->check_ok = check_hexomino_puzzle;
1856 ***** fills a 21x26 rectangle
1858 (All solutions have 180 degree rotational symmetry)
1862 static struct {int len; point_type point[7];
1863 int transform_len, transform_list[8], max_white;} heptomino1 =
1864 {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}},
1865 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1868 int set_heptomino_puzzle1(polyominoesstruct *sp)
1870 int perm_point[7], perm_transform[8], i, p;
1877 sp->nr_polyominoes = 78;
1878 set_allocate(sp->polyomino,polyomino_type,
1879 sp->nr_polyominoes*sizeof(polyomino_type));
1880 for (p=0;p<sp->nr_polyominoes;p+=2) {
1881 copy_polyomino(sp->polyomino[p],heptomino1,1);
1882 copy_polyomino(sp->polyomino[p+1],heptomino1,0);
1885 sp->check_ok = check_heptomino_puzzle;
1890 /* The following puzzles from
1891 Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition
1892 by Solomon W. Golomb Princeton University Press 1994
1898 ***** fills a 28x19 rectangle
1902 int set_heptomino_puzzle2(polyominoesstruct *sp)
1904 int perm_point[7], perm_transform[8], i, p;
1909 sp->nr_polyominoes = 76;
1910 set_allocate(sp->polyomino,polyomino_type,
1911 sp->nr_polyominoes*sizeof(polyomino_type));
1912 for (p=0;p<sp->nr_polyominoes;p++) {
1913 copy_polyomino(sp->polyomino[p],heptomino1,1);
1916 sp->check_ok = check_heptomino_puzzle;
1924 **** fills a 25x22 rectangle
1929 static struct {int len; point_type point[11];
1930 int transform_len, transform_list[8], max_white;} elevenomino1 =
1931 {11, {{0,0}, {1,0}, {2,0},
1932 {0,1}, {1,1}, {2,1}, {3,1},
1933 {0,2}, {1,2}, {2,2}, {3,2}},
1934 8, {0, 1, 2, 3, 4, 5, 6, 7}, 6};
1937 int set_elevenomino_puzzle1(polyominoesstruct *sp)
1939 int perm_point[11], perm_transform[8], i, p;
1946 sp->nr_polyominoes = 50;
1947 set_allocate(sp->polyomino,polyomino_type,
1948 sp->nr_polyominoes*sizeof(polyomino_type));
1949 for (p=0;p<sp->nr_polyominoes;p+=2) {
1950 copy_polyomino(sp->polyomino[p],elevenomino1,1);
1951 copy_polyomino(sp->polyomino[p+1],elevenomino1,0);
1954 sp->check_ok = check_elevenomino_puzzle;
1963 **** fills 32 x 30 rectangle
1968 static struct {int len; point_type point[10];
1969 int transform_len, transform_list[8], max_white;} dekomino1 =
1972 {0,1}, {1,1}, {2,1}, {3,1},
1973 {0,2}, {1,2}, {2,2}, {3,2}},
1974 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1977 int set_dekomino_puzzle1(polyominoesstruct *sp)
1979 int perm_point[10], perm_transform[8], i, p;
1984 sp->nr_polyominoes = 96;
1985 set_allocate(sp->polyomino,polyomino_type,
1986 sp->nr_polyominoes*sizeof(polyomino_type));
1987 for (p=0;p<sp->nr_polyominoes;p++) {
1988 copy_polyomino(sp->polyomino[p],dekomino1,1);
1991 sp->check_ok = check_dekomino_puzzle;
1999 *** fills 96 x 26 rectangle
2004 static struct {int len; point_type point[10];
2005 int transform_len, transform_list[8], max_white;} octomino1 =
2007 {0,1}, {1,1}, {2,1},
2008 {0,2}, {1,2}, {2,2}, {3,2}},
2009 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
2012 int set_octomino_puzzle1(polyominoesstruct *sp)
2014 int perm_point[8], perm_transform[8], i, p;
2019 sp->nr_polyominoes = 312;
2020 set_allocate(sp->polyomino,polyomino_type,
2021 sp->nr_polyominoes*sizeof(polyomino_type));
2022 for (p=0;p<sp->nr_polyominoes;p++) {
2023 copy_polyomino(sp->polyomino[p],octomino1,1);
2026 sp->check_ok = check_octomino_puzzle;
2033 * fills 15 x 15 rectangle
2039 int set_pentomino_puzzle2(polyominoesstruct *sp)
2041 int perm_point[5], perm_transform[8], i, p;
2046 sp->nr_polyominoes = 45;
2047 set_allocate(sp->polyomino,polyomino_type,
2048 sp->nr_polyominoes*sizeof(polyomino_type));
2049 for (p=0;p<sp->nr_polyominoes;p++) {
2050 copy_polyomino(sp->polyomino[p],pentomino1,1);
2053 sp->check_ok = check_pentomino_puzzle;
2061 **** fills a 47x33 rectangle
2067 int set_elevenomino_puzzle2(polyominoesstruct *sp)
2069 int perm_point[11], perm_transform[8], i, p;
2074 sp->nr_polyominoes = 141;
2075 set_allocate(sp->polyomino,polyomino_type,
2076 sp->nr_polyominoes*sizeof(polyomino_type));
2077 for (p=0;p<sp->nr_polyominoes;p++) {
2078 copy_polyomino(sp->polyomino[p],elevenomino1,1);
2081 sp->check_ok = check_elevenomino_puzzle;
2086 /**************************************************
2088 **************************************************/
2090 #define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes(sp); return;}
2093 init_polyominoes (ModeInfo * mi)
2095 polyominoesstruct *sp;
2100 if (polyominoeses == NULL) {
2102 = (polyominoesstruct *) calloc(MI_NUM_SCREENS(mi),sizeof (polyominoesstruct)))
2106 sp = &polyominoeses[MI_SCREEN(mi)];
2108 free_polyominoes(sp);
2113 if (MI_IS_FULLRANDOM(mi)) {
2114 sp->identical = (Bool) (LRAND() & 1);
2115 sp->use3D = (Bool) (NRAND(4));
2117 sp->identical = identical;
2120 if (sp->identical) {
2123 if (!set_pentomino_puzzle1(sp))
2127 if (!set_hexomino_puzzle1(sp))
2131 if (!set_heptomino_puzzle1(sp))
2135 if (!set_heptomino_puzzle2(sp))
2139 if (!set_elevenomino_puzzle1(sp))
2143 if (!set_dekomino_puzzle1(sp))
2147 if (!set_octomino_puzzle1(sp))
2151 if (!set_pentomino_puzzle2(sp))
2155 if (!set_elevenomino_puzzle2(sp))
2162 if (!set_pentomino_puzzle(sp))
2166 if (!set_one_sided_pentomino_puzzle(sp))
2170 if (!set_one_sided_hexomino_puzzle(sp))
2174 if (!set_pent_hexomino_puzzle(sp))
2178 if (!set_tetr_pentomino_puzzle(sp))
2184 allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int));
2185 sp->nr_attached = 0;
2187 if (sp->identical) {
2188 allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int));
2191 allocate(sp->array,int,sp->width*sp->height*sizeof(int));
2192 allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int));
2193 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1;
2195 sp->left_right = NRAND(2);
2196 sp->top_bottom = NRAND(2);
2198 box1 = MI_WIDTH(mi)/(sp->width+2);
2199 box2 = MI_HEIGHT(mi)/(sp->height+2);
2205 if (sp->box >= 12) {
2206 sp->box = (sp->box/12)*12;
2207 create_bitmaps(mi,sp);
2208 if (!sp->use_bitmaps)
2212 sp->use_bitmaps = 0;
2214 if (!sp->use_bitmaps) {
2215 allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle));
2216 allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment));
2219 allocate(perm,int,sp->nr_polyominoes*sizeof(int));
2220 random_permutation(sp->nr_polyominoes, perm);
2221 sp->mono = MI_NPIXELS(mi) < 12;
2222 start = NRAND(MI_NPIXELS(mi));
2223 for (i=0;i<sp->nr_polyominoes;i++)
2225 sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi));
2227 sp->polyomino[i+1].color = sp->polyomino[i].color;
2233 sp->polyomino[i].color = MI_WHITE_PIXEL(mi);
2235 sp->polyomino[i].color = MI_BLACK_PIXEL(mi);
2238 if (sp->use_bitmaps) {
2240 sp->border_color = MI_WHITE_PIXEL(mi);
2242 sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi)));
2245 sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2;
2246 sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2;
2251 /* Clear the background. */
2258 draw_polyominoes (ModeInfo * mi)
2260 polyominoesstruct *sp;
2261 int poly_no,point_no,transform_index,done,another_attachment_try;
2262 point_type attach_point;
2265 if (polyominoeses == NULL)
2267 sp = &polyominoeses[MI_SCREEN(mi)];
2271 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2276 if (MI_CYCLES(mi) != 0) {
2277 if (++sp->counter > MI_CYCLES(mi)) {
2279 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2280 #endif /* STANDALONE */
2281 init_polyominoes(mi);
2288 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2289 #endif /* STANDALONE */
2290 init_polyominoes(mi);
2294 MI_IS_DRAWN(mi) = True;
2296 if (sp->wait>0) return;
2298 memset(sp->changed_array,0,sp->width*sp->height*sizeof(int));
2300 poly_no = first_poly_no(sp);
2302 transform_index = 0;
2304 another_attachment_try = 1;
2305 find_blank(sp,&attach_point);
2306 if (sp->identical && sp->nr_attached < sp->nr_polyominoes)
2307 memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int));
2309 if (sp->nr_attached < sp->nr_polyominoes) {
2310 while (!done && another_attachment_try) {
2311 done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0));
2312 if (done && sp->rot180) {
2313 poly_no = first_poly_no(sp);
2314 done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0));
2316 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2319 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2323 if (sp->identical) {
2325 if (sp->nr_attached == 0)
2328 detach_until=sp->nr_attached-1;
2329 if (sp->nr_attached < sp->nr_polyominoes)
2330 while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0)
2332 while (sp->nr_attached>detach_until) {
2334 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2335 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2336 if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes)
2337 for (i=0;i<sp->nr_polyominoes;i++)
2338 REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i);
2340 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2346 if (sp->nr_attached == 0)
2350 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2351 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2353 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2358 if (sp->use_bitmaps)
2359 draw_with_bitmaps(mi,sp);
2361 draw_without_bitmaps(mi,sp);
2363 if (sp->nr_attached == sp->nr_polyominoes)
2370 reshape_polyominoes(ModeInfo * mi, int width, int height)
2372 XClearWindow (MI_DISPLAY (mi), MI_WINDOW(mi));
2373 init_polyominoes (mi);
2377 release_polyominoes(ModeInfo * mi)
2381 if (polyominoeses != NULL) {
2382 for (screen=0;screen<MI_NUM_SCREENS(mi); screen++)
2383 free_polyominoes(&polyominoeses[screen]);
2384 (void) free((void *) polyominoeses);
2385 polyominoeses = (polyominoesstruct *) NULL;
2390 refresh_polyominoes (ModeInfo * mi)
2395 XSCREENSAVER_MODULE ("Polyominoes", polyominoes)
2397 #endif /* MODE_polyominoes */