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 release_polyominoes 0
43 # define polyominoes_handle_event 0
44 # define SMOOTH_COLORS
45 # include "xlockmore.h" /* in xscreensaver distribution */
47 #else /* STANDALONE */
48 # include "xlock.h" /* in xlockmore distribution */
49 #endif /* STANDALONE */
51 #ifdef MODE_polyominoes
52 #define DEF_IDENTICAL "False"
53 #define DEF_PLAIN "False"
55 static Bool identical;
59 #define countof(x) (sizeof((x))/sizeof((*x)))
61 static XrmOptionDescRec opts[] =
63 {"-identical", ".polyominoes.identical", XrmoptionNoArg, "on"},
64 {"+identical", ".polyominoes.identical", XrmoptionNoArg, "off"},
65 {"-plain", ".polyominoes.plain", XrmoptionNoArg, "on"},
66 {"+plain", ".polyominoes.plain", XrmoptionNoArg, "off"}
68 static argtype vars[] =
70 {&identical, "identical", "Identical", DEF_IDENTICAL, t_Bool},
71 {&plain, "plain", "Plain", DEF_PLAIN, t_Bool}
73 static OptionStruct desc[] =
75 {"-/+identical", "turn on/off puzzles where the polyomino pieces are identical"},
76 {"-/+plain", "turn on/off plain pieces"}
79 ENTRYPOINT ModeSpecOpt polyominoes_opts =
80 {sizeof opts / sizeof opts[0], opts,
81 sizeof vars / sizeof vars[0], vars, desc};
84 ModStruct polyominoes_description = {
85 "polyominoes", "init_polyominoes", "draw_polyominoes", (char *) NULL,
86 "refresh_polyominoes", "init_polyominoes", (char *) NULL, &polyominoes_opts,
87 6000, 1, 8192, 1, 64, 1.0, "",
88 "Shows attempts to place polyominoes into a rectangle", 0, NULL
93 /* Each polyomino is described by several quantities:
94 len: the number of squares in the polyomino;
95 point: the list of points;
96 tranform_len: the number of items in transform_list;
97 transform_list: a list of transformations that need to be done in order
98 to get all rotations and reflections (see the function
100 max_white: the maximum number of white squares covered if polyomino
101 is placed on a chess board;
102 color: it's display color;
103 attached: whether it is currently attached to the rectangle;
104 attach_point: point on rectangle where attached;
105 point_no: the number of the point where it is attached;
106 transform_index: which element of transform_list is currently being used.
109 typedef struct {int x,y;} point_type;
111 typedef struct {int len; point_type *point;
112 int transform_len, transform_list[8], max_white;
115 point_type attach_point;
116 int point_no, transform_index;} polyomino_type;
119 typedef struct _polyominoesstruct{
123 unsigned border_color;
126 polyomino_type *polyomino;
128 Bool identical, use3D;
132 /* The array that tells where the polyominoes are attached. */
133 int *array, *changed_array;
135 /* These specify the dimensions of how things appear on the screen. */
136 int box, x_margin, y_margin;
138 /* These booleans decide in which way to try to attach the polyominoes. */
139 int left_right, top_bottom;
141 /* Bitmaps for display purposes. */
143 XImage *bitmaps[256];
145 /* Structures used for display purposes if there is not enough memory
146 to allocate bitmaps (or if the screen is small). */
148 XRectangle *rectangles;
150 /* A procedure that may be used to see if certain configurations
152 int (*check_ok)(struct _polyominoesstruct *sp);
154 /* Tells program that solutions are invariant under 180 degree
158 /* This is a variable used in the case that all the polyominoes are identical
159 that will further prune the search tree. Essentially it will be
160 int reason_to_not_attach[nr_polynominoes][nr_polynominoes];
161 Let me first explain the effect it is trying to overcome. Often
162 in the search process, the computer will first try to fit shapes into
163 a region (call it A), and then into another region (call it B) that is
164 essentially disjoint from A. But it may be that it just is not possible
165 to fit shapes into region B. So it fits something into A, and then
166 tries to fit something into B. Failing it fits something else into A,
167 and then tried again to fit something into B. Thus the program is trying
168 again and again to fit something into B, when it should have figured out
169 the first time that it was impossible.
171 To overcome this, everytime we try to attach a piece, we collect the reasons
172 why it cannot be attached (a boolean for each piece that got in the way).
173 If we see that a piece cannot be attached, we detach the other pieces until
174 we have detached at least one piece for which the boolean reason_to_not_attach
177 int *reason_to_not_attach;
182 eraser_state *eraser;
186 #define ARRAY(x,y) (sp->array[(x)*sp->height+(y)])
187 #define CHANGED_ARRAY(x,y) (sp->changed_array[(x)*sp->height+(y)])
188 #define ARRAY_P(p) (sp->array[(p).x*sp->height+(p).y])
189 #define CHANGED_ARRAY_P(p) (sp->changed_array[(p).x*sp->height+(p).y])
190 #define ARR(x,y) (((x)<0||(x)>=sp->width||(y)<0||(y)>=sp->height)?-2:ARRAY(x,y))
192 #define REASON_TO_NOT_ATTACH(x,y) (sp->reason_to_not_attach[(x)*sp->nr_polyominoes+(y)])
194 #define ROUND8(n) ((((n)+7)/8)*8)
196 /* Defines to index the bitmaps. A set bit indicates that an edge or
197 corner is required. */
202 #define LEFT_UP (1<<4)
203 #define LEFT_DOWN (1<<5)
204 #define RIGHT_UP (1<<6)
205 #define RIGHT_DOWN (1<<7)
206 #define IS_LEFT(n) ((n) & LEFT)
207 #define IS_RIGHT(n) ((n) & RIGHT)
208 #define IS_UP(n) ((n) & UP)
209 #define IS_DOWN(n) ((n) & DOWN)
210 #define IS_LEFT_UP(n) ((n) & LEFT_UP)
211 #define IS_LEFT_DOWN(n) ((n) & LEFT_DOWN)
212 #define IS_RIGHT_UP(n) ((n) & RIGHT_UP)
213 #define IS_RIGHT_DOWN(n) ((n) & RIGHT_DOWN)
215 /* Defines to access the bitmaps. */
216 #define BITNO(x,y) ((x)+(y)*ROUND8(sp->box))
217 #define SETBIT(n,x,y) {data[BITNO(x,y)/8] |= 1<<(BITNO(x,y)%8);}
218 #define RESBIT(n,x,y) {data[BITNO(x,y)/8] &= ~(1<<(BITNO(x,y)%8));}
219 #define TWOTHIRDSBIT(n,x,y) {if ((x+y-1)%3) SETBIT(n,x,y) else RESBIT(n,x,y)}
220 #define HALFBIT(n,x,y) {if ((x-y)%2) SETBIT(n,x,y) else RESBIT(n,x,y)}
221 #define THIRDBIT(n,x,y) {if (!((x-y-1)%3)) SETBIT(n,x,y) else RESBIT(n,x,y)}
222 #define THREEQUARTERSBIT(n,x,y) \
223 {if ((y%2)||((x+2+y/2+1)%2)) SETBIT(n,x,y) else RESBIT(n,x,y)}
224 #define NOTHALFBIT(n,x,y) {if ((x-y)%2) RESBIT(n,x,y) else SETBIT(n,x,y)}
226 /* Parameters for bitmaps. */
227 #define G ((sp->box/45)+1) /* 1/2 of gap between polyominoes. */
228 #define T ((sp->box<=12)?1:(G*2)) /* Thickness of walls of polyominoes. */
229 #define R ((sp->box<=12)?1:(G*6)) /* Amount of rounding. */
230 #define RT ((sp->box<=12)?1:(G*3)) /* Thickness of wall of rounded parts.
231 Here 3 is an approximation to 2 sqrt(2). */
232 #define RR 0 /* Roof ridge thickness */
235 /* A list of those bitmaps we need to create to display any pentomino. */
236 /* (not used right now because it does not seem to work for hexonimoes.) */
238 static int bitmaps_needed[] =
240 LEFT_UP|LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
242 LEFT|RIGHT_UP|RIGHT_DOWN,
243 RIGHT|LEFT_UP|LEFT_DOWN,
244 UP|LEFT_DOWN|RIGHT_DOWN,
245 DOWN|LEFT_UP|RIGHT_UP,
255 /* These needed for hexonimoes*/
260 LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
261 LEFT_UP|RIGHT_UP|RIGHT_DOWN,
262 LEFT_UP|LEFT_DOWN|RIGHT_DOWN,
263 LEFT_UP|LEFT_DOWN|RIGHT_UP,
285 static int bitmap_needed(int n)
289 for (i=0;bitmaps_needed[i]!=-1;i++)
290 if (n == bitmaps_needed[i])
297 /* Some debugging routines.
299 static void print_board(polyominoesstruct *sp)
302 for (y=0;y<sp->height;y++) {
303 for (x=0;x<sp->width;x++)
304 if (ARRAY(x,y) == -1)
307 fprintf(stderr,"%c",'a'+ARRAY(x,y));
308 fprintf(stderr,"\n");
310 fprintf(stderr,"\n");
313 static void print_points(point_type *point, int len)
318 fprintf(stderr,"(%d %d) ",point[i].x,point[i].y);
321 static void print_polyomino(polyomino_type poly)
325 print_points(poly.point,poly.len);
326 fprintf(stderr,"\n");
327 for (i=0;i<poly.transform_len;i++)
328 fprintf(stderr,"%d ",poly.transform_list[i]);
329 fprintf(stderr,"\n");
333 static polyominoesstruct *polyominoeses = (polyominoesstruct *) NULL;
336 void random_permutation(int n, int a[])
340 for (i=0;i<n;i++) a[i] = -1;
354 /************************************************************
355 These are the routines for manipulating the polyominoes and
356 attaching and detaching them from the rectangle.
357 ************************************************************/
359 static void transform(point_type in, point_type offset, int transform_no,
360 point_type attach_point, point_type *out) {
361 switch (transform_no) {
362 case 0: out->x=in.x-offset.x+attach_point.x;
363 out->y=in.y-offset.y+attach_point.y;
365 case 1: out->x=-(in.y-offset.y)+attach_point.x;
366 out->y=in.x-offset.x+attach_point.y;
368 case 2: out->x=-(in.x-offset.x)+attach_point.x;
369 out->y=-(in.y-offset.y)+attach_point.y;
371 case 3: out->x=in.y-offset.y+attach_point.x;
372 out->y=-(in.x-offset.x)+attach_point.y;
374 case 4: out->x=-(in.x-offset.x)+attach_point.x;
375 out->y=in.y-offset.y+attach_point.y;
377 case 5: out->x=in.y-offset.y+attach_point.x;
378 out->y=in.x-offset.x+attach_point.y;
380 case 6: out->x=in.x-offset.x+attach_point.x;
381 out->y=-(in.y-offset.y)+attach_point.y;
383 case 7: out->x=-(in.y-offset.y)+attach_point.x;
384 out->y=-(in.x-offset.x)+attach_point.y;
389 static int first_poly_no(polyominoesstruct *sp)
394 while(poly_no<sp->nr_polyominoes && sp->polyomino[poly_no].attached)
399 static void next_poly_no(polyominoesstruct *sp, int *poly_no)
403 *poly_no = sp->nr_polyominoes;
407 } while (*poly_no<sp->nr_polyominoes && sp->polyomino[*poly_no].attached);
411 /* check_all_regions_multiple_of looks for connected regions of
412 blank spaces, and returns 0 if it finds a connected region containing
413 a number of blanks that is not a multiple of n.
416 static void count_adjacent_blanks(polyominoesstruct *sp, int *count, int x, int y, int blank_mark)
419 if (ARRAY(x,y) == -1) {
421 ARRAY(x,y) = blank_mark;
422 if (x>=1) count_adjacent_blanks(sp, count,x-1,y,blank_mark);
423 if (x<sp->width-1) count_adjacent_blanks(sp, count,x+1,y,blank_mark);
424 if (y>=1) count_adjacent_blanks(sp, count,x,y-1,blank_mark);
425 if (y<sp->height-1) count_adjacent_blanks(sp, count,x,y+1,blank_mark);
429 static int check_all_regions_multiple_of(polyominoesstruct *sp, int n)
431 int x,y,count,good = 1;
433 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
435 count_adjacent_blanks(sp, &count,x,y,-2);
439 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
440 if (ARRAY(x,y) == -2)
446 static int check_all_regions_positive_combination_of(polyominoesstruct *sp, int m, int n)
448 int x,y,count,good = 1;
450 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
452 count_adjacent_blanks(sp, &count,x,y,-2);
454 for (;count>=0 && !good;count-=m)
458 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
459 if (ARRAY(x,y) == -2)
465 static int find_smallest_blank_component(polyominoesstruct *sp)
467 int x,y,size,smallest_size,blank_mark,smallest_mark;
469 smallest_mark = blank_mark = -10;
470 smallest_size = 1000000000;
471 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y) == -1) {
473 count_adjacent_blanks(sp, &size,x,y,blank_mark);
474 if (size<smallest_size) {
475 smallest_mark = blank_mark;
476 smallest_size = size;
481 return smallest_mark;
484 /* "Chess board" check - see init_max_whites_list above for more details.
486 /* If the rectangle is alternatively covered by white and black
487 squares (chess board style), then this gives the list of
488 the maximal possible whites covered by each polyomino. It
489 is used by the function whites_ok which makes sure that the
490 array has a valid number of white or black remaining blanks left.
493 static int whites_ok(polyominoesstruct *sp)
495 int x,y,poly_no,whites=0,blacks=0,max_white=0,min_white=0;
497 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
498 if (ARRAY(x,y) == -1 && (x+y)%2) whites++;
499 if (ARRAY(x,y) == -1 && (x+y+1)%2) blacks++;
501 for (poly_no=0;poly_no<sp->nr_polyominoes;poly_no++) if (!sp->polyomino[poly_no].attached) {
502 max_white += sp->polyomino[poly_no].max_white;
503 min_white += sp->polyomino[poly_no].len - sp->polyomino[poly_no].max_white;
505 return (min_white <= blacks && min_white <= whites
506 && blacks <= max_white && whites <= max_white);
509 /* This routine looks at the point (x,y) and sees how many polyominoes
510 and all their various transforms may be attached there.
514 score_point(polyominoesstruct *sp, int x, int y, int min_score_so_far)
516 int poly_no, point_no, transform_index, i, attachable;
517 point_type attach_point = { 0, 0 }, target_point = { 0, 0 };
520 if (x>=1 && x<sp->width-1 && y>=1 && y<sp->height-1 &&
521 ARRAY(x-1,y-1)<0 && ARRAY(x-1,y)<0 && ARRAY(x-1,y+1)<0 &&
522 ARRAY(x+1,y-1)<0 && ARRAY(x+1,y)<0 && ARRAY(x+1,y+1)<0 &&
523 ARRAY(x,y-1)<0 && ARRAY(x,y+1)<0)
528 for (poly_no=first_poly_no(sp);poly_no<sp->nr_polyominoes;next_poly_no(sp,&poly_no))
529 if (!sp->polyomino[poly_no].attached) {
530 for (point_no=0;point_no<sp->polyomino[poly_no].len;point_no++)
531 for (transform_index=0;transform_index<sp->polyomino[poly_no].transform_len;transform_index++) {
533 for (i=0;i<sp->polyomino[poly_no].len;i++) {
534 transform(sp->polyomino[poly_no].point[i],
535 sp->polyomino[poly_no].point[point_no],
536 sp->polyomino[poly_no].transform_list[transform_index],
537 attach_point, &target_point);
538 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
539 && (target_point.y>=0) && (target_point.y<sp->height)
540 && (ARRAY_P(target_point)<0))) {
547 if (score>=min_score_so_far)
556 static void find_blank(polyominoesstruct *sp, point_type *point)
558 int score, worst_score;
562 blank_mark = find_smallest_blank_component(sp);
564 worst_score = 1000000;
565 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y)==blank_mark) {
566 score = 100*score_point(sp,x,y,worst_score);
568 if (sp->left_right) score += 10*x;
569 else score += 10*(sp->width-1-x);
570 if (sp->top_bottom) score += y;
571 else score += (sp->height-1-y);
573 if (score<worst_score) {
580 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
581 if (ARRAY(x,y)<0) ARRAY(x,y) = -1;
584 /* Detaches the most recently attached polyomino. */
587 void detach(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index, point_type *attach_point, int rot180)
590 point_type target_point = { 0, 0 };
592 if (sp->nr_attached == 0) return;
594 *poly_no = sp->attach_list[sp->nr_attached];
595 *point_no = sp->polyomino[*poly_no].point_no;
596 *transform_index = sp->polyomino[*poly_no].transform_index;
597 *attach_point = sp->polyomino[*poly_no].attach_point;
598 for (i=0;i<sp->polyomino[*poly_no].len;i++) {
599 transform(sp->polyomino[*poly_no].point[i],
600 sp->polyomino[*poly_no].point[*point_no],
601 sp->polyomino[*poly_no].transform_list[*transform_index]^(rot180<<1),
602 *attach_point, &target_point);
603 ARRAY_P(target_point) = -1;
604 CHANGED_ARRAY_P(target_point) = 1;
607 sp->polyomino[*poly_no].attached = 0;
610 /* Attempts to attach a polyomino at point (x,y) at the
611 point_no-th point of that polyomino, using the transform
612 transform_no. Returns 1 if successful.
616 int attach(polyominoesstruct *sp, int poly_no, int point_no, int transform_index, point_type attach_point, int rot180,
617 int *reason_to_not_attach) {
618 point_type target_point = { 0, 0 };
620 int attachable = 1, worst_reason_not_to_attach = 1000000000;
623 attach_point.x = sp->width-1-attach_point.x;
624 attach_point.y = sp->height-1-attach_point.y;
627 if (sp->polyomino[poly_no].attached)
630 for (i=0;i<sp->polyomino[poly_no].len;i++) {
631 transform(sp->polyomino[poly_no].point[i],
632 sp->polyomino[poly_no].point[point_no],
633 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
634 attach_point, &target_point);
635 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
636 && (target_point.y>=0) && (target_point.y<sp->height)
637 && (ARRAY_P(target_point) == -1))) {
640 if ((target_point.x>=0) && (target_point.x<sp->width)
641 && (target_point.y>=0) && (target_point.y<sp->height)
642 && (ARRAY_P(target_point) >= 0)
643 && (ARRAY_P(target_point)<worst_reason_not_to_attach))
644 worst_reason_not_to_attach = ARRAY_P(target_point);
651 if (sp->identical && !attachable) {
652 if (worst_reason_not_to_attach < 1000000000)
653 reason_to_not_attach[worst_reason_not_to_attach] = 1;
657 for (i=0;i<sp->polyomino[poly_no].len;i++) {
658 transform(sp->polyomino[poly_no].point[i],
659 sp->polyomino[poly_no].point[point_no],
660 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
661 attach_point, &target_point);
662 ARRAY_P(target_point) = poly_no;
663 CHANGED_ARRAY_P(target_point) = 1;
666 sp->attach_list[sp->nr_attached] = poly_no;
669 sp->polyomino[poly_no].attached = 1;
670 sp->polyomino[poly_no].point_no = point_no;
671 sp->polyomino[poly_no].attach_point = attach_point;
672 sp->polyomino[poly_no].transform_index = transform_index;
674 if (!sp->check_ok(sp)) {
675 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,rot180);
683 int next_attach_try(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index)
686 (*transform_index)++;
687 if (*transform_index>=sp->polyomino[*poly_no].transform_len) {
688 *transform_index = 0;
690 if (*point_no>=sp->polyomino[*poly_no].len) {
692 next_poly_no(sp,poly_no);
693 if (*poly_no>=sp->nr_polyominoes) {
694 *poly_no = first_poly_no(sp);
703 /*******************************************************
705 *******************************************************/
708 draw_without_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
710 Display *display = MI_DISPLAY(mi);
711 Window window = MI_WINDOW(mi);
713 int x,y,poly_no,nr_lines,nr_rectangles;
715 XSetLineAttributes(display,gc,sp->box/10+1,LineSolid,CapRound,JoinRound);
717 for (poly_no=-1;poly_no<sp->nr_polyominoes;poly_no++) {
719 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
720 if (CHANGED_ARRAY(x,y) && ARRAY(x,y) == poly_no) {
721 sp->rectangles[nr_rectangles].x = sp->x_margin + sp->box*x;
722 sp->rectangles[nr_rectangles].y = sp->y_margin + sp->box*y;
723 sp->rectangles[nr_rectangles].width = sp->box;
724 sp->rectangles[nr_rectangles].height = sp->box;
728 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
730 XSetForeground(display, gc, sp->polyomino[poly_no].color);
731 XFillRectangles(display, window, gc, sp->rectangles, nr_rectangles);
734 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
737 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
738 if (ARRAY(x,y) == -1 && ARRAY(x+1,y) == -1
739 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x+1,y))) {
740 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
741 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
742 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
743 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
747 XDrawSegments(display, window, gc, sp->lines, nr_lines);
750 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
751 if (ARRAY(x,y) == -1 && ARRAY(x,y+1) == -1
752 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x,y+1))) {
753 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
754 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
755 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
756 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
760 XDrawSegments(display, window, gc, sp->lines, nr_lines);
762 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
763 XDrawRectangle(display, window, gc, sp->x_margin, sp->y_margin, sp->box*sp->width, sp->box*sp->height);
765 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
768 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
769 if (ARRAY(x+1,y) != ARRAY(x,y)) {
770 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
771 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
772 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
773 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
777 XDrawSegments(display, window, gc, sp->lines, nr_lines);
780 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
781 if (ARRAY(x,y+1) != ARRAY(x,y)) {
782 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
783 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
784 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
785 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
789 XDrawSegments(display, window, gc, sp->lines, nr_lines);
790 XSetLineAttributes(display,gc,1,LineSolid,CapRound,JoinRound);
793 static void create_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
798 for (n=0;n<countof(sp->bitmaps);n++) {
800 /* Avoid duplication of identical bitmaps. */
801 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
802 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_UP];
803 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
804 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_DOWN];
805 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
806 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_UP];
807 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
808 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_DOWN];
810 else /* if (bitmap_needed(n)) */ {
811 data = (char *) malloc(sizeof(char)*(sp->box*ROUND8(sp->box)/8));
817 for (y=0;y<sp->box;y++) for (x=0;x<sp->box;x++) {
819 #ifdef SMALL_BELLYBUTTON
820 if (x >= sp->box / 2 && x <= sp->box / 2 + 1 &&
821 y >= sp->box / 2 && y <= sp->box / 2 + 1)
826 } else if ((x>=y && x<=sp->box-y-1 && IS_UP(n))
827 || (x<=y && x<=sp->box-y-1 && y<sp->box/2 && !IS_LEFT(n))
828 || (x>=y && x>=sp->box-y-1 && y<sp->box/2 && !IS_RIGHT(n)))
830 else if ((x<=y && x<=sp->box-y-1 && IS_LEFT(n))
831 || (x>=y && x<=sp->box-y-1 && x<sp->box/2 && !IS_UP(n))
832 || (x<=y && x>=sp->box-y-1 && x<sp->box/2 && !IS_DOWN(n)))
834 else if ((x>=y && x>=sp->box-y-1 && IS_RIGHT(n))
835 || (x>=y && x<=sp->box-y-1 && x>=sp->box/2 && !IS_UP(n))
836 || (x<=y && x>=sp->box-y-1 && x>=sp->box/2 && !IS_DOWN(n)))
838 else if ((x<=y && x>=sp->box-y-1 && IS_DOWN(n))
839 || (x<=y && x<=sp->box-y-1 && y>=sp->box/2 && !IS_LEFT(n))
840 || (x>=y && x>=sp->box-y-1 && y>=sp->box/2 && !IS_RIGHT(n)))
845 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
848 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
849 SETBIT(n,sp->box-1-x,y)
851 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
854 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
855 SETBIT(n,x,sp->box-1-y)
857 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
860 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
861 RESBIT(n,sp->box-1-x,y)
863 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
866 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
867 RESBIT(n,x,sp->box-1-y)
869 if (IS_LEFT(n) && IS_UP(n))
871 for (y=G;y<=R+2*G-x;y++) {
877 if (IS_LEFT(n) && IS_DOWN(n))
879 for (y=G;y<=R+2*G-x;y++) {
881 SETBIT(n,x,sp->box-1-y)
883 RESBIT(n,x,sp->box-1-y)
885 if (IS_RIGHT(n) && IS_UP(n))
887 for (y=G;y<=R+2*G-x;y++) {
889 SETBIT(n,sp->box-1-x,y)
891 RESBIT(n,sp->box-1-x,y)
893 if (IS_RIGHT(n) && IS_DOWN(n))
895 for (y=G;y<=R+2*G-x;y++) {
897 SETBIT(n,sp->box-1-x,sp->box-1-y)
899 RESBIT(n,sp->box-1-x,sp->box-1-y)
902 if (!IS_LEFT(n) && !IS_UP(n) && IS_LEFT_UP(n)) {
903 for (x=0;x<G;x++) for(y=0;y<G;y++)
905 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
907 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
910 if (!IS_LEFT(n) && !IS_DOWN(n) && IS_LEFT_DOWN(n)) {
911 for (x=0;x<G;x++) for(y=0;y<G;y++)
912 RESBIT(n,x,sp->box-1-y)
913 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
914 SETBIT(n,x,sp->box-1-y)
915 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
916 SETBIT(n,x,sp->box-1-y)
918 if (!IS_RIGHT(n) && !IS_UP(n) && IS_RIGHT_UP(n)) {
919 for (x=0;x<G;x++) for(y=0;y<G;y++)
920 RESBIT(n,sp->box-1-x,y)
921 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
922 SETBIT(n,sp->box-1-x,y)
923 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
924 SETBIT(n,sp->box-1-x,y)
926 if (!IS_RIGHT(n) && !IS_DOWN(n) && IS_RIGHT_DOWN(n)) {
927 for (x=0;x<G;x++) for(y=0;y<G;y++)
928 RESBIT(n,sp->box-1-x,sp->box-1-y)
929 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
930 SETBIT(n,sp->box-1-x,sp->box-1-y)
931 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
932 SETBIT(n,sp->box-1-x,sp->box-1-y)
935 #ifdef LARGE_BELLYBUTTON
937 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
938 for (x=0;x<G+T;x++) for(y=0;y<G+T;y++)
940 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
941 for (x=0;x<G+T;x++) for(y=sp->box-G-T;y<sp->box;y++)
943 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
944 for (x=sp->box-G-T;x<sp->box;x++) for(y=0;y<G+T;y++)
946 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
947 for (x=sp->box-G-T;x<sp->box;x++) for(y=sp->box-G-T;y<sp->box;y++)
954 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
955 for (x=0;x<sp->box/2-RR;x++) for(y=0;y<sp->box/2-RR;y++)
956 THREEQUARTERSBIT(n,x,y)
957 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
958 for (x=0;x<sp->box/2-RR;x++) for(y=sp->box/2+RR;y<sp->box;y++)
959 THREEQUARTERSBIT(n,x,y)
960 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
961 for (x=sp->box/2+RR;x<sp->box;x++) for(y=0;y<sp->box/2-RR;y++)
962 THREEQUARTERSBIT(n,x,y)
963 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
964 for (x=sp->box/2+RR;x<sp->box;x++) for(y=sp->box/2+RR;y<sp->box;y++)
965 THREEQUARTERSBIT(n,x,y)
968 sp->bitmaps[n] = XCreateImage(MI_DISPLAY(mi), MI_VISUAL(mi), 1, XYBitmap,
969 0, data, sp->box, sp->box, 8, 0);
970 if (sp->bitmaps[n] == None) {
975 sp->bitmaps[n]->byte_order = MSBFirst;
976 sp->bitmaps[n]->bitmap_unit = 8;
977 sp->bitmaps[n]->bitmap_bit_order = LSBFirst;
984 static void draw_with_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
986 Display *display = MI_DISPLAY(mi);
987 Window window = MI_WINDOW(mi);
989 int x,y,t,bitmap_index;
991 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
992 if (ARRAY(x,y) == -1) {
993 if (CHANGED_ARRAY(x,y)) {
994 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
995 XFillRectangle(display,window,gc,
996 sp->x_margin + sp->box*x,
997 sp->y_margin + sp->box*y,
1002 XSetForeground(display, gc, sp->polyomino[ARRAY(x,y)].color);
1004 if (ARR(x,y) != ARR(x-1,y)) bitmap_index |= LEFT;
1005 if (ARR(x,y) != ARR(x+1,y)) bitmap_index |= RIGHT;
1006 if (ARR(x,y) != ARR(x,y-1)) bitmap_index |= UP;
1007 if (ARR(x,y) != ARR(x,y+1)) bitmap_index |= DOWN;
1008 if (ARR(x,y) != ARR(x-1,y-1)) bitmap_index |= LEFT_UP;
1009 if (ARR(x,y) != ARR(x-1,y+1)) bitmap_index |= LEFT_DOWN;
1010 if (ARR(x,y) != ARR(x+1,y-1)) bitmap_index |= RIGHT_UP;
1011 if (ARR(x,y) != ARR(x+1,y+1)) bitmap_index |= RIGHT_DOWN;
1012 (void) XPutImage(display,window,gc,
1013 sp->bitmaps[bitmap_index],
1015 sp->x_margin + sp->box*x,
1016 sp->y_margin + sp->box*y,
1021 XSetForeground(display, gc, sp->border_color);
1023 XDrawRectangle(display,window,gc,
1024 sp->x_margin-t-1,sp->y_margin-t-1,
1025 sp->box*sp->width+1+2*t, sp->box*sp->height+1+2*t);
1029 /***************************************************
1030 Routines to initialise and close down polyominoes.
1031 ***************************************************/
1033 static void free_bitmaps(polyominoesstruct *sp)
1037 for (n=0;n<countof(sp->bitmaps);n++)
1038 /* Don't bother to free duplicates */
1039 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
1040 sp->bitmaps[n] = None;
1041 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
1042 sp->bitmaps[n] = None;
1043 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
1044 sp->bitmaps[n] = None;
1045 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
1046 sp->bitmaps[n] = None;
1048 else if (sp->bitmaps[n] != None) {
1049 XDestroyImage(sp->bitmaps[n]);
1050 sp->bitmaps[n] = None;
1054 #define deallocate(p,t) if ((p)!=NULL) {free(p); p=(t*)NULL;}
1056 static void free_polyominoes(ModeInfo * mi)
1058 polyominoesstruct *sp = &polyominoeses[MI_SCREEN(mi)];
1061 for (n=0;n<sp->nr_polyominoes;n++) {
1062 deallocate(sp->polyomino[n].point, point_type);
1065 deallocate(sp->polyomino, polyomino_type);
1066 deallocate(sp->attach_list, int);
1067 deallocate(sp->rectangles, XRectangle);
1068 deallocate(sp->lines, XSegment);
1069 deallocate(sp->reason_to_not_attach, int);
1070 deallocate(sp->array, int);
1071 deallocate(sp->changed_array, int);
1076 #define set_allocate(p,type,size) p = (type *) malloc(size); \
1077 if ((p)==NULL) {free_polyominoes(mi);return 0;}
1079 #define copy_polyomino(dst,src,new_rand) \
1080 (dst).len=(src).len; \
1081 (dst).max_white = (src).max_white; \
1082 set_allocate((dst).point,point_type,sizeof(point_type)*(src).len); \
1083 (dst).len = (src).len; \
1085 random_permutation((src).len,perm_point); \
1086 for (i=0;i<(src).len;i++) \
1087 (dst).point[i] = (src).point[perm_point[i]]; \
1088 (dst).transform_len = (src).transform_len; \
1090 random_permutation((src).transform_len,perm_transform); \
1091 for (i=0;i<(src).transform_len;i++) \
1092 (dst).transform_list[i] = (src).transform_list[perm_transform[i]]; \
1096 /***************************************************
1097 Puzzle specific initialization routines.
1098 ***************************************************/
1101 int check_pentomino_puzzle(polyominoesstruct *sp)
1103 return check_all_regions_multiple_of(sp, 5) && whites_ok(sp);
1107 int check_hexomino_puzzle(polyominoesstruct *sp)
1109 return check_all_regions_multiple_of(sp, 6) && whites_ok(sp);
1113 int check_tetr_pentomino_puzzle(polyominoesstruct *sp)
1115 return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp);
1119 int check_pent_hexomino_puzzle(polyominoesstruct *sp)
1121 return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp);
1125 int check_heptomino_puzzle(polyominoesstruct *sp)
1127 return check_all_regions_multiple_of(sp, 7) && whites_ok(sp);
1131 int check_octomino_puzzle(polyominoesstruct *sp)
1133 return check_all_regions_multiple_of(sp, 8) && whites_ok(sp);
1137 int check_dekomino_puzzle(polyominoesstruct *sp)
1139 return check_all_regions_multiple_of(sp, 10) && whites_ok(sp);
1143 int check_elevenomino_puzzle(polyominoesstruct *sp)
1145 return check_all_regions_multiple_of(sp, 11) && whites_ok(sp);
1148 static struct {int len; point_type point[4];
1149 int transform_len, transform_list[8], max_white;} tetromino[5] =
1154 {4, {{0,0}, {1,0}, {2,0}, {3,0}},
1155 2, {0, 1, -1, -1, -1, -1, -1, -1}, 2},
1160 {4, {{0,0}, {1,0}, {2,0}, {2,1}},
1161 8, {0, 1, 2, 3, 4, 5, 6, 7}, 2},
1166 {4, {{0,0}, {1,0}, {1,1}, {2,0}},
1167 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1172 {4, {{0,0}, {1,0}, {1,1}, {2,1}},
1173 4, {0, 1, 4, 5, -1, -1, -1, -1}, 2},
1178 {4, {{0,0}, {0,1}, {1,0}, {1,1}},
1179 1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}};
1182 static struct pentomino_struct {int len; point_type point[5];
1183 int transform_len, transform_list[8], max_white;}
1189 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}},
1190 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1195 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}},
1196 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1201 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}},
1202 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1208 {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}},
1209 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1214 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}},
1215 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1220 {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}},
1221 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1227 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}},
1228 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1234 {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}},
1235 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1240 {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}},
1241 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1247 {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}},
1248 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1254 {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}},
1255 1, {0, -1, -1, -1, -1, -1, -1, -1}, 4},
1261 {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}},
1262 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}};
1265 static struct hexomino_struct {int len; point_type point[6];
1266 int transform_len, transform_list[8], max_white;}
1272 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}},
1273 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1278 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}},
1279 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1284 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}},
1285 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1290 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}},
1291 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1297 {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}},
1298 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1303 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}},
1304 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1309 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}},
1310 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1316 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}},
1317 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1323 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}},
1324 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1329 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}},
1330 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1336 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}},
1337 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1342 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}},
1343 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1349 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}},
1350 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1356 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}},
1357 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1362 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}},
1363 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1369 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}},
1370 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1376 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}},
1377 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1383 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}},
1384 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1390 {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1391 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1397 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1398 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1403 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}},
1404 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1410 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}},
1411 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1416 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}},
1417 4, {0, 1, 4, 5, -1, -1, -1, -1}, 4},
1423 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}},
1424 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1430 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}},
1431 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1436 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}},
1437 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1443 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}},
1444 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1450 {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}},
1451 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1456 {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}},
1457 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1463 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}},
1464 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1470 {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}},
1471 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1477 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}},
1478 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1484 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}},
1485 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1491 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}},
1492 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1498 {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}},
1499 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}};
1501 static struct pentomino_struct one_sided_pentomino[60];
1503 static void make_one_sided_pentomino(void)
1508 for (i=0;i<countof(pentomino);i++) {
1509 one_sided_pentomino[j] = pentomino[i];
1511 if (one_sided_pentomino[j].transform_list[t]>=4) {
1512 one_sided_pentomino[j].transform_len = t;
1514 one_sided_pentomino[j] = pentomino[i];
1515 for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u];
1516 one_sided_pentomino[j].transform_len -= t;
1523 static struct hexomino_struct one_sided_hexomino[60];
1525 static void make_one_sided_hexomino(void)
1530 for (i=0;i<countof(hexomino);i++) {
1531 one_sided_hexomino[j] = hexomino[i];
1533 if (one_sided_hexomino[j].transform_list[t]>=4) {
1534 one_sided_hexomino[j].transform_len = t;
1536 one_sided_hexomino[j] = hexomino[i];
1537 for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u];
1538 one_sided_hexomino[j].transform_len -= t;
1546 Find all the ways of placing all twelve pentominoes
1547 into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6.
1551 int set_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1553 int perm_poly[12], perm_point[5], perm_transform[8], i, p;
1574 sp->nr_polyominoes = 12;
1575 set_allocate(sp->polyomino,polyomino_type,
1576 sp->nr_polyominoes*sizeof(polyomino_type));
1577 random_permutation(sp->nr_polyominoes,perm_poly);
1578 for (p=0;p<sp->nr_polyominoes;p++) {
1579 copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1);
1582 sp->check_ok = check_pentomino_puzzle;
1588 Many of the following puzzles are inspired by
1589 http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
1593 Find all the ways of placing all eighteen one-sided pentominoes
1598 int set_one_sided_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1600 int perm_poly[18], perm_point[5], perm_transform[8], i, p;
1602 make_one_sided_pentomino();
1623 sp->nr_polyominoes = 18;
1624 set_allocate(sp->polyomino,polyomino_type,
1625 sp->nr_polyominoes*sizeof(polyomino_type));
1626 random_permutation(sp->nr_polyominoes,perm_poly);
1627 for (p=0;p<sp->nr_polyominoes;p++) {
1628 copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1);
1631 sp->check_ok = check_pentomino_puzzle;
1637 Find all the ways of placing all sixty one-sided hexominoes
1642 int set_one_sided_hexomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1644 int perm_poly[60], perm_point[6], perm_transform[8], i, p;
1646 make_one_sided_hexomino();
1683 sp->nr_polyominoes = 60;
1684 set_allocate(sp->polyomino,polyomino_type,
1685 sp->nr_polyominoes*sizeof(polyomino_type));
1686 random_permutation(sp->nr_polyominoes,perm_poly);
1687 for (p=0;p<sp->nr_polyominoes;p++) {
1688 copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1);
1691 sp->check_ok = check_hexomino_puzzle;
1697 Find all the ways of placing all five tetrominoes and all twelve
1698 pentominoes into a rectangle.
1702 int set_tetr_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1704 int perm_poly[17], perm_point[5], perm_transform[8], i, p;
1721 sp->nr_polyominoes = 17;
1722 set_allocate(sp->polyomino,polyomino_type,
1723 sp->nr_polyominoes*sizeof(polyomino_type));
1724 random_permutation(sp->nr_polyominoes,perm_poly);
1725 for (p=0;p<countof(tetromino);p++) {
1726 copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1);
1728 for (p=0;p<countof(pentomino);p++) {
1729 copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1);
1732 sp->check_ok = check_tetr_pentomino_puzzle;
1737 Find all the ways of placing all twelve pentominoes and all thirty five
1738 hexominoes into a rectangle whose size is 18x15.
1742 int set_pent_hexomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1744 int perm_poly[47], perm_point[6], perm_transform[8], i, p;
1769 sp->nr_polyominoes = 47;
1770 set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type));
1771 random_permutation(47,perm_poly);
1772 for (p=0;p<countof(pentomino);p++) {
1773 copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1);
1775 for (p=0;p<countof(hexomino);p++) {
1776 copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1);
1779 sp->check_ok = check_pent_hexomino_puzzle;
1787 Science News September 20, 1986 Vol 130, No 12
1788 Science News November 14, 1987 Vol 132, Pg 310
1794 **** fills a 10x5 rectangle
1798 static struct {int len; point_type point[5];
1799 int transform_len, transform_list[8], max_white;} pentomino1 =
1800 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}},
1801 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3};
1804 int set_pentomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1806 int perm_point[5], perm_transform[8], i, p;
1811 sp->nr_polyominoes = 10;
1812 set_allocate(sp->polyomino,polyomino_type,
1813 sp->nr_polyominoes*sizeof(polyomino_type));
1814 for (p=0;p<sp->nr_polyominoes;p++) {
1815 copy_polyomino(sp->polyomino[p],pentomino1,1);
1818 sp->check_ok = check_pentomino_puzzle;
1826 ***** fills a 24x23 rectangle
1830 static struct {int len; point_type point[6];
1831 int transform_len, transform_list[8], max_white;} hexomino1 =
1832 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}},
1833 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1836 int set_hexomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1838 int perm_point[6], perm_transform[8], i, p;
1843 sp->nr_polyominoes = 92;
1844 set_allocate(sp->polyomino,polyomino_type,
1845 sp->nr_polyominoes*sizeof(polyomino_type));
1846 for (p=0;p<sp->nr_polyominoes;p++) {
1847 copy_polyomino(sp->polyomino[p],hexomino1,1);
1850 sp->check_ok = check_hexomino_puzzle;
1858 ***** fills a 21x26 rectangle
1860 (All solutions have 180 degree rotational symmetry)
1864 static struct {int len; point_type point[7];
1865 int transform_len, transform_list[8], max_white;} heptomino1 =
1866 {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}},
1867 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1870 int set_heptomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1872 int perm_point[7], perm_transform[8], i, p;
1879 sp->nr_polyominoes = 78;
1880 set_allocate(sp->polyomino,polyomino_type,
1881 sp->nr_polyominoes*sizeof(polyomino_type));
1882 for (p=0;p<sp->nr_polyominoes;p+=2) {
1883 copy_polyomino(sp->polyomino[p],heptomino1,1);
1884 copy_polyomino(sp->polyomino[p+1],heptomino1,0);
1887 sp->check_ok = check_heptomino_puzzle;
1892 /* The following puzzles from
1893 Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition
1894 by Solomon W. Golomb Princeton University Press 1994
1900 ***** fills a 28x19 rectangle
1904 int set_heptomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp)
1906 int perm_point[7], perm_transform[8], i, p;
1911 sp->nr_polyominoes = 76;
1912 set_allocate(sp->polyomino,polyomino_type,
1913 sp->nr_polyominoes*sizeof(polyomino_type));
1914 for (p=0;p<sp->nr_polyominoes;p++) {
1915 copy_polyomino(sp->polyomino[p],heptomino1,1);
1918 sp->check_ok = check_heptomino_puzzle;
1926 **** fills a 25x22 rectangle
1931 static struct {int len; point_type point[11];
1932 int transform_len, transform_list[8], max_white;} elevenomino1 =
1933 {11, {{0,0}, {1,0}, {2,0},
1934 {0,1}, {1,1}, {2,1}, {3,1},
1935 {0,2}, {1,2}, {2,2}, {3,2}},
1936 8, {0, 1, 2, 3, 4, 5, 6, 7}, 6};
1939 int set_elevenomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1941 int perm_point[11], perm_transform[8], i, p;
1948 sp->nr_polyominoes = 50;
1949 set_allocate(sp->polyomino,polyomino_type,
1950 sp->nr_polyominoes*sizeof(polyomino_type));
1951 for (p=0;p<sp->nr_polyominoes;p+=2) {
1952 copy_polyomino(sp->polyomino[p],elevenomino1,1);
1953 copy_polyomino(sp->polyomino[p+1],elevenomino1,0);
1956 sp->check_ok = check_elevenomino_puzzle;
1965 **** fills 32 x 30 rectangle
1970 static struct {int len; point_type point[10];
1971 int transform_len, transform_list[8], max_white;} dekomino1 =
1974 {0,1}, {1,1}, {2,1}, {3,1},
1975 {0,2}, {1,2}, {2,2}, {3,2}},
1976 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1979 int set_dekomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1981 int perm_point[10], perm_transform[8], i, p;
1986 sp->nr_polyominoes = 96;
1987 set_allocate(sp->polyomino,polyomino_type,
1988 sp->nr_polyominoes*sizeof(polyomino_type));
1989 for (p=0;p<sp->nr_polyominoes;p++) {
1990 copy_polyomino(sp->polyomino[p],dekomino1,1);
1993 sp->check_ok = check_dekomino_puzzle;
2001 *** fills 96 x 26 rectangle
2006 static struct {int len; point_type point[10];
2007 int transform_len, transform_list[8], max_white;} octomino1 =
2009 {0,1}, {1,1}, {2,1},
2010 {0,2}, {1,2}, {2,2}, {3,2}},
2011 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
2014 int set_octomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
2016 int perm_point[8], perm_transform[8], i, p;
2021 sp->nr_polyominoes = 312;
2022 set_allocate(sp->polyomino,polyomino_type,
2023 sp->nr_polyominoes*sizeof(polyomino_type));
2024 for (p=0;p<sp->nr_polyominoes;p++) {
2025 copy_polyomino(sp->polyomino[p],octomino1,1);
2028 sp->check_ok = check_octomino_puzzle;
2035 * fills 15 x 15 rectangle
2041 int set_pentomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp)
2043 int perm_point[5], perm_transform[8], i, p;
2048 sp->nr_polyominoes = 45;
2049 set_allocate(sp->polyomino,polyomino_type,
2050 sp->nr_polyominoes*sizeof(polyomino_type));
2051 for (p=0;p<sp->nr_polyominoes;p++) {
2052 copy_polyomino(sp->polyomino[p],pentomino1,1);
2055 sp->check_ok = check_pentomino_puzzle;
2063 **** fills a 47x33 rectangle
2069 int set_elevenomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp)
2071 int perm_point[11], perm_transform[8], i, p;
2076 sp->nr_polyominoes = 141;
2077 set_allocate(sp->polyomino,polyomino_type,
2078 sp->nr_polyominoes*sizeof(polyomino_type));
2079 for (p=0;p<sp->nr_polyominoes;p++) {
2080 copy_polyomino(sp->polyomino[p],elevenomino1,1);
2083 sp->check_ok = check_elevenomino_puzzle;
2088 /**************************************************
2090 **************************************************/
2092 #define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes(mi); return;}
2095 init_polyominoes (ModeInfo * mi)
2097 polyominoesstruct *sp;
2102 MI_INIT (mi, polyominoeses, free_polyominoes);
2103 sp = &polyominoeses[MI_SCREEN(mi)];
2108 if (MI_IS_FULLRANDOM(mi)) {
2109 sp->identical = (Bool) (LRAND() & 1);
2110 sp->use3D = (Bool) (NRAND(4));
2112 sp->identical = identical;
2115 if (sp->identical) {
2118 if (!set_pentomino_puzzle1(mi, sp))
2122 if (!set_hexomino_puzzle1(mi, sp))
2126 if (!set_heptomino_puzzle1(mi, sp))
2130 if (!set_heptomino_puzzle2(mi, sp))
2134 if (!set_elevenomino_puzzle1(mi, sp))
2138 if (!set_dekomino_puzzle1(mi, sp))
2142 if (!set_octomino_puzzle1(mi, sp))
2146 if (!set_pentomino_puzzle2(mi, sp))
2150 if (!set_elevenomino_puzzle2(mi, sp))
2157 if (!set_pentomino_puzzle(mi, sp))
2161 if (!set_one_sided_pentomino_puzzle(mi, sp))
2165 if (!set_one_sided_hexomino_puzzle(mi, sp))
2169 if (!set_pent_hexomino_puzzle(mi, sp))
2173 if (!set_tetr_pentomino_puzzle(mi, sp))
2179 allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int));
2180 sp->nr_attached = 0;
2182 if (sp->identical) {
2183 allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int));
2186 allocate(sp->array,int,sp->width*sp->height*sizeof(int));
2187 allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int));
2188 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1;
2190 sp->left_right = NRAND(2);
2191 sp->top_bottom = NRAND(2);
2193 box1 = MI_WIDTH(mi)/(sp->width+2);
2194 box2 = MI_HEIGHT(mi)/(sp->height+2);
2200 if (sp->box >= 12) {
2201 sp->box = (sp->box/12)*12;
2202 create_bitmaps(mi,sp);
2203 if (!sp->use_bitmaps)
2207 sp->use_bitmaps = 0;
2209 if (!sp->use_bitmaps) {
2210 allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle));
2211 allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment));
2214 allocate(perm,int,sp->nr_polyominoes*sizeof(int));
2215 random_permutation(sp->nr_polyominoes, perm);
2216 sp->mono = MI_NPIXELS(mi) < 12;
2217 start = NRAND(MI_NPIXELS(mi));
2218 for (i=0;i<sp->nr_polyominoes;i++)
2220 sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi));
2222 sp->polyomino[i+1].color = sp->polyomino[i].color;
2228 sp->polyomino[i].color = MI_WHITE_PIXEL(mi);
2230 sp->polyomino[i].color = MI_BLACK_PIXEL(mi);
2233 if (sp->use_bitmaps) {
2235 sp->border_color = MI_WHITE_PIXEL(mi);
2237 sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi)));
2240 sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2;
2241 sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2;
2246 /* Clear the background. */
2253 draw_polyominoes (ModeInfo * mi)
2255 polyominoesstruct *sp;
2256 int poly_no,point_no,transform_index,done,another_attachment_try;
2257 point_type attach_point;
2260 if (polyominoeses == NULL)
2262 sp = &polyominoeses[MI_SCREEN(mi)];
2266 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2268 init_polyominoes(mi);
2273 if (MI_CYCLES(mi) != 0) {
2274 if (++sp->counter > MI_CYCLES(mi)) {
2276 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2277 #else /* !STANDALONE */
2278 init_polyominoes(mi);
2279 #endif /* !STANDALONE */
2286 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2287 #else /* !STANDALONE */
2288 init_polyominoes(mi);
2293 MI_IS_DRAWN(mi) = True;
2295 if (sp->wait>0) return;
2297 memset(sp->changed_array,0,sp->width*sp->height*sizeof(int));
2299 poly_no = first_poly_no(sp);
2301 transform_index = 0;
2303 another_attachment_try = 1;
2304 find_blank(sp,&attach_point);
2305 if (sp->identical && sp->nr_attached < sp->nr_polyominoes)
2306 memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int));
2308 if (sp->nr_attached < sp->nr_polyominoes) {
2309 while (!done && another_attachment_try) {
2310 done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0));
2311 if (done && sp->rot180) {
2312 poly_no = first_poly_no(sp);
2313 done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0));
2315 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2318 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2322 if (sp->identical) {
2324 if (sp->nr_attached == 0)
2327 detach_until=sp->nr_attached-1;
2328 if (sp->nr_attached < sp->nr_polyominoes)
2329 while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0)
2331 while (sp->nr_attached>detach_until) {
2333 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2334 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2335 if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes)
2336 for (i=0;i<sp->nr_polyominoes;i++)
2337 REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i);
2339 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2345 if (sp->nr_attached == 0)
2349 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2350 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2352 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2357 if (sp->use_bitmaps)
2358 draw_with_bitmaps(mi,sp);
2360 draw_without_bitmaps(mi,sp);
2362 if (sp->nr_attached == sp->nr_polyominoes)
2369 reshape_polyominoes(ModeInfo * mi, int width, int height)
2371 XClearWindow (MI_DISPLAY (mi), MI_WINDOW(mi));
2372 init_polyominoes (mi);
2376 refresh_polyominoes (ModeInfo * mi)
2381 XSCREENSAVER_MODULE ("Polyominoes", polyominoes)
2383 #endif /* MODE_polyominoes */