1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* polyominoes --- Shows attempts to place polyominoes into a rectangle */
4 #if !defined( lint ) && !defined( SABER )
5 static const char sccsid[] = "@(#)polyominoes.c 5.01 2000/12/18 xlockmore";
10 * Copyright (c) 2000 by Stephen Montgomery-Smith <stephen@math.missouri.edu>
12 * Permission to use, copy, modify, and distribute this software and its
13 * documentation for any purpose and without fee is hereby granted,
14 * provided that the above copyright notice appear in all copies and that
15 * both that copyright notice and this permission notice appear in
16 * supporting documentation.
18 * This file is provided AS IS with no warranties of any kind. The author
19 * shall have no liability with respect to the infringement of copyrights,
20 * trade secrets or any patents by this file or any part thereof. In no
21 * event will the author be liable for any lost revenue or profits or
22 * other special, indirect and consequential damages.
25 * 07-Jan-2001: Made improvement to the search algorithm for the puzzles
26 * involving identical polyominoes (via the variable
27 * reason_to_not_attach). By Stephen Montgomery-Smith.
28 * 20-Dec-2000: Added more puzzles at David Bagley's request.
29 * 27-Nov-2000: Adapted from euler2d.c Copyright (c) 2000 by Stephen
31 * 05-Jun-2000: Adapted from flow.c Copyright (c) 1996 by Tim Auckland
32 * 18-Jul-1996: Adapted from swarm.c Copyright (c) 1991 by Patrick J. Naughton.
33 * 31-Aug-1990: Adapted from xswarm by Jeff Butterworth. (butterwo@ncsc.org)
37 #define MODE_polyominoes
38 #define PROGCLASS "Polyominoes"
39 #define HACK_INIT init_polyominoes
40 #define HACK_DRAW draw_polyominoes
41 #define polyominoes_opts xlockmore_opts
42 #define DEFAULTS "*delay: 10000 \n" \
46 #include "xlockmore.h" /* in xscreensaver distribution */
48 #include <X11/Xutil.h>
49 #else /* STANDALONE */
50 #include "xlock.h" /* in xlockmore distribution */
51 #endif /* STANDALONE */
53 #ifdef MODE_polyominoes
54 #define DEF_IDENTICAL "False"
55 #define DEF_PLAIN "False"
57 static Bool identical;
60 static XrmOptionDescRec opts[] =
62 {(char *) "-identical", (char *) ".polyominoes.identical", XrmoptionNoArg, (caddr_t) "on"},
63 {(char *) "+identical", (char *) ".polyominoes.identical", XrmoptionNoArg, (caddr_t) "off"},
64 {(char *) "-plain", (char *) ".polyominoes.plain", XrmoptionNoArg, (caddr_t) "on"},
65 {(char *) "+plain", (char *) ".polyominoes.plain", XrmoptionNoArg, (caddr_t) "off"}
67 static argtype vars[] =
69 {(caddr_t *) &identical, (char *) "identical", (char *) "Identical", (char *) DEF_IDENTICAL, t_Bool},
70 {(caddr_t *) & plain, (char *) "plain", (char *) "Plain", (char *) DEF_PLAIN, t_Bool}
72 static OptionStruct desc[] =
74 {(char *) "-/+identical", (char *) "turn on/off puzzles where the polyomino pieces are identical"},
75 {(char *) "-/+plain", (char *) "turn on/off plain pieces"}
78 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 #define ARRAY(x,y) (sp->array[(x)*sp->height+(y)])
182 #define CHANGED_ARRAY(x,y) (sp->changed_array[(x)*sp->height+(y)])
183 #define ARRAY_P(p) (sp->array[(p).x*sp->height+(p).y])
184 #define CHANGED_ARRAY_P(p) (sp->changed_array[(p).x*sp->height+(p).y])
185 #define ARR(x,y) (((x)<0||(x)>=sp->width||(y)<0||(y)>=sp->height)?-2:ARRAY(x,y))
187 #define REASON_TO_NOT_ATTACH(x,y) (sp->reason_to_not_attach[(x)*sp->nr_polyominoes+(y)])
189 #define ROUND8(n) ((((n)+7)/8)*8)
191 /* Defines to index the bitmaps. A set bit indicates that an edge or
192 corner is required. */
197 #define LEFT_UP (1<<4)
198 #define LEFT_DOWN (1<<5)
199 #define RIGHT_UP (1<<6)
200 #define RIGHT_DOWN (1<<7)
201 #define IS_LEFT(n) ((n) & LEFT)
202 #define IS_RIGHT(n) ((n) & RIGHT)
203 #define IS_UP(n) ((n) & UP)
204 #define IS_DOWN(n) ((n) & DOWN)
205 #define IS_LEFT_UP(n) ((n) & LEFT_UP)
206 #define IS_LEFT_DOWN(n) ((n) & LEFT_DOWN)
207 #define IS_RIGHT_UP(n) ((n) & RIGHT_UP)
208 #define IS_RIGHT_DOWN(n) ((n) & RIGHT_DOWN)
210 /* Defines to access the bitmaps. */
211 #define BITNO(x,y) ((x)+(y)*ROUND8(sp->box))
212 #define SETBIT(n,x,y) {data[BITNO(x,y)/8] |= 1<<(BITNO(x,y)%8);}
213 #define RESBIT(n,x,y) {data[BITNO(x,y)/8] &= ~(1<<(BITNO(x,y)%8));}
214 #define TWOTHIRDSBIT(n,x,y) {if ((x+y-1)%3) SETBIT(n,x,y) else RESBIT(n,x,y)}
215 #define HALFBIT(n,x,y) {if ((x-y)%2) SETBIT(n,x,y) else RESBIT(n,x,y)}
216 #define THIRDBIT(n,x,y) {if (!((x-y-1)%3)) SETBIT(n,x,y) else RESBIT(n,x,y)}
217 #define THREEQUARTERSBIT(n,x,y) \
218 {if ((y%2)||((x+2+y/2+1)%2)) SETBIT(n,x,y) else RESBIT(n,x,y)}
219 #define NOTHALFBIT(n,x,y) {if ((x-y)%2) RESBIT(n,x,y) else SETBIT(n,x,y)}
221 /* Parameters for bitmaps. */
222 #define G ((sp->box/45)+1) /* 1/2 of gap between polyominoes. */
223 #define T ((sp->box<=12)?1:(G*2)) /* Thickness of walls of polyominoes. */
224 #define R ((sp->box<=12)?1:(G*6)) /* Amount of rounding. */
225 #define RT ((sp->box<=12)?1:(G*3)) /* Thickness of wall of rounded parts.
226 Here 3 is an approximation to 2 sqrt(2). */
227 #define RR 0 /* Roof ridge thickness */
230 /* A list of those bitmaps we need to create to display any pentomino. */
231 /* (not used right now because it does not seem to work for hexonimoes.) */
233 static int bitmaps_needed[] =
235 LEFT_UP|LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
237 LEFT|RIGHT_UP|RIGHT_DOWN,
238 RIGHT|LEFT_UP|LEFT_DOWN,
239 UP|LEFT_DOWN|RIGHT_DOWN,
240 DOWN|LEFT_UP|RIGHT_UP,
250 /* These needed for hexonimoes*/
255 LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
256 LEFT_UP|RIGHT_UP|RIGHT_DOWN,
257 LEFT_UP|LEFT_DOWN|RIGHT_DOWN,
258 LEFT_UP|LEFT_DOWN|RIGHT_UP,
280 static int bitmap_needed(int n) {
283 for (i=0;bitmaps_needed[i]!=-1;i++)
284 if (n == bitmaps_needed[i])
291 /* Some debugging routines.
293 static void print_board(polyominoesstruct *sp) {
295 for (y=0;y<sp->height;y++) {
296 for (x=0;x<sp->width;x++)
297 if (ARRAY(x,y) == -1)
300 fprintf(stderr,"%c",'a'+ARRAY(x,y));
301 fprintf(stderr,"\n");
303 fprintf(stderr,"\n");
306 static void print_points(point_type *point, int len) {
310 fprintf(stderr,"(%d %d) ",point[i].x,point[i].y);
313 static void print_polyomino(polyomino_type poly) {
316 print_points(poly.point,poly.len);
317 fprintf(stderr,"\n");
318 for (i=0;i<poly.transform_len;i++)
319 fprintf(stderr,"%d ",poly.transform_list[i]);
320 fprintf(stderr,"\n");
324 static polyominoesstruct *polyominoeses = (polyominoesstruct *) NULL;
327 void random_permutation(int n, int a[]) {
330 for (i=0;i<n;i++) a[i] = -1;
344 /************************************************************
345 These are the routines for manipulating the polyominoes and
346 attaching and detaching them from the rectangle.
347 ************************************************************/
349 static void transform(point_type in, point_type offset, int transform_no,
350 point_type attach_point, point_type *out) {
351 switch (transform_no) {
352 case 0: out->x=in.x-offset.x+attach_point.x;
353 out->y=in.y-offset.y+attach_point.y;
355 case 1: out->x=-(in.y-offset.y)+attach_point.x;
356 out->y=in.x-offset.x+attach_point.y;
358 case 2: out->x=-(in.x-offset.x)+attach_point.x;
359 out->y=-(in.y-offset.y)+attach_point.y;
361 case 3: out->x=in.y-offset.y+attach_point.x;
362 out->y=-(in.x-offset.x)+attach_point.y;
364 case 4: out->x=-(in.x-offset.x)+attach_point.x;
365 out->y=in.y-offset.y+attach_point.y;
367 case 5: out->x=in.y-offset.y+attach_point.x;
368 out->y=in.x-offset.x+attach_point.y;
370 case 6: out->x=in.x-offset.x+attach_point.x;
371 out->y=-(in.y-offset.y)+attach_point.y;
373 case 7: out->x=-(in.y-offset.y)+attach_point.x;
374 out->y=-(in.x-offset.x)+attach_point.y;
379 static int first_poly_no(polyominoesstruct *sp) {
383 while(poly_no<sp->nr_polyominoes && sp->polyomino[poly_no].attached)
388 static void next_poly_no(polyominoesstruct *sp, int *poly_no) {
391 *poly_no = sp->nr_polyominoes;
395 } while (*poly_no<sp->nr_polyominoes && sp->polyomino[*poly_no].attached);
399 /* check_all_regions_multiple_of looks for connected regions of
400 blank spaces, and returns 0 if it finds a connected region containing
401 a number of blanks that is not a multiple of n.
404 static void count_adjacent_blanks(polyominoesstruct *sp, int *count, int x, int y, int blank_mark) {
406 if (ARRAY(x,y) == -1) {
408 ARRAY(x,y) = blank_mark;
409 if (x>=1) count_adjacent_blanks(sp, count,x-1,y,blank_mark);
410 if (x<sp->width-1) count_adjacent_blanks(sp, count,x+1,y,blank_mark);
411 if (y>=1) count_adjacent_blanks(sp, count,x,y-1,blank_mark);
412 if (y<sp->height-1) count_adjacent_blanks(sp, count,x,y+1,blank_mark);
416 static int check_all_regions_multiple_of(polyominoesstruct *sp, int n) {
417 int x,y,count,good = 1;
419 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
421 count_adjacent_blanks(sp, &count,x,y,-2);
425 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
426 if (ARRAY(x,y) == -2)
432 static int check_all_regions_positive_combination_of(polyominoesstruct *sp, int m, int n) {
433 int x,y,count,good = 1;
435 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
437 count_adjacent_blanks(sp, &count,x,y,-2);
439 for (;count>=0 && !good;count-=m)
443 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
444 if (ARRAY(x,y) == -2)
450 static int find_smallest_blank_component(polyominoesstruct *sp) {
451 int x,y,size,smallest_size,blank_mark,smallest_mark;
453 smallest_mark = blank_mark = -10;
454 smallest_size = 1000000000;
455 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y) == -1) {
457 count_adjacent_blanks(sp, &size,x,y,blank_mark);
458 if (size<smallest_size) {
459 smallest_mark = blank_mark;
460 smallest_size = size;
465 return smallest_mark;
468 /* "Chess board" check - see init_max_whites_list above for more details.
470 /* If the rectangle is alternatively covered by white and black
471 squares (chess board style), then this gives the list of
472 the maximal possible whites covered by each polyomino. It
473 is used by the function whites_ok which makes sure that the
474 array has a valid number of white or black remaining blanks left.
477 static int whites_ok(polyominoesstruct *sp) {
478 int x,y,poly_no,whites=0,blacks=0,max_white=0,min_white=0;
480 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
481 if (ARRAY(x,y) == -1 && (x+y)%2) whites++;
482 if (ARRAY(x,y) == -1 && (x+y+1)%2) blacks++;
484 for (poly_no=0;poly_no<sp->nr_polyominoes;poly_no++) if (!sp->polyomino[poly_no].attached) {
485 max_white += sp->polyomino[poly_no].max_white;
486 min_white += sp->polyomino[poly_no].len - sp->polyomino[poly_no].max_white;
488 return (min_white <= blacks && min_white <= whites
489 && blacks <= max_white && whites <= max_white);
492 /* This routine looks at the point (x,y) and sees how many polyominoes
493 and all their various transforms may be attached there.
497 score_point(polyominoesstruct *sp, int x, int y, int min_score_so_far) {
498 int poly_no, point_no, transform_index, i, attachable;
499 point_type attach_point, target_point;
502 if (x>=1 && x<sp->width-1 && y>=1 && y<sp->height-1 &&
503 ARRAY(x-1,y-1)<0 && ARRAY(x-1,y)<0 && ARRAY(x-1,y+1)<0 &&
504 ARRAY(x+1,y-1)<0 && ARRAY(x+1,y)<0 && ARRAY(x+1,y+1)<0 &&
505 ARRAY(x,y-1)<0 && ARRAY(x,y+1)<0)
510 for (poly_no=first_poly_no(sp);poly_no<sp->nr_polyominoes;next_poly_no(sp,&poly_no))
511 if (!sp->polyomino[poly_no].attached) {
512 for (point_no=0;point_no<sp->polyomino[poly_no].len;point_no++)
513 for (transform_index=0;transform_index<sp->polyomino[poly_no].transform_len;transform_index++) {
515 for (i=0;i<sp->polyomino[poly_no].len;i++) {
516 transform(sp->polyomino[poly_no].point[i],
517 sp->polyomino[poly_no].point[point_no],
518 sp->polyomino[poly_no].transform_list[transform_index],
519 attach_point, &target_point);
520 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
521 && (target_point.y>=0) && (target_point.y<sp->height)
522 && (ARRAY_P(target_point)<0))) {
529 if (score>=min_score_so_far)
538 static void find_blank(polyominoesstruct *sp, point_type *point) {
539 int score, worst_score;
543 blank_mark = find_smallest_blank_component(sp);
545 worst_score = 1000000;
546 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y)==blank_mark) {
547 score = 100*score_point(sp,x,y,worst_score);
549 if (sp->left_right) score += 10*x;
550 else score += 10*(sp->width-1-x);
551 if (sp->top_bottom) score += y;
552 else score += (sp->height-1-y);
554 if (score<worst_score) {
561 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
562 if (ARRAY(x,y)<0) ARRAY(x,y) = -1;
565 /* Detaches the most recently attached polyomino. */
568 void detach(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index, point_type *attach_point, int rot180) {
570 point_type target_point;
572 if (sp->nr_attached == 0) return;
574 *poly_no = sp->attach_list[sp->nr_attached];
575 *point_no = sp->polyomino[*poly_no].point_no;
576 *transform_index = sp->polyomino[*poly_no].transform_index;
577 *attach_point = sp->polyomino[*poly_no].attach_point;
578 for (i=0;i<sp->polyomino[*poly_no].len;i++) {
579 transform(sp->polyomino[*poly_no].point[i],
580 sp->polyomino[*poly_no].point[*point_no],
581 sp->polyomino[*poly_no].transform_list[*transform_index]^(rot180<<1),
582 *attach_point, &target_point);
583 ARRAY_P(target_point) = -1;
584 CHANGED_ARRAY_P(target_point) = 1;
587 sp->polyomino[*poly_no].attached = 0;
590 /* Attempts to attach a polyomino at point (x,y) at the
591 point_no-th point of that polyomino, using the transform
592 transform_no. Returns 1 if successful.
596 int attach(polyominoesstruct *sp, int poly_no, int point_no, int transform_index, point_type attach_point, int rot180,
597 int *reason_to_not_attach) {
598 point_type target_point;
600 int attachable = 1, worst_reason_not_to_attach = 1000000000;
603 attach_point.x = sp->width-1-attach_point.x;
604 attach_point.y = sp->height-1-attach_point.y;
607 if (sp->polyomino[poly_no].attached)
610 for (i=0;i<sp->polyomino[poly_no].len;i++) {
611 transform(sp->polyomino[poly_no].point[i],
612 sp->polyomino[poly_no].point[point_no],
613 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
614 attach_point, &target_point);
615 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
616 && (target_point.y>=0) && (target_point.y<sp->height)
617 && (ARRAY_P(target_point) == -1))) {
620 if ((target_point.x>=0) && (target_point.x<sp->width)
621 && (target_point.y>=0) && (target_point.y<sp->height)
622 && (ARRAY_P(target_point) >= 0)
623 && (ARRAY_P(target_point)<worst_reason_not_to_attach))
624 worst_reason_not_to_attach = ARRAY_P(target_point);
631 if (sp->identical && !attachable) {
632 if (worst_reason_not_to_attach < 1000000000)
633 reason_to_not_attach[worst_reason_not_to_attach] = 1;
637 for (i=0;i<sp->polyomino[poly_no].len;i++) {
638 transform(sp->polyomino[poly_no].point[i],
639 sp->polyomino[poly_no].point[point_no],
640 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
641 attach_point, &target_point);
642 ARRAY_P(target_point) = poly_no;
643 CHANGED_ARRAY_P(target_point) = 1;
646 sp->attach_list[sp->nr_attached] = poly_no;
649 sp->polyomino[poly_no].attached = 1;
650 sp->polyomino[poly_no].point_no = point_no;
651 sp->polyomino[poly_no].attach_point = attach_point;
652 sp->polyomino[poly_no].transform_index = transform_index;
654 if (!sp->check_ok(sp)) {
655 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,rot180);
663 int next_attach_try(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index) {
665 (*transform_index)++;
666 if (*transform_index>=sp->polyomino[*poly_no].transform_len) {
667 *transform_index = 0;
669 if (*point_no>=sp->polyomino[*poly_no].len) {
671 next_poly_no(sp,poly_no);
672 if (*poly_no>=sp->nr_polyominoes) {
673 *poly_no = first_poly_no(sp);
682 /*******************************************************
684 *******************************************************/
687 draw_without_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
688 Display *display = MI_DISPLAY(mi);
689 Window window = MI_WINDOW(mi);
691 int x,y,poly_no,nr_lines,nr_rectangles;
693 XSetLineAttributes(display,gc,sp->box/10+1,LineSolid,CapRound,JoinRound);
695 for (poly_no=-1;poly_no<sp->nr_polyominoes;poly_no++) {
697 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
698 if (CHANGED_ARRAY(x,y) && ARRAY(x,y) == poly_no) {
699 sp->rectangles[nr_rectangles].x = sp->x_margin + sp->box*x;
700 sp->rectangles[nr_rectangles].y = sp->y_margin + sp->box*y;
701 sp->rectangles[nr_rectangles].width = sp->box;
702 sp->rectangles[nr_rectangles].height = sp->box;
706 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
708 XSetForeground(display, gc, sp->polyomino[poly_no].color);
709 XFillRectangles(display, window, gc, sp->rectangles, nr_rectangles);
712 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
715 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
716 if (ARRAY(x,y) == -1 && ARRAY(x+1,y) == -1
717 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x+1,y))) {
718 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
719 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
720 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
721 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
725 XDrawSegments(display, window, gc, sp->lines, nr_lines);
728 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
729 if (ARRAY(x,y) == -1 && ARRAY(x,y+1) == -1
730 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x,y+1))) {
731 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
732 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
733 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
734 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
738 XDrawSegments(display, window, gc, sp->lines, nr_lines);
740 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
741 XDrawRectangle(display, window, gc, sp->x_margin, sp->y_margin, sp->box*sp->width, sp->box*sp->height);
743 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
746 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
747 if (ARRAY(x+1,y) != ARRAY(x,y)) {
748 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
749 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
750 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
751 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
755 XDrawSegments(display, window, gc, sp->lines, nr_lines);
758 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
759 if (ARRAY(x,y+1) != ARRAY(x,y)) {
760 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
761 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
762 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
763 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
767 XDrawSegments(display, window, gc, sp->lines, nr_lines);
768 XSetLineAttributes(display,gc,1,LineSolid,CapRound,JoinRound);
772 static void create_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
776 for (n=0;n<256;n++) {
778 /* Avoid duplication of identical bitmaps. */
779 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
780 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_UP];
781 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
782 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_DOWN];
783 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
784 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_UP];
785 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
786 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_DOWN];
788 else /* if (bitmap_needed(n)) */ {
789 data = (char *) malloc(sizeof(char)*(sp->box*ROUND8(sp->box)/8));
795 for (y=0;y<sp->box;y++) for (x=0;x<sp->box;x++) {
797 #ifdef SMALL_BELLYBUTTON
798 if (x >= sp->box / 2 && x <= sp->box / 2 + 1 &&
799 y >= sp->box / 2 && y <= sp->box / 2 + 1)
804 } else if ((x>=y && x<=sp->box-y-1 && IS_UP(n))
805 || (x<=y && x<=sp->box-y-1 && y<sp->box/2 && !IS_LEFT(n))
806 || (x>=y && x>=sp->box-y-1 && y<sp->box/2 && !IS_RIGHT(n)))
808 else if ((x<=y && x<=sp->box-y-1 && IS_LEFT(n))
809 || (x>=y && x<=sp->box-y-1 && x<sp->box/2 && !IS_UP(n))
810 || (x<=y && x>=sp->box-y-1 && x<sp->box/2 && !IS_DOWN(n)))
812 else if ((x>=y && x>=sp->box-y-1 && IS_RIGHT(n))
813 || (x>=y && x<=sp->box-y-1 && x>=sp->box/2 && !IS_UP(n))
814 || (x<=y && x>=sp->box-y-1 && x>=sp->box/2 && !IS_DOWN(n)))
816 else if ((x<=y && x>=sp->box-y-1 && IS_DOWN(n))
817 || (x<=y && x<=sp->box-y-1 && y>=sp->box/2 && !IS_LEFT(n))
818 || (x>=y && x>=sp->box-y-1 && y>=sp->box/2 && !IS_RIGHT(n)))
823 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
826 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
827 SETBIT(n,sp->box-1-x,y)
829 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
832 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
833 SETBIT(n,x,sp->box-1-y)
835 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
838 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
839 RESBIT(n,sp->box-1-x,y)
841 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
844 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
845 RESBIT(n,x,sp->box-1-y)
847 if (IS_LEFT(n) && IS_UP(n))
849 for (y=G;y<=R+2*G-x;y++) {
855 if (IS_LEFT(n) && IS_DOWN(n))
857 for (y=G;y<=R+2*G-x;y++) {
859 SETBIT(n,x,sp->box-1-y)
861 RESBIT(n,x,sp->box-1-y)
863 if (IS_RIGHT(n) && IS_UP(n))
865 for (y=G;y<=R+2*G-x;y++) {
867 SETBIT(n,sp->box-1-x,y)
869 RESBIT(n,sp->box-1-x,y)
871 if (IS_RIGHT(n) && IS_DOWN(n))
873 for (y=G;y<=R+2*G-x;y++) {
875 SETBIT(n,sp->box-1-x,sp->box-1-y)
877 RESBIT(n,sp->box-1-x,sp->box-1-y)
880 if (!IS_LEFT(n) && !IS_UP(n) && IS_LEFT_UP(n)) {
881 for (x=0;x<G;x++) for(y=0;y<G;y++)
883 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
885 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
888 if (!IS_LEFT(n) && !IS_DOWN(n) && IS_LEFT_DOWN(n)) {
889 for (x=0;x<G;x++) for(y=0;y<G;y++)
890 RESBIT(n,x,sp->box-1-y)
891 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
892 SETBIT(n,x,sp->box-1-y)
893 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
894 SETBIT(n,x,sp->box-1-y)
896 if (!IS_RIGHT(n) && !IS_UP(n) && IS_RIGHT_UP(n)) {
897 for (x=0;x<G;x++) for(y=0;y<G;y++)
898 RESBIT(n,sp->box-1-x,y)
899 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
900 SETBIT(n,sp->box-1-x,y)
901 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
902 SETBIT(n,sp->box-1-x,y)
904 if (!IS_RIGHT(n) && !IS_DOWN(n) && IS_RIGHT_DOWN(n)) {
905 for (x=0;x<G;x++) for(y=0;y<G;y++)
906 RESBIT(n,sp->box-1-x,sp->box-1-y)
907 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
908 SETBIT(n,sp->box-1-x,sp->box-1-y)
909 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
910 SETBIT(n,sp->box-1-x,sp->box-1-y)
913 #ifdef LARGE_BELLYBUTTON
915 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
916 for (x=0;x<G+T;x++) for(y=0;y<G+T;y++)
918 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
919 for (x=0;x<G+T;x++) for(y=sp->box-G-T;y<sp->box;y++)
921 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
922 for (x=sp->box-G-T;x<sp->box;x++) for(y=0;y<G+T;y++)
924 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
925 for (x=sp->box-G-T;x<sp->box;x++) for(y=sp->box-G-T;y<sp->box;y++)
932 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
933 for (x=0;x<sp->box/2-RR;x++) for(y=0;y<sp->box/2-RR;y++)
934 THREEQUARTERSBIT(n,x,y)
935 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
936 for (x=0;x<sp->box/2-RR;x++) for(y=sp->box/2+RR;y<sp->box;y++)
937 THREEQUARTERSBIT(n,x,y)
938 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
939 for (x=sp->box/2+RR;x<sp->box;x++) for(y=0;y<sp->box/2-RR;y++)
940 THREEQUARTERSBIT(n,x,y)
941 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
942 for (x=sp->box/2+RR;x<sp->box;x++) for(y=sp->box/2+RR;y<sp->box;y++)
943 THREEQUARTERSBIT(n,x,y)
946 sp->bitmaps[n] = XCreateImage(MI_DISPLAY(mi), MI_VISUAL(mi), 1, XYBitmap,
947 0, data, sp->box, sp->box, 8, 0);
948 if (sp->bitmaps[n] == None) {
953 sp->bitmaps[n]->byte_order = MSBFirst;
954 sp->bitmaps[n]->bitmap_unit = 8;
955 sp->bitmaps[n]->bitmap_bit_order = LSBFirst;
962 static void draw_with_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
963 Display *display = MI_DISPLAY(mi);
964 Window window = MI_WINDOW(mi);
966 int x,y,t,bitmap_index;
968 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
969 if (ARRAY(x,y) == -1) {
970 if (CHANGED_ARRAY(x,y)) {
971 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
972 XFillRectangle(display,window,gc,
973 sp->x_margin + sp->box*x,
974 sp->y_margin + sp->box*y,
979 XSetForeground(display, gc, sp->polyomino[ARRAY(x,y)].color);
981 if (ARR(x,y) != ARR(x-1,y)) bitmap_index |= LEFT;
982 if (ARR(x,y) != ARR(x+1,y)) bitmap_index |= RIGHT;
983 if (ARR(x,y) != ARR(x,y-1)) bitmap_index |= UP;
984 if (ARR(x,y) != ARR(x,y+1)) bitmap_index |= DOWN;
985 if (ARR(x,y) != ARR(x-1,y-1)) bitmap_index |= LEFT_UP;
986 if (ARR(x,y) != ARR(x-1,y+1)) bitmap_index |= LEFT_DOWN;
987 if (ARR(x,y) != ARR(x+1,y-1)) bitmap_index |= RIGHT_UP;
988 if (ARR(x,y) != ARR(x+1,y+1)) bitmap_index |= RIGHT_DOWN;
989 (void) XPutImage(display,window,gc,
990 sp->bitmaps[bitmap_index],
992 sp->x_margin + sp->box*x,
993 sp->y_margin + sp->box*y,
998 XSetForeground(display, gc, sp->border_color);
1000 XDrawRectangle(display,window,gc,
1001 sp->x_margin-t-1,sp->y_margin-t-1,
1002 sp->box*sp->width+1+2*t, sp->box*sp->height+1+2*t);
1007 /***************************************************
1008 Routines to initialise and close down polyominoes.
1009 ***************************************************/
1011 static void free_bitmaps(polyominoesstruct *sp) {
1015 /* Don't bother to free duplicates */
1016 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
1017 sp->bitmaps[n] = None;
1018 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
1019 sp->bitmaps[n] = None;
1020 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
1021 sp->bitmaps[n] = None;
1022 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
1023 sp->bitmaps[n] = None;
1025 else if (sp->bitmaps[n] != None) {
1026 XDestroyImage(sp->bitmaps[n]);
1027 sp->bitmaps[n] = None;
1031 #define deallocate(p,t) if ((p)!=NULL) {free(p); p=(t*)NULL;}
1033 static void free_polyominoes(polyominoesstruct *sp) {
1036 for (n=0;n<sp->nr_polyominoes;n++) {
1037 deallocate(sp->polyomino[n].point, point_type);
1040 deallocate(sp->polyomino, polyomino_type);
1041 deallocate(sp->attach_list, int);
1042 deallocate(sp->rectangles, XRectangle);
1043 deallocate(sp->lines, XSegment);
1044 deallocate(sp->reason_to_not_attach, int);
1045 deallocate(sp->array, int);
1046 deallocate(sp->changed_array, int);
1051 #define set_allocate(p,type,size) p = (type *) malloc(size); \
1052 if ((p)==NULL) {free_polyominoes(sp);return 0;}
1054 #define copy_polyomino(dst,src,new_rand) \
1055 (dst).len=(src).len; \
1056 (dst).max_white = (src).max_white; \
1057 set_allocate((dst).point,point_type,sizeof(point_type)*(src).len); \
1058 (dst).len = (src).len; \
1060 random_permutation((src).len,perm_point); \
1061 for (i=0;i<(src).len;i++) \
1062 (dst).point[i] = (src).point[perm_point[i]]; \
1063 (dst).transform_len = (src).transform_len; \
1065 random_permutation((src).transform_len,perm_transform); \
1066 for (i=0;i<(src).transform_len;i++) \
1067 (dst).transform_list[i] = (src).transform_list[perm_transform[i]]; \
1071 /***************************************************
1072 Puzzle specific initialization routines.
1073 ***************************************************/
1076 int check_pentomino_puzzle(polyominoesstruct *sp) {
1077 return check_all_regions_multiple_of(sp, 5) && whites_ok(sp);
1081 int check_hexomino_puzzle(polyominoesstruct *sp) {
1082 return check_all_regions_multiple_of(sp, 6) && whites_ok(sp);
1086 int check_tetr_pentomino_puzzle(polyominoesstruct *sp) {
1087 return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp);
1091 int check_pent_hexomino_puzzle(polyominoesstruct *sp) {
1092 return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp);
1096 int check_heptomino_puzzle(polyominoesstruct *sp) {
1097 return check_all_regions_multiple_of(sp, 7) && whites_ok(sp);
1101 int check_octomino_puzzle(polyominoesstruct *sp) {
1102 return check_all_regions_multiple_of(sp, 8) && whites_ok(sp);
1106 int check_dekomino_puzzle(polyominoesstruct *sp) {
1107 return check_all_regions_multiple_of(sp, 10) && whites_ok(sp);
1111 int check_elevenomino_puzzle(polyominoesstruct *sp) {
1112 return check_all_regions_multiple_of(sp, 11) && whites_ok(sp);
1115 static struct {int len; point_type point[4];
1116 int transform_len, transform_list[8], max_white;} tetromino[5] =
1121 {4, {{0,0}, {1,0}, {2,0}, {3,0}},
1122 2, {0, 1, -1, -1, -1, -1, -1, -1}, 2},
1127 {4, {{0,0}, {1,0}, {2,0}, {2,1}},
1128 8, {0, 1, 2, 3, 4, 5, 6, 7}, 2},
1133 {4, {{0,0}, {1,0}, {1,1}, {2,0}},
1134 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1139 {4, {{0,0}, {1,0}, {1,1}, {2,1}},
1140 4, {0, 1, 4, 5, -1, -1, -1, -1}, 2},
1145 {4, {{0,0}, {0,1}, {1,0}, {1,1}},
1146 1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}};
1149 static struct pentomino_struct {int len; point_type point[5];
1150 int transform_len, transform_list[8], max_white;}
1156 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}},
1157 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1162 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}},
1163 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1168 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}},
1169 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1175 {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}},
1176 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1181 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}},
1182 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1187 {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}},
1188 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1194 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}},
1195 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1201 {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}},
1202 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1207 {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}},
1208 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1214 {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}},
1215 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1221 {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}},
1222 1, {0, -1, -1, -1, -1, -1, -1, -1}, 4},
1228 {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}},
1229 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}};
1232 static struct hexomino_struct {int len; point_type point[6];
1233 int transform_len, transform_list[8], max_white;}
1239 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}},
1240 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1245 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}},
1246 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1251 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}},
1252 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1257 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}},
1258 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1264 {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}},
1265 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1270 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}},
1271 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1276 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}},
1277 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1283 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}},
1284 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1290 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}},
1291 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1296 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}},
1297 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1303 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}},
1304 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1309 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}},
1310 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1316 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}},
1317 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1323 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}},
1324 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1329 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}},
1330 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1336 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}},
1337 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1343 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}},
1344 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1350 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}},
1351 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1357 {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1358 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1364 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1365 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1370 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}},
1371 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1377 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}},
1378 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1383 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}},
1384 4, {0, 1, 4, 5, -1, -1, -1, -1}, 4},
1390 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}},
1391 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1397 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}},
1398 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1403 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}},
1404 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1410 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}},
1411 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1417 {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}},
1418 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1423 {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}},
1424 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1430 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}},
1431 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1437 {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}},
1438 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1444 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}},
1445 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1451 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}},
1452 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1458 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}},
1459 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1465 {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}},
1466 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}};
1468 static struct pentomino_struct one_sided_pentomino[60];
1470 void make_one_sided_pentomino(void) {
1474 for (i=0;i<18;i++) {
1475 one_sided_pentomino[j] = pentomino[i];
1477 if (one_sided_pentomino[j].transform_list[t]>=4) {
1478 one_sided_pentomino[j].transform_len = t;
1480 one_sided_pentomino[j] = pentomino[i];
1481 for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u];
1482 one_sided_pentomino[j].transform_len -= t;
1489 static struct hexomino_struct one_sided_hexomino[60];
1491 void make_one_sided_hexomino(void) {
1495 for (i=0;i<35;i++) {
1496 one_sided_hexomino[j] = hexomino[i];
1498 if (one_sided_hexomino[j].transform_list[t]>=4) {
1499 one_sided_hexomino[j].transform_len = t;
1501 one_sided_hexomino[j] = hexomino[i];
1502 for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u];
1503 one_sided_hexomino[j].transform_len -= t;
1511 Find all the ways of placing all twelve pentominoes
1512 into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6.
1516 int set_pentomino_puzzle(polyominoesstruct *sp) {
1517 int perm_poly[12], perm_point[5], perm_transform[8], i, p;
1538 sp->nr_polyominoes = 12;
1539 set_allocate(sp->polyomino,polyomino_type,12*sizeof(polyomino_type));
1540 random_permutation(12,perm_poly);
1541 for (p=0;p<12;p++) {
1542 copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1);
1545 sp->check_ok = check_pentomino_puzzle;
1551 Many of the following puzzles are inspired by
1552 http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
1556 Find all the ways of placing all eighteen one-sided pentominoes
1561 int set_one_sided_pentomino_puzzle(polyominoesstruct *sp) {
1562 int perm_poly[18], perm_point[5], perm_transform[8], i, p;
1564 make_one_sided_pentomino();
1585 sp->nr_polyominoes = 18;
1586 set_allocate(sp->polyomino,polyomino_type,18*sizeof(polyomino_type));
1587 random_permutation(18,perm_poly);
1588 for (p=0;p<18;p++) {
1589 copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1);
1592 sp->check_ok = check_pentomino_puzzle;
1598 Find all the ways of placing all sixty one-sided hexominoes
1603 int set_one_sided_hexomino_puzzle(polyominoesstruct *sp) {
1604 int perm_poly[60], perm_point[6], perm_transform[8], i, p;
1606 make_one_sided_hexomino();
1643 sp->nr_polyominoes = 60;
1644 set_allocate(sp->polyomino,polyomino_type,60*sizeof(polyomino_type));
1645 random_permutation(60,perm_poly);
1646 for (p=0;p<60;p++) {
1647 copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1);
1650 sp->check_ok = check_hexomino_puzzle;
1656 Find all the ways of placing all five tetrominoes and all twelve
1657 pentominoes into a rectangle.
1661 int set_tetr_pentomino_puzzle(polyominoesstruct *sp) {
1662 int perm_poly[17], perm_point[5], perm_transform[8], i, p;
1679 sp->nr_polyominoes = 17;
1680 set_allocate(sp->polyomino,polyomino_type,17*sizeof(polyomino_type));
1681 random_permutation(17,perm_poly);
1683 copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1);
1685 for (p=0;p<12;p++) {
1686 copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1);
1689 sp->check_ok = check_tetr_pentomino_puzzle;
1694 Find all the ways of placing all twelve pentominoes and all thirty five
1695 hexominoes into a rectangle whose size is 18x15.
1699 int set_pent_hexomino_puzzle(polyominoesstruct *sp) {
1700 int perm_poly[47], perm_point[6], perm_transform[8], i, p;
1725 sp->nr_polyominoes = 47;
1726 set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type));
1727 random_permutation(47,perm_poly);
1728 for (p=0;p<12;p++) {
1729 copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1);
1731 for (p=0;p<35;p++) {
1732 copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1);
1735 sp->check_ok = check_pent_hexomino_puzzle;
1743 Science News September 20, 1986 Vol 130, No 12
1744 Science News November 14, 1987 Vol 132, Pg 310
1750 **** fills a 10x5 rectangle
1754 static struct {int len; point_type point[5];
1755 int transform_len, transform_list[8], max_white;} pentomino1 =
1756 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}},
1757 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3};
1760 int set_pentomino_puzzle1(polyominoesstruct *sp) {
1761 int perm_point[5], perm_transform[8], i, p;
1766 sp->nr_polyominoes = 10;
1767 set_allocate(sp->polyomino,polyomino_type,10*sizeof(polyomino_type));
1768 for (p=0;p<10;p++) {
1769 copy_polyomino(sp->polyomino[p],pentomino1,1);
1772 sp->check_ok = check_pentomino_puzzle;
1780 ***** fills a 24x23 rectangle
1784 static struct {int len; point_type point[6];
1785 int transform_len, transform_list[8], max_white;} hexomino1 =
1786 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}},
1787 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1790 int set_hexomino_puzzle1(polyominoesstruct *sp) {
1791 int perm_point[6], perm_transform[8], i, p;
1796 sp->nr_polyominoes = 92;
1797 set_allocate(sp->polyomino,polyomino_type,92*sizeof(polyomino_type));
1798 for (p=0;p<92;p++) {
1799 copy_polyomino(sp->polyomino[p],hexomino1,1);
1802 sp->check_ok = check_hexomino_puzzle;
1810 ***** fills a 21x26 rectangle
1812 (All solutions have 180 degree rotational symmetry)
1816 static struct {int len; point_type point[7];
1817 int transform_len, transform_list[8], max_white;} heptomino1 =
1818 {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}},
1819 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1822 int set_heptomino_puzzle1(polyominoesstruct *sp) {
1823 int perm_point[7], perm_transform[8], i, p;
1830 sp->nr_polyominoes = 78;
1831 set_allocate(sp->polyomino,polyomino_type,78*sizeof(polyomino_type));
1832 for (p=0;p<78;p+=2) {
1833 copy_polyomino(sp->polyomino[p],heptomino1,1);
1834 copy_polyomino(sp->polyomino[p+1],heptomino1,0);
1837 sp->check_ok = check_heptomino_puzzle;
1842 /* The following puzzles from
1843 Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition
1844 by Solomon W. Golomb Princeton University Press 1994
1850 ***** fills a 28x19 rectangle
1854 int set_heptomino_puzzle2(polyominoesstruct *sp) {
1855 int perm_point[7], perm_transform[8], i, p;
1860 sp->nr_polyominoes = 76;
1861 set_allocate(sp->polyomino,polyomino_type,76*sizeof(polyomino_type));
1862 for (p=0;p<76;p++) {
1863 copy_polyomino(sp->polyomino[p],heptomino1,1);
1866 sp->check_ok = check_heptomino_puzzle;
1874 **** fills a 25x22 rectangle
1879 static struct {int len; point_type point[11];
1880 int transform_len, transform_list[8], max_white;} elevenomino1 =
1881 {11, {{0,0}, {1,0}, {2,0},
1882 {0,1}, {1,1}, {2,1}, {3,1},
1883 {0,2}, {1,2}, {2,2}, {3,2}},
1884 8, {0, 1, 2, 3, 4, 5, 6, 7}, 6};
1887 int set_elevenomino_puzzle1(polyominoesstruct *sp) {
1888 int perm_point[11], perm_transform[8], i, p;
1895 sp->nr_polyominoes = 50;
1896 set_allocate(sp->polyomino,polyomino_type,50*sizeof(polyomino_type));
1897 for (p=0;p<50;p+=2) {
1898 copy_polyomino(sp->polyomino[p],elevenomino1,1);
1899 copy_polyomino(sp->polyomino[p+1],elevenomino1,0);
1902 sp->check_ok = check_elevenomino_puzzle;
1911 **** fills 32 x 30 rectangle
1916 static struct {int len; point_type point[10];
1917 int transform_len, transform_list[8], max_white;} dekomino1 =
1920 {0,1}, {1,1}, {2,1}, {3,1},
1921 {0,2}, {1,2}, {2,2}, {3,2}},
1922 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1925 int set_dekomino_puzzle1(polyominoesstruct *sp) {
1926 int perm_point[10], perm_transform[8], i, p;
1931 sp->nr_polyominoes = 96;
1932 set_allocate(sp->polyomino,polyomino_type,96*sizeof(polyomino_type));
1933 for (p=0;p<96;p++) {
1934 copy_polyomino(sp->polyomino[p],dekomino1,1);
1937 sp->check_ok = check_dekomino_puzzle;
1945 *** fills 96 x 26 rectangle
1950 static struct {int len; point_type point[10];
1951 int transform_len, transform_list[8], max_white;} octomino1 =
1953 {0,1}, {1,1}, {2,1},
1954 {0,2}, {1,2}, {2,2}, {3,2}},
1955 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1958 int set_octomino_puzzle1(polyominoesstruct *sp) {
1959 int perm_point[8], perm_transform[8], i, p;
1964 sp->nr_polyominoes = 312;
1965 set_allocate(sp->polyomino,polyomino_type,312*sizeof(polyomino_type));
1966 for (p=0;p<312;p++) {
1967 copy_polyomino(sp->polyomino[p],octomino1,1);
1970 sp->check_ok = check_octomino_puzzle;
1977 * fills 15 x 15 rectangle
1983 int set_pentomino_puzzle2(polyominoesstruct *sp) {
1984 int perm_point[5], perm_transform[8], i, p;
1989 sp->nr_polyominoes = 45;
1990 set_allocate(sp->polyomino,polyomino_type,45*sizeof(polyomino_type));
1991 for (p=0;p<45;p++) {
1992 copy_polyomino(sp->polyomino[p],pentomino1,1);
1995 sp->check_ok = check_pentomino_puzzle;
2003 **** fills a 47x33 rectangle
2009 int set_elevenomino_puzzle2(polyominoesstruct *sp) {
2010 int perm_point[11], perm_transform[8], i, p;
2015 sp->nr_polyominoes = 141;
2016 set_allocate(sp->polyomino,polyomino_type,141*sizeof(polyomino_type));
2017 for (p=0;p<141;p++) {
2018 copy_polyomino(sp->polyomino[p],elevenomino1,1);
2021 sp->check_ok = check_elevenomino_puzzle;
2026 /**************************************************
2028 **************************************************/
2030 #define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes(sp); return;}
2033 init_polyominoes(ModeInfo * mi) {
2034 polyominoesstruct *sp;
2039 if (polyominoeses == NULL) {
2041 = (polyominoesstruct *) calloc(MI_NUM_SCREENS(mi),sizeof (polyominoesstruct)))
2045 sp = &polyominoeses[MI_SCREEN(mi)];
2047 free_polyominoes(sp);
2052 if (MI_IS_FULLRANDOM(mi)) {
2053 sp->identical = (Bool) (LRAND() & 1);
2054 sp->use3D = (Bool) (NRAND(4));
2056 sp->identical = identical;
2059 if (sp->identical) {
2062 if (!set_pentomino_puzzle1(sp))
2066 if (!set_hexomino_puzzle1(sp))
2070 if (!set_heptomino_puzzle1(sp))
2074 if (!set_heptomino_puzzle2(sp))
2078 if (!set_elevenomino_puzzle1(sp))
2082 if (!set_dekomino_puzzle1(sp))
2086 if (!set_octomino_puzzle1(sp))
2090 if (!set_pentomino_puzzle2(sp))
2094 if (!set_elevenomino_puzzle2(sp))
2101 if (!set_pentomino_puzzle(sp))
2105 if (!set_one_sided_pentomino_puzzle(sp))
2109 if (!set_one_sided_hexomino_puzzle(sp))
2113 if (!set_pent_hexomino_puzzle(sp))
2117 if (!set_tetr_pentomino_puzzle(sp))
2123 allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int));
2124 sp->nr_attached = 0;
2126 if (sp->identical) {
2127 allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int));
2130 allocate(sp->array,int,sp->width*sp->height*sizeof(int));
2131 allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int));
2132 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1;
2134 sp->left_right = NRAND(2);
2135 sp->top_bottom = NRAND(2);
2137 box1 = MI_WIDTH(mi)/(sp->width+2);
2138 box2 = MI_HEIGHT(mi)/(sp->height+2);
2144 if (sp->box >= 12) {
2145 sp->box = (sp->box/12)*12;
2146 create_bitmaps(mi,sp);
2147 if (!sp->use_bitmaps)
2151 sp->use_bitmaps = 0;
2153 if (!sp->use_bitmaps) {
2154 allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle));
2155 allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment));
2158 allocate(perm,int,sp->nr_polyominoes*sizeof(int));
2159 random_permutation(sp->nr_polyominoes, perm);
2160 sp->mono = MI_NPIXELS(mi) < 12;
2161 start = NRAND(MI_NPIXELS(mi));
2162 for (i=0;i<sp->nr_polyominoes;i++)
2164 sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi));
2166 sp->polyomino[i+1].color = sp->polyomino[i].color;
2172 sp->polyomino[i].color = MI_WHITE_PIXEL(mi);
2174 sp->polyomino[i].color = MI_BLACK_PIXEL(mi);
2177 if (sp->use_bitmaps) {
2179 sp->border_color = MI_WHITE_PIXEL(mi);
2181 sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi)));
2184 sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2;
2185 sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2;
2189 /* Clear the background. */
2195 draw_polyominoes(ModeInfo * mi) {
2196 polyominoesstruct *sp;
2197 int poly_no,point_no,transform_index,done,another_attachment_try;
2198 point_type attach_point;
2201 if (polyominoeses == NULL)
2203 sp = &polyominoeses[MI_SCREEN(mi)];
2205 if (MI_CYCLES(mi) != 0) {
2206 if (++sp->counter > MI_CYCLES(mi)) {
2208 erase_full_window(MI_DISPLAY(mi), MI_WINDOW(mi));
2209 #endif /* STANDALONE */
2210 init_polyominoes(mi);
2217 erase_full_window(MI_DISPLAY(mi), MI_WINDOW(mi));
2218 #endif /* STANDALONE */
2219 init_polyominoes(mi);
2223 MI_IS_DRAWN(mi) = True;
2225 if (sp->wait>0) return;
2227 memset(sp->changed_array,0,sp->width*sp->height*sizeof(int));
2229 poly_no = first_poly_no(sp);
2231 transform_index = 0;
2233 another_attachment_try = 1;
2234 find_blank(sp,&attach_point);
2235 if (sp->identical && sp->nr_attached < sp->nr_polyominoes)
2236 memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int));
2238 if (sp->nr_attached < sp->nr_polyominoes) {
2239 while (!done && another_attachment_try) {
2240 done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0));
2241 if (done && sp->rot180) {
2242 poly_no = first_poly_no(sp);
2243 done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0));
2245 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2248 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2252 if (sp->identical) {
2254 if (sp->nr_attached == 0)
2257 detach_until=sp->nr_attached-1;
2258 if (sp->nr_attached < sp->nr_polyominoes)
2259 while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0)
2261 while (sp->nr_attached>detach_until) {
2263 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2264 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2265 if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes)
2266 for (i=0;i<sp->nr_polyominoes;i++)
2267 REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i);
2269 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2275 if (sp->nr_attached == 0)
2279 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2280 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2282 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2287 if (sp->use_bitmaps)
2288 draw_with_bitmaps(mi,sp);
2290 draw_without_bitmaps(mi,sp);
2292 if (sp->nr_attached == sp->nr_polyominoes)
2299 release_polyominoes(ModeInfo * mi) {
2302 if (polyominoeses != NULL) {
2303 for (screen=0;screen<MI_NUM_SCREENS(mi); screen++)
2304 free_polyominoes(&polyominoeses[screen]);
2305 (void) free((void *) polyominoeses);
2306 polyominoeses = (polyominoesstruct *) NULL;
2311 refresh_polyominoes(ModeInfo * mi) {
2315 #endif /* MODE_polyominoes */