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 reshape_polyominoes 0
44 # define polyominoes_handle_event 0
45 # define SMOOTH_COLORS
46 # 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", "free_polyominoes",
87 &polyominoes_opts, 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 #define ARRAY(x,y) (sp->array[(x)*sp->height+(y)])
183 #define CHANGED_ARRAY(x,y) (sp->changed_array[(x)*sp->height+(y)])
184 #define ARRAY_P(p) (sp->array[(p).x*sp->height+(p).y])
185 #define CHANGED_ARRAY_P(p) (sp->changed_array[(p).x*sp->height+(p).y])
186 #define ARR(x,y) (((x)<0||(x)>=sp->width||(y)<0||(y)>=sp->height)?-2:ARRAY(x,y))
188 #define REASON_TO_NOT_ATTACH(x,y) (sp->reason_to_not_attach[(x)*sp->nr_polyominoes+(y)])
190 #define ROUND8(n) ((((n)+7)/8)*8)
192 /* Defines to index the bitmaps. A set bit indicates that an edge or
193 corner is required. */
198 #define LEFT_UP (1<<4)
199 #define LEFT_DOWN (1<<5)
200 #define RIGHT_UP (1<<6)
201 #define RIGHT_DOWN (1<<7)
202 #define IS_LEFT(n) ((n) & LEFT)
203 #define IS_RIGHT(n) ((n) & RIGHT)
204 #define IS_UP(n) ((n) & UP)
205 #define IS_DOWN(n) ((n) & DOWN)
206 #define IS_LEFT_UP(n) ((n) & LEFT_UP)
207 #define IS_LEFT_DOWN(n) ((n) & LEFT_DOWN)
208 #define IS_RIGHT_UP(n) ((n) & RIGHT_UP)
209 #define IS_RIGHT_DOWN(n) ((n) & RIGHT_DOWN)
211 /* Defines to access the bitmaps. */
212 #define BITNO(x,y) ((x)+(y)*ROUND8(sp->box))
213 #define SETBIT(n,x,y) {data[BITNO(x,y)/8] |= 1<<(BITNO(x,y)%8);}
214 #define RESBIT(n,x,y) {data[BITNO(x,y)/8] &= ~(1<<(BITNO(x,y)%8));}
215 #define TWOTHIRDSBIT(n,x,y) {if ((x+y-1)%3) SETBIT(n,x,y) else RESBIT(n,x,y)}
216 #define HALFBIT(n,x,y) {if ((x-y)%2) SETBIT(n,x,y) else RESBIT(n,x,y)}
217 #define THIRDBIT(n,x,y) {if (!((x-y-1)%3)) SETBIT(n,x,y) else RESBIT(n,x,y)}
218 #define THREEQUARTERSBIT(n,x,y) \
219 {if ((y%2)||((x+2+y/2+1)%2)) SETBIT(n,x,y) else RESBIT(n,x,y)}
220 #define NOTHALFBIT(n,x,y) {if ((x-y)%2) RESBIT(n,x,y) else SETBIT(n,x,y)}
222 /* Parameters for bitmaps. */
223 #define G ((sp->box/45)+1) /* 1/2 of gap between polyominoes. */
224 #define T ((sp->box<=12)?1:(G*2)) /* Thickness of walls of polyominoes. */
225 #define R ((sp->box<=12)?1:(G*6)) /* Amount of rounding. */
226 #define RT ((sp->box<=12)?1:(G*3)) /* Thickness of wall of rounded parts.
227 Here 3 is an approximation to 2 sqrt(2). */
228 #define RR 0 /* Roof ridge thickness */
231 /* A list of those bitmaps we need to create to display any pentomino. */
232 /* (not used right now because it does not seem to work for hexonimoes.) */
234 static int bitmaps_needed[] =
236 LEFT_UP|LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
238 LEFT|RIGHT_UP|RIGHT_DOWN,
239 RIGHT|LEFT_UP|LEFT_DOWN,
240 UP|LEFT_DOWN|RIGHT_DOWN,
241 DOWN|LEFT_UP|RIGHT_UP,
251 /* These needed for hexonimoes*/
256 LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
257 LEFT_UP|RIGHT_UP|RIGHT_DOWN,
258 LEFT_UP|LEFT_DOWN|RIGHT_DOWN,
259 LEFT_UP|LEFT_DOWN|RIGHT_UP,
281 static int bitmap_needed(int n)
285 for (i=0;bitmaps_needed[i]!=-1;i++)
286 if (n == bitmaps_needed[i])
293 /* Some debugging routines.
295 static void print_board(polyominoesstruct *sp)
298 for (y=0;y<sp->height;y++) {
299 for (x=0;x<sp->width;x++)
300 if (ARRAY(x,y) == -1)
303 fprintf(stderr,"%c",'a'+ARRAY(x,y));
304 fprintf(stderr,"\n");
306 fprintf(stderr,"\n");
309 static void print_points(point_type *point, int len)
314 fprintf(stderr,"(%d %d) ",point[i].x,point[i].y);
317 static void print_polyomino(polyomino_type poly)
321 print_points(poly.point,poly.len);
322 fprintf(stderr,"\n");
323 for (i=0;i<poly.transform_len;i++)
324 fprintf(stderr,"%d ",poly.transform_list[i]);
325 fprintf(stderr,"\n");
329 static polyominoesstruct *polyominoeses = (polyominoesstruct *) NULL;
332 void random_permutation(int n, int a[])
336 for (i=0;i<n;i++) a[i] = -1;
350 /************************************************************
351 These are the routines for manipulating the polyominoes and
352 attaching and detaching them from the rectangle.
353 ************************************************************/
355 static void transform(point_type in, point_type offset, int transform_no,
356 point_type attach_point, point_type *out) {
357 switch (transform_no) {
358 case 0: out->x=in.x-offset.x+attach_point.x;
359 out->y=in.y-offset.y+attach_point.y;
361 case 1: out->x=-(in.y-offset.y)+attach_point.x;
362 out->y=in.x-offset.x+attach_point.y;
364 case 2: out->x=-(in.x-offset.x)+attach_point.x;
365 out->y=-(in.y-offset.y)+attach_point.y;
367 case 3: out->x=in.y-offset.y+attach_point.x;
368 out->y=-(in.x-offset.x)+attach_point.y;
370 case 4: out->x=-(in.x-offset.x)+attach_point.x;
371 out->y=in.y-offset.y+attach_point.y;
373 case 5: out->x=in.y-offset.y+attach_point.x;
374 out->y=in.x-offset.x+attach_point.y;
376 case 6: out->x=in.x-offset.x+attach_point.x;
377 out->y=-(in.y-offset.y)+attach_point.y;
379 case 7: out->x=-(in.y-offset.y)+attach_point.x;
380 out->y=-(in.x-offset.x)+attach_point.y;
385 static int first_poly_no(polyominoesstruct *sp)
390 while(poly_no<sp->nr_polyominoes && sp->polyomino[poly_no].attached)
395 static void next_poly_no(polyominoesstruct *sp, int *poly_no)
399 *poly_no = sp->nr_polyominoes;
403 } while (*poly_no<sp->nr_polyominoes && sp->polyomino[*poly_no].attached);
407 /* check_all_regions_multiple_of looks for connected regions of
408 blank spaces, and returns 0 if it finds a connected region containing
409 a number of blanks that is not a multiple of n.
412 static void count_adjacent_blanks(polyominoesstruct *sp, int *count, int x, int y, int blank_mark)
415 if (ARRAY(x,y) == -1) {
417 ARRAY(x,y) = blank_mark;
418 if (x>=1) count_adjacent_blanks(sp, count,x-1,y,blank_mark);
419 if (x<sp->width-1) count_adjacent_blanks(sp, count,x+1,y,blank_mark);
420 if (y>=1) count_adjacent_blanks(sp, count,x,y-1,blank_mark);
421 if (y<sp->height-1) count_adjacent_blanks(sp, count,x,y+1,blank_mark);
425 static int check_all_regions_multiple_of(polyominoesstruct *sp, int n)
427 int x,y,count,good = 1;
429 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
431 count_adjacent_blanks(sp, &count,x,y,-2);
435 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
436 if (ARRAY(x,y) == -2)
442 static int check_all_regions_positive_combination_of(polyominoesstruct *sp, int m, int n)
444 int x,y,count,good = 1;
446 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
448 count_adjacent_blanks(sp, &count,x,y,-2);
450 for (;count>=0 && !good;count-=m)
454 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
455 if (ARRAY(x,y) == -2)
461 static int find_smallest_blank_component(polyominoesstruct *sp)
463 int x,y,size,smallest_size,blank_mark,smallest_mark;
465 smallest_mark = blank_mark = -10;
466 smallest_size = 1000000000;
467 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y) == -1) {
469 count_adjacent_blanks(sp, &size,x,y,blank_mark);
470 if (size<smallest_size) {
471 smallest_mark = blank_mark;
472 smallest_size = size;
477 return smallest_mark;
480 /* "Chess board" check - see init_max_whites_list above for more details.
482 /* If the rectangle is alternatively covered by white and black
483 squares (chess board style), then this gives the list of
484 the maximal possible whites covered by each polyomino. It
485 is used by the function whites_ok which makes sure that the
486 array has a valid number of white or black remaining blanks left.
489 static int whites_ok(polyominoesstruct *sp)
491 int x,y,poly_no,whites=0,blacks=0,max_white=0,min_white=0;
493 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
494 if (ARRAY(x,y) == -1 && (x+y)%2) whites++;
495 if (ARRAY(x,y) == -1 && (x+y+1)%2) blacks++;
497 for (poly_no=0;poly_no<sp->nr_polyominoes;poly_no++) if (!sp->polyomino[poly_no].attached) {
498 max_white += sp->polyomino[poly_no].max_white;
499 min_white += sp->polyomino[poly_no].len - sp->polyomino[poly_no].max_white;
501 return (min_white <= blacks && min_white <= whites
502 && blacks <= max_white && whites <= max_white);
505 /* This routine looks at the point (x,y) and sees how many polyominoes
506 and all their various transforms may be attached there.
510 score_point(polyominoesstruct *sp, int x, int y, int min_score_so_far)
512 int poly_no, point_no, transform_index, i, attachable;
513 point_type attach_point = { 0, 0 }, target_point = { 0, 0 };
516 if (x>=1 && x<sp->width-1 && y>=1 && y<sp->height-1 &&
517 ARRAY(x-1,y-1)<0 && ARRAY(x-1,y)<0 && ARRAY(x-1,y+1)<0 &&
518 ARRAY(x+1,y-1)<0 && ARRAY(x+1,y)<0 && ARRAY(x+1,y+1)<0 &&
519 ARRAY(x,y-1)<0 && ARRAY(x,y+1)<0)
524 for (poly_no=first_poly_no(sp);poly_no<sp->nr_polyominoes;next_poly_no(sp,&poly_no))
525 if (!sp->polyomino[poly_no].attached) {
526 for (point_no=0;point_no<sp->polyomino[poly_no].len;point_no++)
527 for (transform_index=0;transform_index<sp->polyomino[poly_no].transform_len;transform_index++) {
529 for (i=0;i<sp->polyomino[poly_no].len;i++) {
530 transform(sp->polyomino[poly_no].point[i],
531 sp->polyomino[poly_no].point[point_no],
532 sp->polyomino[poly_no].transform_list[transform_index],
533 attach_point, &target_point);
534 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
535 && (target_point.y>=0) && (target_point.y<sp->height)
536 && (ARRAY_P(target_point)<0))) {
543 if (score>=min_score_so_far)
552 static void find_blank(polyominoesstruct *sp, point_type *point)
554 int score, worst_score;
558 blank_mark = find_smallest_blank_component(sp);
560 worst_score = 1000000;
561 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y)==blank_mark) {
562 score = 100*score_point(sp,x,y,worst_score);
564 if (sp->left_right) score += 10*x;
565 else score += 10*(sp->width-1-x);
566 if (sp->top_bottom) score += y;
567 else score += (sp->height-1-y);
569 if (score<worst_score) {
576 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
577 if (ARRAY(x,y)<0) ARRAY(x,y) = -1;
580 /* Detaches the most recently attached polyomino. */
583 void detach(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index, point_type *attach_point, int rot180)
586 point_type target_point = { 0, 0 };
588 if (sp->nr_attached == 0) return;
590 *poly_no = sp->attach_list[sp->nr_attached];
591 *point_no = sp->polyomino[*poly_no].point_no;
592 *transform_index = sp->polyomino[*poly_no].transform_index;
593 *attach_point = sp->polyomino[*poly_no].attach_point;
594 for (i=0;i<sp->polyomino[*poly_no].len;i++) {
595 transform(sp->polyomino[*poly_no].point[i],
596 sp->polyomino[*poly_no].point[*point_no],
597 sp->polyomino[*poly_no].transform_list[*transform_index]^(rot180<<1),
598 *attach_point, &target_point);
599 ARRAY_P(target_point) = -1;
600 CHANGED_ARRAY_P(target_point) = 1;
603 sp->polyomino[*poly_no].attached = 0;
606 /* Attempts to attach a polyomino at point (x,y) at the
607 point_no-th point of that polyomino, using the transform
608 transform_no. Returns 1 if successful.
612 int attach(polyominoesstruct *sp, int poly_no, int point_no, int transform_index, point_type attach_point, int rot180,
613 int *reason_to_not_attach) {
614 point_type target_point = { 0, 0 };
616 int attachable = 1, worst_reason_not_to_attach = 1000000000;
619 attach_point.x = sp->width-1-attach_point.x;
620 attach_point.y = sp->height-1-attach_point.y;
623 if (sp->polyomino[poly_no].attached)
626 for (i=0;i<sp->polyomino[poly_no].len;i++) {
627 transform(sp->polyomino[poly_no].point[i],
628 sp->polyomino[poly_no].point[point_no],
629 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
630 attach_point, &target_point);
631 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
632 && (target_point.y>=0) && (target_point.y<sp->height)
633 && (ARRAY_P(target_point) == -1))) {
636 if ((target_point.x>=0) && (target_point.x<sp->width)
637 && (target_point.y>=0) && (target_point.y<sp->height)
638 && (ARRAY_P(target_point) >= 0)
639 && (ARRAY_P(target_point)<worst_reason_not_to_attach))
640 worst_reason_not_to_attach = ARRAY_P(target_point);
647 if (sp->identical && !attachable) {
648 if (worst_reason_not_to_attach < 1000000000)
649 reason_to_not_attach[worst_reason_not_to_attach] = 1;
653 for (i=0;i<sp->polyomino[poly_no].len;i++) {
654 transform(sp->polyomino[poly_no].point[i],
655 sp->polyomino[poly_no].point[point_no],
656 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
657 attach_point, &target_point);
658 ARRAY_P(target_point) = poly_no;
659 CHANGED_ARRAY_P(target_point) = 1;
662 sp->attach_list[sp->nr_attached] = poly_no;
665 sp->polyomino[poly_no].attached = 1;
666 sp->polyomino[poly_no].point_no = point_no;
667 sp->polyomino[poly_no].attach_point = attach_point;
668 sp->polyomino[poly_no].transform_index = transform_index;
670 if (!sp->check_ok(sp)) {
671 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,rot180);
679 int next_attach_try(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index)
682 (*transform_index)++;
683 if (*transform_index>=sp->polyomino[*poly_no].transform_len) {
684 *transform_index = 0;
686 if (*point_no>=sp->polyomino[*poly_no].len) {
688 next_poly_no(sp,poly_no);
689 if (*poly_no>=sp->nr_polyominoes) {
690 *poly_no = first_poly_no(sp);
699 /*******************************************************
701 *******************************************************/
704 draw_without_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
706 Display *display = MI_DISPLAY(mi);
707 Window window = MI_WINDOW(mi);
709 int x,y,poly_no,nr_lines,nr_rectangles;
711 XSetLineAttributes(display,gc,sp->box/10+1,LineSolid,CapRound,JoinRound);
713 for (poly_no=-1;poly_no<sp->nr_polyominoes;poly_no++) {
715 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
716 if (CHANGED_ARRAY(x,y) && ARRAY(x,y) == poly_no) {
717 sp->rectangles[nr_rectangles].x = sp->x_margin + sp->box*x;
718 sp->rectangles[nr_rectangles].y = sp->y_margin + sp->box*y;
719 sp->rectangles[nr_rectangles].width = sp->box;
720 sp->rectangles[nr_rectangles].height = sp->box;
724 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
726 XSetForeground(display, gc, sp->polyomino[poly_no].color);
727 XFillRectangles(display, window, gc, sp->rectangles, nr_rectangles);
730 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
733 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
734 if (ARRAY(x,y) == -1 && ARRAY(x+1,y) == -1
735 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x+1,y))) {
736 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
737 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
738 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
739 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
743 XDrawSegments(display, window, gc, sp->lines, nr_lines);
746 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
747 if (ARRAY(x,y) == -1 && ARRAY(x,y+1) == -1
748 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x,y+1))) {
749 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
750 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
751 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
752 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
756 XDrawSegments(display, window, gc, sp->lines, nr_lines);
758 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
759 XDrawRectangle(display, window, gc, sp->x_margin, sp->y_margin, sp->box*sp->width, sp->box*sp->height);
761 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
764 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
765 if (ARRAY(x+1,y) != ARRAY(x,y)) {
766 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
767 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
768 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
769 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
773 XDrawSegments(display, window, gc, sp->lines, nr_lines);
776 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
777 if (ARRAY(x,y+1) != ARRAY(x,y)) {
778 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
779 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
780 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
781 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
785 XDrawSegments(display, window, gc, sp->lines, nr_lines);
786 XSetLineAttributes(display,gc,1,LineSolid,CapRound,JoinRound);
789 static void create_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
794 for (n=0;n<countof(sp->bitmaps);n++) {
796 /* Avoid duplication of identical bitmaps. */
797 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
798 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_UP];
799 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
800 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_DOWN];
801 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
802 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_UP];
803 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
804 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_DOWN];
806 else /* if (bitmap_needed(n)) */ {
807 data = (char *) malloc(sizeof(char)*(sp->box*ROUND8(sp->box)/8));
813 for (y=0;y<sp->box;y++) for (x=0;x<sp->box;x++) {
815 #ifdef SMALL_BELLYBUTTON
816 if (x >= sp->box / 2 && x <= sp->box / 2 + 1 &&
817 y >= sp->box / 2 && y <= sp->box / 2 + 1)
822 } else if ((x>=y && x<=sp->box-y-1 && IS_UP(n))
823 || (x<=y && x<=sp->box-y-1 && y<sp->box/2 && !IS_LEFT(n))
824 || (x>=y && x>=sp->box-y-1 && y<sp->box/2 && !IS_RIGHT(n)))
826 else if ((x<=y && x<=sp->box-y-1 && IS_LEFT(n))
827 || (x>=y && x<=sp->box-y-1 && x<sp->box/2 && !IS_UP(n))
828 || (x<=y && x>=sp->box-y-1 && x<sp->box/2 && !IS_DOWN(n)))
830 else if ((x>=y && x>=sp->box-y-1 && IS_RIGHT(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_DOWN(n))
835 || (x<=y && x<=sp->box-y-1 && y>=sp->box/2 && !IS_LEFT(n))
836 || (x>=y && x>=sp->box-y-1 && y>=sp->box/2 && !IS_RIGHT(n)))
841 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
844 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
845 SETBIT(n,sp->box-1-x,y)
847 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
850 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
851 SETBIT(n,x,sp->box-1-y)
853 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
856 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
857 RESBIT(n,sp->box-1-x,y)
859 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
862 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
863 RESBIT(n,x,sp->box-1-y)
865 if (IS_LEFT(n) && IS_UP(n))
867 for (y=G;y<=R+2*G-x;y++) {
873 if (IS_LEFT(n) && IS_DOWN(n))
875 for (y=G;y<=R+2*G-x;y++) {
877 SETBIT(n,x,sp->box-1-y)
879 RESBIT(n,x,sp->box-1-y)
881 if (IS_RIGHT(n) && IS_UP(n))
883 for (y=G;y<=R+2*G-x;y++) {
885 SETBIT(n,sp->box-1-x,y)
887 RESBIT(n,sp->box-1-x,y)
889 if (IS_RIGHT(n) && IS_DOWN(n))
891 for (y=G;y<=R+2*G-x;y++) {
893 SETBIT(n,sp->box-1-x,sp->box-1-y)
895 RESBIT(n,sp->box-1-x,sp->box-1-y)
898 if (!IS_LEFT(n) && !IS_UP(n) && IS_LEFT_UP(n)) {
899 for (x=0;x<G;x++) for(y=0;y<G;y++)
901 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
903 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
906 if (!IS_LEFT(n) && !IS_DOWN(n) && IS_LEFT_DOWN(n)) {
907 for (x=0;x<G;x++) for(y=0;y<G;y++)
908 RESBIT(n,x,sp->box-1-y)
909 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
910 SETBIT(n,x,sp->box-1-y)
911 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
912 SETBIT(n,x,sp->box-1-y)
914 if (!IS_RIGHT(n) && !IS_UP(n) && IS_RIGHT_UP(n)) {
915 for (x=0;x<G;x++) for(y=0;y<G;y++)
916 RESBIT(n,sp->box-1-x,y)
917 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
918 SETBIT(n,sp->box-1-x,y)
919 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
920 SETBIT(n,sp->box-1-x,y)
922 if (!IS_RIGHT(n) && !IS_DOWN(n) && IS_RIGHT_DOWN(n)) {
923 for (x=0;x<G;x++) for(y=0;y<G;y++)
924 RESBIT(n,sp->box-1-x,sp->box-1-y)
925 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
926 SETBIT(n,sp->box-1-x,sp->box-1-y)
927 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
928 SETBIT(n,sp->box-1-x,sp->box-1-y)
931 #ifdef LARGE_BELLYBUTTON
933 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
934 for (x=0;x<G+T;x++) for(y=0;y<G+T;y++)
936 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
937 for (x=0;x<G+T;x++) for(y=sp->box-G-T;y<sp->box;y++)
939 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
940 for (x=sp->box-G-T;x<sp->box;x++) for(y=0;y<G+T;y++)
942 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
943 for (x=sp->box-G-T;x<sp->box;x++) for(y=sp->box-G-T;y<sp->box;y++)
950 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
951 for (x=0;x<sp->box/2-RR;x++) for(y=0;y<sp->box/2-RR;y++)
952 THREEQUARTERSBIT(n,x,y)
953 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
954 for (x=0;x<sp->box/2-RR;x++) for(y=sp->box/2+RR;y<sp->box;y++)
955 THREEQUARTERSBIT(n,x,y)
956 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
957 for (x=sp->box/2+RR;x<sp->box;x++) for(y=0;y<sp->box/2-RR;y++)
958 THREEQUARTERSBIT(n,x,y)
959 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
960 for (x=sp->box/2+RR;x<sp->box;x++) for(y=sp->box/2+RR;y<sp->box;y++)
961 THREEQUARTERSBIT(n,x,y)
964 sp->bitmaps[n] = XCreateImage(MI_DISPLAY(mi), MI_VISUAL(mi), 1, XYBitmap,
965 0, data, sp->box, sp->box, 8, 0);
966 if (sp->bitmaps[n] == None) {
971 sp->bitmaps[n]->byte_order = MSBFirst;
972 sp->bitmaps[n]->bitmap_unit = 8;
973 sp->bitmaps[n]->bitmap_bit_order = LSBFirst;
980 static void draw_with_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
982 Display *display = MI_DISPLAY(mi);
983 Window window = MI_WINDOW(mi);
985 int x,y,t,bitmap_index;
987 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
988 if (ARRAY(x,y) == -1) {
989 if (CHANGED_ARRAY(x,y)) {
990 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
991 XFillRectangle(display,window,gc,
992 sp->x_margin + sp->box*x,
993 sp->y_margin + sp->box*y,
998 XSetForeground(display, gc, sp->polyomino[ARRAY(x,y)].color);
1000 if (ARR(x,y) != ARR(x-1,y)) bitmap_index |= LEFT;
1001 if (ARR(x,y) != ARR(x+1,y)) bitmap_index |= RIGHT;
1002 if (ARR(x,y) != ARR(x,y-1)) bitmap_index |= UP;
1003 if (ARR(x,y) != ARR(x,y+1)) bitmap_index |= DOWN;
1004 if (ARR(x,y) != ARR(x-1,y-1)) bitmap_index |= LEFT_UP;
1005 if (ARR(x,y) != ARR(x-1,y+1)) bitmap_index |= LEFT_DOWN;
1006 if (ARR(x,y) != ARR(x+1,y-1)) bitmap_index |= RIGHT_UP;
1007 if (ARR(x,y) != ARR(x+1,y+1)) bitmap_index |= RIGHT_DOWN;
1008 (void) XPutImage(display,window,gc,
1009 sp->bitmaps[bitmap_index],
1011 sp->x_margin + sp->box*x,
1012 sp->y_margin + sp->box*y,
1017 XSetForeground(display, gc, sp->border_color);
1019 XDrawRectangle(display,window,gc,
1020 sp->x_margin-t-1,sp->y_margin-t-1,
1021 sp->box*sp->width+1+2*t, sp->box*sp->height+1+2*t);
1025 /***************************************************
1026 Routines to initialise and close down polyominoes.
1027 ***************************************************/
1029 static void free_bitmaps(polyominoesstruct *sp)
1033 for (n=0;n<countof(sp->bitmaps);n++)
1034 /* Don't bother to free duplicates */
1035 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
1036 sp->bitmaps[n] = None;
1037 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
1038 sp->bitmaps[n] = None;
1039 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
1040 sp->bitmaps[n] = None;
1041 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
1042 sp->bitmaps[n] = None;
1044 else if (sp->bitmaps[n] != None) {
1045 XDestroyImage(sp->bitmaps[n]);
1046 sp->bitmaps[n] = None;
1050 #define deallocate(p,t) if ((p)!=NULL) {free(p); p=(t*)NULL;}
1052 ENTRYPOINT void free_polyominoes(ModeInfo * mi)
1054 polyominoesstruct *sp = &polyominoeses[MI_SCREEN(mi)];
1057 for (n=0;n<sp->nr_polyominoes;n++) {
1058 deallocate(sp->polyomino[n].point, point_type);
1061 deallocate(sp->polyomino, polyomino_type);
1062 deallocate(sp->attach_list, int);
1063 deallocate(sp->rectangles, XRectangle);
1064 deallocate(sp->lines, XSegment);
1065 deallocate(sp->reason_to_not_attach, int);
1066 deallocate(sp->array, int);
1067 deallocate(sp->changed_array, int);
1072 #define set_allocate(p,type,size) p = (type *) malloc(size); \
1073 if ((p)==NULL) {free_polyominoes(mi);return 0;}
1075 #define copy_polyomino(dst,src,new_rand) \
1076 (dst).len=(src).len; \
1077 (dst).max_white = (src).max_white; \
1078 set_allocate((dst).point,point_type,sizeof(point_type)*(src).len); \
1079 (dst).len = (src).len; \
1081 random_permutation((src).len,perm_point); \
1082 for (i=0;i<(src).len;i++) \
1083 (dst).point[i] = (src).point[perm_point[i]]; \
1084 (dst).transform_len = (src).transform_len; \
1086 random_permutation((src).transform_len,perm_transform); \
1087 for (i=0;i<(src).transform_len;i++) \
1088 (dst).transform_list[i] = (src).transform_list[perm_transform[i]]; \
1092 /***************************************************
1093 Puzzle specific initialization routines.
1094 ***************************************************/
1097 int check_pentomino_puzzle(polyominoesstruct *sp)
1099 return check_all_regions_multiple_of(sp, 5) && whites_ok(sp);
1103 int check_hexomino_puzzle(polyominoesstruct *sp)
1105 return check_all_regions_multiple_of(sp, 6) && whites_ok(sp);
1109 int check_tetr_pentomino_puzzle(polyominoesstruct *sp)
1111 return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp);
1115 int check_pent_hexomino_puzzle(polyominoesstruct *sp)
1117 return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp);
1121 int check_heptomino_puzzle(polyominoesstruct *sp)
1123 return check_all_regions_multiple_of(sp, 7) && whites_ok(sp);
1127 int check_octomino_puzzle(polyominoesstruct *sp)
1129 return check_all_regions_multiple_of(sp, 8) && whites_ok(sp);
1133 int check_dekomino_puzzle(polyominoesstruct *sp)
1135 return check_all_regions_multiple_of(sp, 10) && whites_ok(sp);
1139 int check_elevenomino_puzzle(polyominoesstruct *sp)
1141 return check_all_regions_multiple_of(sp, 11) && whites_ok(sp);
1144 static struct {int len; point_type point[4];
1145 int transform_len, transform_list[8], max_white;} tetromino[5] =
1150 {4, {{0,0}, {1,0}, {2,0}, {3,0}},
1151 2, {0, 1, -1, -1, -1, -1, -1, -1}, 2},
1156 {4, {{0,0}, {1,0}, {2,0}, {2,1}},
1157 8, {0, 1, 2, 3, 4, 5, 6, 7}, 2},
1162 {4, {{0,0}, {1,0}, {1,1}, {2,0}},
1163 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1168 {4, {{0,0}, {1,0}, {1,1}, {2,1}},
1169 4, {0, 1, 4, 5, -1, -1, -1, -1}, 2},
1174 {4, {{0,0}, {0,1}, {1,0}, {1,1}},
1175 1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}};
1178 static struct pentomino_struct {int len; point_type point[5];
1179 int transform_len, transform_list[8], max_white;}
1185 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}},
1186 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1191 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}},
1192 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1197 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}},
1198 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1204 {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}},
1205 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1210 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}},
1211 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1216 {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}},
1217 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1223 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}},
1224 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1230 {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}},
1231 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1236 {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}},
1237 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1243 {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}},
1244 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1250 {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}},
1251 1, {0, -1, -1, -1, -1, -1, -1, -1}, 4},
1257 {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}},
1258 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}};
1261 static struct hexomino_struct {int len; point_type point[6];
1262 int transform_len, transform_list[8], max_white;}
1268 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}},
1269 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1274 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}},
1275 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1280 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}},
1281 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1286 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}},
1287 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1293 {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}},
1294 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1299 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}},
1300 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1305 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}},
1306 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1312 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}},
1313 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1319 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}},
1320 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1325 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}},
1326 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1332 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}},
1333 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1338 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}},
1339 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1345 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}},
1346 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1352 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}},
1353 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1358 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}},
1359 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1365 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}},
1366 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1372 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}},
1373 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1379 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}},
1380 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1386 {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1387 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1393 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1394 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1399 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}},
1400 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1406 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}},
1407 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1412 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}},
1413 4, {0, 1, 4, 5, -1, -1, -1, -1}, 4},
1419 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}},
1420 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1426 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}},
1427 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1432 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}},
1433 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1439 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}},
1440 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1446 {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}},
1447 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1452 {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}},
1453 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1459 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}},
1460 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1466 {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}},
1467 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1473 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}},
1474 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1480 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}},
1481 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1487 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}},
1488 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1494 {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}},
1495 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}};
1497 static struct pentomino_struct one_sided_pentomino[60];
1499 static void make_one_sided_pentomino(void)
1504 for (i=0;i<countof(pentomino);i++) {
1505 one_sided_pentomino[j] = pentomino[i];
1507 if (one_sided_pentomino[j].transform_list[t]>=4) {
1508 one_sided_pentomino[j].transform_len = t;
1510 one_sided_pentomino[j] = pentomino[i];
1511 for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u];
1512 one_sided_pentomino[j].transform_len -= t;
1519 static struct hexomino_struct one_sided_hexomino[60];
1521 static void make_one_sided_hexomino(void)
1526 for (i=0;i<countof(hexomino);i++) {
1527 one_sided_hexomino[j] = hexomino[i];
1529 if (one_sided_hexomino[j].transform_list[t]>=4) {
1530 one_sided_hexomino[j].transform_len = t;
1532 one_sided_hexomino[j] = hexomino[i];
1533 for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u];
1534 one_sided_hexomino[j].transform_len -= t;
1542 Find all the ways of placing all twelve pentominoes
1543 into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6.
1547 int set_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1549 int perm_poly[12], perm_point[5], perm_transform[8], i, p;
1570 sp->nr_polyominoes = 12;
1571 set_allocate(sp->polyomino,polyomino_type,
1572 sp->nr_polyominoes*sizeof(polyomino_type));
1573 random_permutation(sp->nr_polyominoes,perm_poly);
1574 for (p=0;p<sp->nr_polyominoes;p++) {
1575 copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1);
1578 sp->check_ok = check_pentomino_puzzle;
1584 Many of the following puzzles are inspired by
1585 http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
1589 Find all the ways of placing all eighteen one-sided pentominoes
1594 int set_one_sided_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1596 int perm_poly[18], perm_point[5], perm_transform[8], i, p;
1598 make_one_sided_pentomino();
1619 sp->nr_polyominoes = 18;
1620 set_allocate(sp->polyomino,polyomino_type,
1621 sp->nr_polyominoes*sizeof(polyomino_type));
1622 random_permutation(sp->nr_polyominoes,perm_poly);
1623 for (p=0;p<sp->nr_polyominoes;p++) {
1624 copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1);
1627 sp->check_ok = check_pentomino_puzzle;
1633 Find all the ways of placing all sixty one-sided hexominoes
1638 int set_one_sided_hexomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1640 int perm_poly[60], perm_point[6], perm_transform[8], i, p;
1642 make_one_sided_hexomino();
1679 sp->nr_polyominoes = 60;
1680 set_allocate(sp->polyomino,polyomino_type,
1681 sp->nr_polyominoes*sizeof(polyomino_type));
1682 random_permutation(sp->nr_polyominoes,perm_poly);
1683 for (p=0;p<sp->nr_polyominoes;p++) {
1684 copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1);
1687 sp->check_ok = check_hexomino_puzzle;
1693 Find all the ways of placing all five tetrominoes and all twelve
1694 pentominoes into a rectangle.
1698 int set_tetr_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1700 int perm_poly[17], perm_point[5], perm_transform[8], i, p;
1717 sp->nr_polyominoes = 17;
1718 set_allocate(sp->polyomino,polyomino_type,
1719 sp->nr_polyominoes*sizeof(polyomino_type));
1720 random_permutation(sp->nr_polyominoes,perm_poly);
1721 for (p=0;p<countof(tetromino);p++) {
1722 copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1);
1724 for (p=0;p<countof(pentomino);p++) {
1725 copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1);
1728 sp->check_ok = check_tetr_pentomino_puzzle;
1733 Find all the ways of placing all twelve pentominoes and all thirty five
1734 hexominoes into a rectangle whose size is 18x15.
1738 int set_pent_hexomino_puzzle(ModeInfo * mi, polyominoesstruct *sp)
1740 int perm_poly[47], perm_point[6], perm_transform[8], i, p;
1765 sp->nr_polyominoes = 47;
1766 set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type));
1767 random_permutation(47,perm_poly);
1768 for (p=0;p<countof(pentomino);p++) {
1769 copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1);
1771 for (p=0;p<countof(hexomino);p++) {
1772 copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1);
1775 sp->check_ok = check_pent_hexomino_puzzle;
1783 Science News September 20, 1986 Vol 130, No 12
1784 Science News November 14, 1987 Vol 132, Pg 310
1790 **** fills a 10x5 rectangle
1794 static struct {int len; point_type point[5];
1795 int transform_len, transform_list[8], max_white;} pentomino1 =
1796 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}},
1797 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3};
1800 int set_pentomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1802 int perm_point[5], perm_transform[8], i, p;
1807 sp->nr_polyominoes = 10;
1808 set_allocate(sp->polyomino,polyomino_type,
1809 sp->nr_polyominoes*sizeof(polyomino_type));
1810 for (p=0;p<sp->nr_polyominoes;p++) {
1811 copy_polyomino(sp->polyomino[p],pentomino1,1);
1814 sp->check_ok = check_pentomino_puzzle;
1822 ***** fills a 24x23 rectangle
1826 static struct {int len; point_type point[6];
1827 int transform_len, transform_list[8], max_white;} hexomino1 =
1828 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}},
1829 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1832 int set_hexomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1834 int perm_point[6], perm_transform[8], i, p;
1839 sp->nr_polyominoes = 92;
1840 set_allocate(sp->polyomino,polyomino_type,
1841 sp->nr_polyominoes*sizeof(polyomino_type));
1842 for (p=0;p<sp->nr_polyominoes;p++) {
1843 copy_polyomino(sp->polyomino[p],hexomino1,1);
1846 sp->check_ok = check_hexomino_puzzle;
1854 ***** fills a 21x26 rectangle
1856 (All solutions have 180 degree rotational symmetry)
1860 static struct {int len; point_type point[7];
1861 int transform_len, transform_list[8], max_white;} heptomino1 =
1862 {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}},
1863 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1866 int set_heptomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1868 int perm_point[7], perm_transform[8], i, p;
1875 sp->nr_polyominoes = 78;
1876 set_allocate(sp->polyomino,polyomino_type,
1877 sp->nr_polyominoes*sizeof(polyomino_type));
1878 for (p=0;p<sp->nr_polyominoes;p+=2) {
1879 copy_polyomino(sp->polyomino[p],heptomino1,1);
1880 copy_polyomino(sp->polyomino[p+1],heptomino1,0);
1883 sp->check_ok = check_heptomino_puzzle;
1888 /* The following puzzles from
1889 Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition
1890 by Solomon W. Golomb Princeton University Press 1994
1896 ***** fills a 28x19 rectangle
1900 int set_heptomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp)
1902 int perm_point[7], perm_transform[8], i, p;
1907 sp->nr_polyominoes = 76;
1908 set_allocate(sp->polyomino,polyomino_type,
1909 sp->nr_polyominoes*sizeof(polyomino_type));
1910 for (p=0;p<sp->nr_polyominoes;p++) {
1911 copy_polyomino(sp->polyomino[p],heptomino1,1);
1914 sp->check_ok = check_heptomino_puzzle;
1922 **** fills a 25x22 rectangle
1927 static struct {int len; point_type point[11];
1928 int transform_len, transform_list[8], max_white;} elevenomino1 =
1929 {11, {{0,0}, {1,0}, {2,0},
1930 {0,1}, {1,1}, {2,1}, {3,1},
1931 {0,2}, {1,2}, {2,2}, {3,2}},
1932 8, {0, 1, 2, 3, 4, 5, 6, 7}, 6};
1935 int set_elevenomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1937 int perm_point[11], perm_transform[8], i, p;
1944 sp->nr_polyominoes = 50;
1945 set_allocate(sp->polyomino,polyomino_type,
1946 sp->nr_polyominoes*sizeof(polyomino_type));
1947 for (p=0;p<sp->nr_polyominoes;p+=2) {
1948 copy_polyomino(sp->polyomino[p],elevenomino1,1);
1949 copy_polyomino(sp->polyomino[p+1],elevenomino1,0);
1952 sp->check_ok = check_elevenomino_puzzle;
1961 **** fills 32 x 30 rectangle
1966 static struct {int len; point_type point[10];
1967 int transform_len, transform_list[8], max_white;} dekomino1 =
1970 {0,1}, {1,1}, {2,1}, {3,1},
1971 {0,2}, {1,2}, {2,2}, {3,2}},
1972 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1975 int set_dekomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
1977 int perm_point[10], perm_transform[8], i, p;
1982 sp->nr_polyominoes = 96;
1983 set_allocate(sp->polyomino,polyomino_type,
1984 sp->nr_polyominoes*sizeof(polyomino_type));
1985 for (p=0;p<sp->nr_polyominoes;p++) {
1986 copy_polyomino(sp->polyomino[p],dekomino1,1);
1989 sp->check_ok = check_dekomino_puzzle;
1997 *** fills 96 x 26 rectangle
2002 static struct {int len; point_type point[10];
2003 int transform_len, transform_list[8], max_white;} octomino1 =
2005 {0,1}, {1,1}, {2,1},
2006 {0,2}, {1,2}, {2,2}, {3,2}},
2007 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
2010 int set_octomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp)
2012 int perm_point[8], perm_transform[8], i, p;
2017 sp->nr_polyominoes = 312;
2018 set_allocate(sp->polyomino,polyomino_type,
2019 sp->nr_polyominoes*sizeof(polyomino_type));
2020 for (p=0;p<sp->nr_polyominoes;p++) {
2021 copy_polyomino(sp->polyomino[p],octomino1,1);
2024 sp->check_ok = check_octomino_puzzle;
2031 * fills 15 x 15 rectangle
2037 int set_pentomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp)
2039 int perm_point[5], perm_transform[8], i, p;
2044 sp->nr_polyominoes = 45;
2045 set_allocate(sp->polyomino,polyomino_type,
2046 sp->nr_polyominoes*sizeof(polyomino_type));
2047 for (p=0;p<sp->nr_polyominoes;p++) {
2048 copy_polyomino(sp->polyomino[p],pentomino1,1);
2051 sp->check_ok = check_pentomino_puzzle;
2059 **** fills a 47x33 rectangle
2065 int set_elevenomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp)
2067 int perm_point[11], perm_transform[8], i, p;
2072 sp->nr_polyominoes = 141;
2073 set_allocate(sp->polyomino,polyomino_type,
2074 sp->nr_polyominoes*sizeof(polyomino_type));
2075 for (p=0;p<sp->nr_polyominoes;p++) {
2076 copy_polyomino(sp->polyomino[p],elevenomino1,1);
2079 sp->check_ok = check_elevenomino_puzzle;
2084 /**************************************************
2086 **************************************************/
2088 #define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes(mi); return;}
2091 init_polyominoes (ModeInfo * mi)
2093 polyominoesstruct *sp;
2098 MI_INIT (mi, polyominoeses);
2099 sp = &polyominoeses[MI_SCREEN(mi)];
2104 if (MI_IS_FULLRANDOM(mi)) {
2105 sp->identical = (Bool) (LRAND() & 1);
2106 sp->use3D = (Bool) (NRAND(4));
2108 sp->identical = identical;
2111 if (sp->identical) {
2114 if (!set_pentomino_puzzle1(mi, sp))
2118 if (!set_hexomino_puzzle1(mi, sp))
2122 if (!set_heptomino_puzzle1(mi, sp))
2126 if (!set_heptomino_puzzle2(mi, sp))
2130 if (!set_elevenomino_puzzle1(mi, sp))
2134 if (!set_dekomino_puzzle1(mi, sp))
2138 if (!set_octomino_puzzle1(mi, sp))
2142 if (!set_pentomino_puzzle2(mi, sp))
2146 if (!set_elevenomino_puzzle2(mi, sp))
2153 if (!set_pentomino_puzzle(mi, sp))
2157 if (!set_one_sided_pentomino_puzzle(mi, sp))
2161 if (!set_one_sided_hexomino_puzzle(mi, sp))
2165 if (!set_pent_hexomino_puzzle(mi, sp))
2169 if (!set_tetr_pentomino_puzzle(mi, sp))
2175 if (MI_HEIGHT(mi) > MI_WIDTH(mi)) { /* rotate if portrait */
2176 int swap = sp->height;
2177 sp->height = sp->width;
2181 allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int));
2182 sp->nr_attached = 0;
2184 if (sp->identical) {
2185 allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int));
2188 allocate(sp->array,int,sp->width*sp->height*sizeof(int));
2189 allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int));
2190 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1;
2192 sp->left_right = NRAND(2);
2193 sp->top_bottom = NRAND(2);
2195 box1 = MI_WIDTH(mi)/(sp->width+2);
2196 box2 = MI_HEIGHT(mi)/(sp->height+2);
2202 if (MI_WIDTH(mi) > MI_HEIGHT(mi) * 5 || /* weird window aspect ratio */
2203 MI_HEIGHT(mi) > MI_WIDTH(mi)* 5) {
2204 sp->box *= (MI_WIDTH(mi) > MI_HEIGHT(mi)
2205 ? MI_WIDTH(mi) / (double) MI_HEIGHT(mi)
2206 : MI_HEIGHT(mi) / (double) MI_WIDTH(mi));
2209 if (sp->box >= 12) {
2210 sp->box = (sp->box/12)*12;
2211 create_bitmaps(mi,sp);
2212 if (!sp->use_bitmaps)
2216 sp->use_bitmaps = 0;
2218 if (!sp->use_bitmaps) {
2219 allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle));
2220 allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment));
2223 allocate(perm,int,sp->nr_polyominoes*sizeof(int));
2224 random_permutation(sp->nr_polyominoes, perm);
2225 sp->mono = MI_NPIXELS(mi) < 12;
2226 start = NRAND(MI_NPIXELS(mi));
2227 for (i=0;i<sp->nr_polyominoes;i++)
2229 sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi));
2231 sp->polyomino[i+1].color = sp->polyomino[i].color;
2237 sp->polyomino[i].color = MI_WHITE_PIXEL(mi);
2239 sp->polyomino[i].color = MI_BLACK_PIXEL(mi);
2242 if (sp->use_bitmaps) {
2244 sp->border_color = MI_WHITE_PIXEL(mi);
2246 sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi)));
2249 sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2;
2250 sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2;
2254 /* Clear the background. */
2260 draw_polyominoes (ModeInfo * mi)
2262 polyominoesstruct *sp;
2263 int poly_no,point_no,transform_index,done,another_attachment_try;
2264 point_type attach_point;
2267 if (polyominoeses == NULL)
2269 sp = &polyominoeses[MI_SCREEN(mi)];
2271 if (MI_CYCLES(mi) != 0) {
2272 if (++sp->counter > MI_CYCLES(mi)) {
2273 init_polyominoes(mi);
2279 init_polyominoes(mi);
2283 MI_IS_DRAWN(mi) = True;
2285 if (sp->wait>0) return;
2287 memset(sp->changed_array,0,sp->width*sp->height*sizeof(int));
2289 poly_no = first_poly_no(sp);
2291 transform_index = 0;
2293 another_attachment_try = 1;
2294 find_blank(sp,&attach_point);
2295 if (sp->identical && sp->nr_attached < sp->nr_polyominoes)
2296 memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int));
2298 if (sp->nr_attached < sp->nr_polyominoes) {
2299 while (!done && another_attachment_try) {
2300 done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0));
2301 if (done && sp->rot180) {
2302 poly_no = first_poly_no(sp);
2303 done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0));
2305 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2308 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2312 if (sp->identical) {
2314 if (sp->nr_attached == 0)
2317 detach_until=sp->nr_attached-1;
2318 if (sp->nr_attached < sp->nr_polyominoes)
2319 while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0)
2321 while (sp->nr_attached>detach_until) {
2323 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2324 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2325 if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes)
2326 for (i=0;i<sp->nr_polyominoes;i++)
2327 REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i);
2329 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2335 if (sp->nr_attached == 0)
2339 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2340 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2342 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2347 if (sp->use_bitmaps)
2348 draw_with_bitmaps(mi,sp);
2350 draw_without_bitmaps(mi,sp);
2352 if (sp->nr_attached == sp->nr_polyominoes)
2360 refresh_polyominoes (ModeInfo * mi)
2366 XSCREENSAVER_MODULE ("Polyominoes", polyominoes)
2368 #endif /* MODE_polyominoes */