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 # define reshape_polyominoes 0
41 # define polyominoes_handle_event 0
42 # define SMOOTH_COLORS
43 # include "xlockmore.h" /* in xscreensaver distribution */
45 #else /* STANDALONE */
46 # include "xlock.h" /* in xlockmore distribution */
47 #endif /* STANDALONE */
49 #ifdef MODE_polyominoes
50 #define DEF_IDENTICAL "False"
51 #define DEF_PLAIN "False"
53 static Bool identical;
56 static XrmOptionDescRec opts[] =
58 {"-identical", ".polyominoes.identical", XrmoptionNoArg, "on"},
59 {"+identical", ".polyominoes.identical", XrmoptionNoArg, "off"},
60 {"-plain", ".polyominoes.plain", XrmoptionNoArg, "on"},
61 {"+plain", ".polyominoes.plain", XrmoptionNoArg, "off"}
63 static argtype vars[] =
65 {&identical, "identical", "Identical", DEF_IDENTICAL, t_Bool},
66 {&plain, "plain", "Plain", DEF_PLAIN, t_Bool}
68 static OptionStruct desc[] =
70 {"-/+identical", "turn on/off puzzles where the polyomino pieces are identical"},
71 {"-/+plain", "turn on/off plain pieces"}
74 ENTRYPOINT ModeSpecOpt polyominoes_opts =
75 {sizeof opts / sizeof opts[0], opts,
76 sizeof vars / sizeof vars[0], vars, desc};
79 ModStruct polyominoes_description = {
80 "polyominoes", "init_polyominoes", "draw_polyominoes", "release_polyominoes",
81 "refresh_polyominoes", "init_polyominoes", (char *) NULL, &polyominoes_opts,
82 6000, 1, 8192, 1, 64, 1.0, "",
83 "Shows attempts to place polyominoes into a rectangle", 0, NULL
88 /* Each polyomino is described by several quantities:
89 len: the number of squares in the polyomino;
90 point: the list of points;
91 tranform_len: the number of items in transform_list;
92 transform_list: a list of transformations that need to be done in order
93 to get all rotations and reflections (see the function
95 max_white: the maximum number of white squares covered if polyomino
96 is placed on a chess board;
97 color: it's display color;
98 attached: whether it is currently attached to the rectangle;
99 attach_point: point on rectangle where attached;
100 point_no: the number of the point where it is attached;
101 transform_index: which element of transform_list is currently being used.
104 typedef struct {int x,y;} point_type;
106 typedef struct {int len; point_type *point;
107 int transform_len, transform_list[8], max_white;
110 point_type attach_point;
111 int point_no, transform_index;} polyomino_type;
114 typedef struct _polyominoesstruct{
118 unsigned border_color;
121 polyomino_type *polyomino;
123 Bool identical, use3D;
127 /* The array that tells where the polyominoes are attached. */
128 int *array, *changed_array;
130 /* These specify the dimensions of how things appear on the screen. */
131 int box, x_margin, y_margin;
133 /* These booleans decide in which way to try to attach the polyominoes. */
134 int left_right, top_bottom;
136 /* Bitmaps for display purposes. */
138 XImage *bitmaps[256];
140 /* Structures used for display purposes if there is not enough memory
141 to allocate bitmaps (or if the screen is small). */
143 XRectangle *rectangles;
145 /* A procedure that may be used to see if certain configurations
147 int (*check_ok)(struct _polyominoesstruct *sp);
149 /* Tells program that solutions are invariant under 180 degree
153 /* This is a variable used in the case that all the polyominoes are identical
154 that will further prune the search tree. Essentially it will be
155 int reason_to_not_attach[nr_polynominoes][nr_polynominoes];
156 Let me first explain the effect it is trying to overcome. Often
157 in the search process, the computer will first try to fit shapes into
158 a region (call it A), and then into another region (call it B) that is
159 essentially disjoint from A. But it may be that it just is not possible
160 to fit shapes into region B. So it fits something into A, and then
161 tries to fit something into B. Failing it fits something else into A,
162 and then tried again to fit something into B. Thus the program is trying
163 again and again to fit something into B, when it should have figured out
164 the first time that it was impossible.
166 To overcome this, everytime we try to attach a piece, we collect the reasons
167 why it cannot be attached (a boolean for each piece that got in the way).
168 If we see that a piece cannot be attached, we detach the other pieces until
169 we have detached at least one piece for which the boolean reason_to_not_attach
172 int *reason_to_not_attach;
177 eraser_state *eraser;
181 #define ARRAY(x,y) (sp->array[(x)*sp->height+(y)])
182 #define CHANGED_ARRAY(x,y) (sp->changed_array[(x)*sp->height+(y)])
183 #define ARRAY_P(p) (sp->array[(p).x*sp->height+(p).y])
184 #define CHANGED_ARRAY_P(p) (sp->changed_array[(p).x*sp->height+(p).y])
185 #define ARR(x,y) (((x)<0||(x)>=sp->width||(y)<0||(y)>=sp->height)?-2:ARRAY(x,y))
187 #define REASON_TO_NOT_ATTACH(x,y) (sp->reason_to_not_attach[(x)*sp->nr_polyominoes+(y)])
189 #define ROUND8(n) ((((n)+7)/8)*8)
191 /* Defines to index the bitmaps. A set bit indicates that an edge or
192 corner is required. */
197 #define LEFT_UP (1<<4)
198 #define LEFT_DOWN (1<<5)
199 #define RIGHT_UP (1<<6)
200 #define RIGHT_DOWN (1<<7)
201 #define IS_LEFT(n) ((n) & LEFT)
202 #define IS_RIGHT(n) ((n) & RIGHT)
203 #define IS_UP(n) ((n) & UP)
204 #define IS_DOWN(n) ((n) & DOWN)
205 #define IS_LEFT_UP(n) ((n) & LEFT_UP)
206 #define IS_LEFT_DOWN(n) ((n) & LEFT_DOWN)
207 #define IS_RIGHT_UP(n) ((n) & RIGHT_UP)
208 #define IS_RIGHT_DOWN(n) ((n) & RIGHT_DOWN)
210 /* Defines to access the bitmaps. */
211 #define BITNO(x,y) ((x)+(y)*ROUND8(sp->box))
212 #define SETBIT(n,x,y) {data[BITNO(x,y)/8] |= 1<<(BITNO(x,y)%8);}
213 #define RESBIT(n,x,y) {data[BITNO(x,y)/8] &= ~(1<<(BITNO(x,y)%8));}
214 #define TWOTHIRDSBIT(n,x,y) {if ((x+y-1)%3) SETBIT(n,x,y) else RESBIT(n,x,y)}
215 #define HALFBIT(n,x,y) {if ((x-y)%2) SETBIT(n,x,y) else RESBIT(n,x,y)}
216 #define THIRDBIT(n,x,y) {if (!((x-y-1)%3)) SETBIT(n,x,y) else RESBIT(n,x,y)}
217 #define THREEQUARTERSBIT(n,x,y) \
218 {if ((y%2)||((x+2+y/2+1)%2)) SETBIT(n,x,y) else RESBIT(n,x,y)}
219 #define NOTHALFBIT(n,x,y) {if ((x-y)%2) RESBIT(n,x,y) else SETBIT(n,x,y)}
221 /* Parameters for bitmaps. */
222 #define G ((sp->box/45)+1) /* 1/2 of gap between polyominoes. */
223 #define T ((sp->box<=12)?1:(G*2)) /* Thickness of walls of polyominoes. */
224 #define R ((sp->box<=12)?1:(G*6)) /* Amount of rounding. */
225 #define RT ((sp->box<=12)?1:(G*3)) /* Thickness of wall of rounded parts.
226 Here 3 is an approximation to 2 sqrt(2). */
227 #define RR 0 /* Roof ridge thickness */
230 /* A list of those bitmaps we need to create to display any pentomino. */
231 /* (not used right now because it does not seem to work for hexonimoes.) */
233 static int bitmaps_needed[] =
235 LEFT_UP|LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
237 LEFT|RIGHT_UP|RIGHT_DOWN,
238 RIGHT|LEFT_UP|LEFT_DOWN,
239 UP|LEFT_DOWN|RIGHT_DOWN,
240 DOWN|LEFT_UP|RIGHT_UP,
250 /* These needed for hexonimoes*/
255 LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
256 LEFT_UP|RIGHT_UP|RIGHT_DOWN,
257 LEFT_UP|LEFT_DOWN|RIGHT_DOWN,
258 LEFT_UP|LEFT_DOWN|RIGHT_UP,
280 static int bitmap_needed(int n)
284 for (i=0;bitmaps_needed[i]!=-1;i++)
285 if (n == bitmaps_needed[i])
292 /* Some debugging routines.
294 static void print_board(polyominoesstruct *sp)
297 for (y=0;y<sp->height;y++) {
298 for (x=0;x<sp->width;x++)
299 if (ARRAY(x,y) == -1)
302 fprintf(stderr,"%c",'a'+ARRAY(x,y));
303 fprintf(stderr,"\n");
305 fprintf(stderr,"\n");
308 static void print_points(point_type *point, int len)
313 fprintf(stderr,"(%d %d) ",point[i].x,point[i].y);
316 static void print_polyomino(polyomino_type poly)
320 print_points(poly.point,poly.len);
321 fprintf(stderr,"\n");
322 for (i=0;i<poly.transform_len;i++)
323 fprintf(stderr,"%d ",poly.transform_list[i]);
324 fprintf(stderr,"\n");
328 static polyominoesstruct *polyominoeses = (polyominoesstruct *) NULL;
331 void random_permutation(int n, int a[])
335 for (i=0;i<n;i++) a[i] = -1;
349 /************************************************************
350 These are the routines for manipulating the polyominoes and
351 attaching and detaching them from the rectangle.
352 ************************************************************/
354 static void transform(point_type in, point_type offset, int transform_no,
355 point_type attach_point, point_type *out) {
356 switch (transform_no) {
357 case 0: out->x=in.x-offset.x+attach_point.x;
358 out->y=in.y-offset.y+attach_point.y;
360 case 1: out->x=-(in.y-offset.y)+attach_point.x;
361 out->y=in.x-offset.x+attach_point.y;
363 case 2: out->x=-(in.x-offset.x)+attach_point.x;
364 out->y=-(in.y-offset.y)+attach_point.y;
366 case 3: out->x=in.y-offset.y+attach_point.x;
367 out->y=-(in.x-offset.x)+attach_point.y;
369 case 4: out->x=-(in.x-offset.x)+attach_point.x;
370 out->y=in.y-offset.y+attach_point.y;
372 case 5: out->x=in.y-offset.y+attach_point.x;
373 out->y=in.x-offset.x+attach_point.y;
375 case 6: out->x=in.x-offset.x+attach_point.x;
376 out->y=-(in.y-offset.y)+attach_point.y;
378 case 7: out->x=-(in.y-offset.y)+attach_point.x;
379 out->y=-(in.x-offset.x)+attach_point.y;
384 static int first_poly_no(polyominoesstruct *sp)
389 while(poly_no<sp->nr_polyominoes && sp->polyomino[poly_no].attached)
394 static void next_poly_no(polyominoesstruct *sp, int *poly_no)
398 *poly_no = sp->nr_polyominoes;
402 } while (*poly_no<sp->nr_polyominoes && sp->polyomino[*poly_no].attached);
406 /* check_all_regions_multiple_of looks for connected regions of
407 blank spaces, and returns 0 if it finds a connected region containing
408 a number of blanks that is not a multiple of n.
411 static void count_adjacent_blanks(polyominoesstruct *sp, int *count, int x, int y, int blank_mark)
414 if (ARRAY(x,y) == -1) {
416 ARRAY(x,y) = blank_mark;
417 if (x>=1) count_adjacent_blanks(sp, count,x-1,y,blank_mark);
418 if (x<sp->width-1) count_adjacent_blanks(sp, count,x+1,y,blank_mark);
419 if (y>=1) count_adjacent_blanks(sp, count,x,y-1,blank_mark);
420 if (y<sp->height-1) count_adjacent_blanks(sp, count,x,y+1,blank_mark);
424 static int check_all_regions_multiple_of(polyominoesstruct *sp, int n)
426 int x,y,count,good = 1;
428 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
430 count_adjacent_blanks(sp, &count,x,y,-2);
434 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
435 if (ARRAY(x,y) == -2)
441 static int check_all_regions_positive_combination_of(polyominoesstruct *sp, int m, int n)
443 int x,y,count,good = 1;
445 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
447 count_adjacent_blanks(sp, &count,x,y,-2);
449 for (;count>=0 && !good;count-=m)
453 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
454 if (ARRAY(x,y) == -2)
460 static int find_smallest_blank_component(polyominoesstruct *sp)
462 int x,y,size,smallest_size,blank_mark,smallest_mark;
464 smallest_mark = blank_mark = -10;
465 smallest_size = 1000000000;
466 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y) == -1) {
468 count_adjacent_blanks(sp, &size,x,y,blank_mark);
469 if (size<smallest_size) {
470 smallest_mark = blank_mark;
471 smallest_size = size;
476 return smallest_mark;
479 /* "Chess board" check - see init_max_whites_list above for more details.
481 /* If the rectangle is alternatively covered by white and black
482 squares (chess board style), then this gives the list of
483 the maximal possible whites covered by each polyomino. It
484 is used by the function whites_ok which makes sure that the
485 array has a valid number of white or black remaining blanks left.
488 static int whites_ok(polyominoesstruct *sp)
490 int x,y,poly_no,whites=0,blacks=0,max_white=0,min_white=0;
492 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
493 if (ARRAY(x,y) == -1 && (x+y)%2) whites++;
494 if (ARRAY(x,y) == -1 && (x+y+1)%2) blacks++;
496 for (poly_no=0;poly_no<sp->nr_polyominoes;poly_no++) if (!sp->polyomino[poly_no].attached) {
497 max_white += sp->polyomino[poly_no].max_white;
498 min_white += sp->polyomino[poly_no].len - sp->polyomino[poly_no].max_white;
500 return (min_white <= blacks && min_white <= whites
501 && blacks <= max_white && whites <= max_white);
504 /* This routine looks at the point (x,y) and sees how many polyominoes
505 and all their various transforms may be attached there.
509 score_point(polyominoesstruct *sp, int x, int y, int min_score_so_far)
511 int poly_no, point_no, transform_index, i, attachable;
512 point_type attach_point, target_point;
515 if (x>=1 && x<sp->width-1 && y>=1 && y<sp->height-1 &&
516 ARRAY(x-1,y-1)<0 && ARRAY(x-1,y)<0 && ARRAY(x-1,y+1)<0 &&
517 ARRAY(x+1,y-1)<0 && ARRAY(x+1,y)<0 && ARRAY(x+1,y+1)<0 &&
518 ARRAY(x,y-1)<0 && ARRAY(x,y+1)<0)
523 for (poly_no=first_poly_no(sp);poly_no<sp->nr_polyominoes;next_poly_no(sp,&poly_no))
524 if (!sp->polyomino[poly_no].attached) {
525 for (point_no=0;point_no<sp->polyomino[poly_no].len;point_no++)
526 for (transform_index=0;transform_index<sp->polyomino[poly_no].transform_len;transform_index++) {
528 for (i=0;i<sp->polyomino[poly_no].len;i++) {
529 transform(sp->polyomino[poly_no].point[i],
530 sp->polyomino[poly_no].point[point_no],
531 sp->polyomino[poly_no].transform_list[transform_index],
532 attach_point, &target_point);
533 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
534 && (target_point.y>=0) && (target_point.y<sp->height)
535 && (ARRAY_P(target_point)<0))) {
542 if (score>=min_score_so_far)
551 static void find_blank(polyominoesstruct *sp, point_type *point)
553 int score, worst_score;
557 blank_mark = find_smallest_blank_component(sp);
559 worst_score = 1000000;
560 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y)==blank_mark) {
561 score = 100*score_point(sp,x,y,worst_score);
563 if (sp->left_right) score += 10*x;
564 else score += 10*(sp->width-1-x);
565 if (sp->top_bottom) score += y;
566 else score += (sp->height-1-y);
568 if (score<worst_score) {
575 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
576 if (ARRAY(x,y)<0) ARRAY(x,y) = -1;
579 /* Detaches the most recently attached polyomino. */
582 void detach(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index, point_type *attach_point, int rot180)
585 point_type target_point;
587 if (sp->nr_attached == 0) return;
589 *poly_no = sp->attach_list[sp->nr_attached];
590 *point_no = sp->polyomino[*poly_no].point_no;
591 *transform_index = sp->polyomino[*poly_no].transform_index;
592 *attach_point = sp->polyomino[*poly_no].attach_point;
593 for (i=0;i<sp->polyomino[*poly_no].len;i++) {
594 transform(sp->polyomino[*poly_no].point[i],
595 sp->polyomino[*poly_no].point[*point_no],
596 sp->polyomino[*poly_no].transform_list[*transform_index]^(rot180<<1),
597 *attach_point, &target_point);
598 ARRAY_P(target_point) = -1;
599 CHANGED_ARRAY_P(target_point) = 1;
602 sp->polyomino[*poly_no].attached = 0;
605 /* Attempts to attach a polyomino at point (x,y) at the
606 point_no-th point of that polyomino, using the transform
607 transform_no. Returns 1 if successful.
611 int attach(polyominoesstruct *sp, int poly_no, int point_no, int transform_index, point_type attach_point, int rot180,
612 int *reason_to_not_attach) {
613 point_type target_point;
615 int attachable = 1, worst_reason_not_to_attach = 1000000000;
618 attach_point.x = sp->width-1-attach_point.x;
619 attach_point.y = sp->height-1-attach_point.y;
622 if (sp->polyomino[poly_no].attached)
625 for (i=0;i<sp->polyomino[poly_no].len;i++) {
626 transform(sp->polyomino[poly_no].point[i],
627 sp->polyomino[poly_no].point[point_no],
628 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
629 attach_point, &target_point);
630 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
631 && (target_point.y>=0) && (target_point.y<sp->height)
632 && (ARRAY_P(target_point) == -1))) {
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) >= 0)
638 && (ARRAY_P(target_point)<worst_reason_not_to_attach))
639 worst_reason_not_to_attach = ARRAY_P(target_point);
646 if (sp->identical && !attachable) {
647 if (worst_reason_not_to_attach < 1000000000)
648 reason_to_not_attach[worst_reason_not_to_attach] = 1;
652 for (i=0;i<sp->polyomino[poly_no].len;i++) {
653 transform(sp->polyomino[poly_no].point[i],
654 sp->polyomino[poly_no].point[point_no],
655 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
656 attach_point, &target_point);
657 ARRAY_P(target_point) = poly_no;
658 CHANGED_ARRAY_P(target_point) = 1;
661 sp->attach_list[sp->nr_attached] = poly_no;
664 sp->polyomino[poly_no].attached = 1;
665 sp->polyomino[poly_no].point_no = point_no;
666 sp->polyomino[poly_no].attach_point = attach_point;
667 sp->polyomino[poly_no].transform_index = transform_index;
669 if (!sp->check_ok(sp)) {
670 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,rot180);
678 int next_attach_try(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index)
681 (*transform_index)++;
682 if (*transform_index>=sp->polyomino[*poly_no].transform_len) {
683 *transform_index = 0;
685 if (*point_no>=sp->polyomino[*poly_no].len) {
687 next_poly_no(sp,poly_no);
688 if (*poly_no>=sp->nr_polyominoes) {
689 *poly_no = first_poly_no(sp);
698 /*******************************************************
700 *******************************************************/
703 draw_without_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
705 Display *display = MI_DISPLAY(mi);
706 Window window = MI_WINDOW(mi);
708 int x,y,poly_no,nr_lines,nr_rectangles;
710 XSetLineAttributes(display,gc,sp->box/10+1,LineSolid,CapRound,JoinRound);
712 for (poly_no=-1;poly_no<sp->nr_polyominoes;poly_no++) {
714 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
715 if (CHANGED_ARRAY(x,y) && ARRAY(x,y) == poly_no) {
716 sp->rectangles[nr_rectangles].x = sp->x_margin + sp->box*x;
717 sp->rectangles[nr_rectangles].y = sp->y_margin + sp->box*y;
718 sp->rectangles[nr_rectangles].width = sp->box;
719 sp->rectangles[nr_rectangles].height = sp->box;
723 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
725 XSetForeground(display, gc, sp->polyomino[poly_no].color);
726 XFillRectangles(display, window, gc, sp->rectangles, nr_rectangles);
729 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
732 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
733 if (ARRAY(x,y) == -1 && ARRAY(x+1,y) == -1
734 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x+1,y))) {
735 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
736 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
737 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
738 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
742 XDrawSegments(display, window, gc, sp->lines, nr_lines);
745 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
746 if (ARRAY(x,y) == -1 && ARRAY(x,y+1) == -1
747 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x,y+1))) {
748 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
749 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
750 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
751 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
755 XDrawSegments(display, window, gc, sp->lines, nr_lines);
757 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
758 XDrawRectangle(display, window, gc, sp->x_margin, sp->y_margin, sp->box*sp->width, sp->box*sp->height);
760 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
763 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
764 if (ARRAY(x+1,y) != ARRAY(x,y)) {
765 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
766 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
767 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
768 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
772 XDrawSegments(display, window, gc, sp->lines, nr_lines);
775 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
776 if (ARRAY(x,y+1) != ARRAY(x,y)) {
777 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
778 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
779 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
780 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
784 XDrawSegments(display, window, gc, sp->lines, nr_lines);
785 XSetLineAttributes(display,gc,1,LineSolid,CapRound,JoinRound);
788 static void create_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
793 for (n=0;n<256;n++) {
795 /* Avoid duplication of identical bitmaps. */
796 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
797 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_UP];
798 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
799 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_DOWN];
800 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
801 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_UP];
802 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
803 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_DOWN];
805 else /* if (bitmap_needed(n)) */ {
806 data = (char *) malloc(sizeof(char)*(sp->box*ROUND8(sp->box)/8));
812 for (y=0;y<sp->box;y++) for (x=0;x<sp->box;x++) {
814 #ifdef SMALL_BELLYBUTTON
815 if (x >= sp->box / 2 && x <= sp->box / 2 + 1 &&
816 y >= sp->box / 2 && y <= sp->box / 2 + 1)
821 } else if ((x>=y && x<=sp->box-y-1 && IS_UP(n))
822 || (x<=y && x<=sp->box-y-1 && y<sp->box/2 && !IS_LEFT(n))
823 || (x>=y && x>=sp->box-y-1 && y<sp->box/2 && !IS_RIGHT(n)))
825 else if ((x<=y && x<=sp->box-y-1 && IS_LEFT(n))
826 || (x>=y && x<=sp->box-y-1 && x<sp->box/2 && !IS_UP(n))
827 || (x<=y && x>=sp->box-y-1 && x<sp->box/2 && !IS_DOWN(n)))
829 else if ((x>=y && x>=sp->box-y-1 && IS_RIGHT(n))
830 || (x>=y && x<=sp->box-y-1 && x>=sp->box/2 && !IS_UP(n))
831 || (x<=y && x>=sp->box-y-1 && x>=sp->box/2 && !IS_DOWN(n)))
833 else if ((x<=y && x>=sp->box-y-1 && IS_DOWN(n))
834 || (x<=y && x<=sp->box-y-1 && y>=sp->box/2 && !IS_LEFT(n))
835 || (x>=y && x>=sp->box-y-1 && y>=sp->box/2 && !IS_RIGHT(n)))
840 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
843 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
844 SETBIT(n,sp->box-1-x,y)
846 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
849 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
850 SETBIT(n,x,sp->box-1-y)
852 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
855 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
856 RESBIT(n,sp->box-1-x,y)
858 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
861 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
862 RESBIT(n,x,sp->box-1-y)
864 if (IS_LEFT(n) && IS_UP(n))
866 for (y=G;y<=R+2*G-x;y++) {
872 if (IS_LEFT(n) && IS_DOWN(n))
874 for (y=G;y<=R+2*G-x;y++) {
876 SETBIT(n,x,sp->box-1-y)
878 RESBIT(n,x,sp->box-1-y)
880 if (IS_RIGHT(n) && IS_UP(n))
882 for (y=G;y<=R+2*G-x;y++) {
884 SETBIT(n,sp->box-1-x,y)
886 RESBIT(n,sp->box-1-x,y)
888 if (IS_RIGHT(n) && IS_DOWN(n))
890 for (y=G;y<=R+2*G-x;y++) {
892 SETBIT(n,sp->box-1-x,sp->box-1-y)
894 RESBIT(n,sp->box-1-x,sp->box-1-y)
897 if (!IS_LEFT(n) && !IS_UP(n) && IS_LEFT_UP(n)) {
898 for (x=0;x<G;x++) for(y=0;y<G;y++)
900 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
902 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
905 if (!IS_LEFT(n) && !IS_DOWN(n) && IS_LEFT_DOWN(n)) {
906 for (x=0;x<G;x++) for(y=0;y<G;y++)
907 RESBIT(n,x,sp->box-1-y)
908 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
909 SETBIT(n,x,sp->box-1-y)
910 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
911 SETBIT(n,x,sp->box-1-y)
913 if (!IS_RIGHT(n) && !IS_UP(n) && IS_RIGHT_UP(n)) {
914 for (x=0;x<G;x++) for(y=0;y<G;y++)
915 RESBIT(n,sp->box-1-x,y)
916 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
917 SETBIT(n,sp->box-1-x,y)
918 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
919 SETBIT(n,sp->box-1-x,y)
921 if (!IS_RIGHT(n) && !IS_DOWN(n) && IS_RIGHT_DOWN(n)) {
922 for (x=0;x<G;x++) for(y=0;y<G;y++)
923 RESBIT(n,sp->box-1-x,sp->box-1-y)
924 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
925 SETBIT(n,sp->box-1-x,sp->box-1-y)
926 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
927 SETBIT(n,sp->box-1-x,sp->box-1-y)
930 #ifdef LARGE_BELLYBUTTON
932 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
933 for (x=0;x<G+T;x++) for(y=0;y<G+T;y++)
935 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
936 for (x=0;x<G+T;x++) for(y=sp->box-G-T;y<sp->box;y++)
938 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
939 for (x=sp->box-G-T;x<sp->box;x++) for(y=0;y<G+T;y++)
941 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
942 for (x=sp->box-G-T;x<sp->box;x++) for(y=sp->box-G-T;y<sp->box;y++)
949 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
950 for (x=0;x<sp->box/2-RR;x++) for(y=0;y<sp->box/2-RR;y++)
951 THREEQUARTERSBIT(n,x,y)
952 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
953 for (x=0;x<sp->box/2-RR;x++) for(y=sp->box/2+RR;y<sp->box;y++)
954 THREEQUARTERSBIT(n,x,y)
955 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
956 for (x=sp->box/2+RR;x<sp->box;x++) for(y=0;y<sp->box/2-RR;y++)
957 THREEQUARTERSBIT(n,x,y)
958 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
959 for (x=sp->box/2+RR;x<sp->box;x++) for(y=sp->box/2+RR;y<sp->box;y++)
960 THREEQUARTERSBIT(n,x,y)
963 sp->bitmaps[n] = XCreateImage(MI_DISPLAY(mi), MI_VISUAL(mi), 1, XYBitmap,
964 0, data, sp->box, sp->box, 8, 0);
965 if (sp->bitmaps[n] == None) {
970 sp->bitmaps[n]->byte_order = MSBFirst;
971 sp->bitmaps[n]->bitmap_unit = 8;
972 sp->bitmaps[n]->bitmap_bit_order = LSBFirst;
979 static void draw_with_bitmaps(ModeInfo * mi, polyominoesstruct *sp)
981 Display *display = MI_DISPLAY(mi);
982 Window window = MI_WINDOW(mi);
984 int x,y,t,bitmap_index;
986 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
987 if (ARRAY(x,y) == -1) {
988 if (CHANGED_ARRAY(x,y)) {
989 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
990 XFillRectangle(display,window,gc,
991 sp->x_margin + sp->box*x,
992 sp->y_margin + sp->box*y,
997 XSetForeground(display, gc, sp->polyomino[ARRAY(x,y)].color);
999 if (ARR(x,y) != ARR(x-1,y)) bitmap_index |= LEFT;
1000 if (ARR(x,y) != ARR(x+1,y)) bitmap_index |= RIGHT;
1001 if (ARR(x,y) != ARR(x,y-1)) bitmap_index |= UP;
1002 if (ARR(x,y) != ARR(x,y+1)) bitmap_index |= DOWN;
1003 if (ARR(x,y) != ARR(x-1,y-1)) bitmap_index |= LEFT_UP;
1004 if (ARR(x,y) != ARR(x-1,y+1)) bitmap_index |= LEFT_DOWN;
1005 if (ARR(x,y) != ARR(x+1,y-1)) bitmap_index |= RIGHT_UP;
1006 if (ARR(x,y) != ARR(x+1,y+1)) bitmap_index |= RIGHT_DOWN;
1007 (void) XPutImage(display,window,gc,
1008 sp->bitmaps[bitmap_index],
1010 sp->x_margin + sp->box*x,
1011 sp->y_margin + sp->box*y,
1016 XSetForeground(display, gc, sp->border_color);
1018 XDrawRectangle(display,window,gc,
1019 sp->x_margin-t-1,sp->y_margin-t-1,
1020 sp->box*sp->width+1+2*t, sp->box*sp->height+1+2*t);
1024 /***************************************************
1025 Routines to initialise and close down polyominoes.
1026 ***************************************************/
1028 static void free_bitmaps(polyominoesstruct *sp)
1033 /* Don't bother to free duplicates */
1034 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
1035 sp->bitmaps[n] = None;
1036 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
1037 sp->bitmaps[n] = None;
1038 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
1039 sp->bitmaps[n] = None;
1040 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
1041 sp->bitmaps[n] = None;
1043 else if (sp->bitmaps[n] != None) {
1044 XDestroyImage(sp->bitmaps[n]);
1045 sp->bitmaps[n] = None;
1049 #define deallocate(p,t) if ((p)!=NULL) {free(p); p=(t*)NULL;}
1051 static void free_polyominoes(polyominoesstruct *sp)
1055 for (n=0;n<sp->nr_polyominoes;n++) {
1056 deallocate(sp->polyomino[n].point, point_type);
1059 deallocate(sp->polyomino, polyomino_type);
1060 deallocate(sp->attach_list, int);
1061 deallocate(sp->rectangles, XRectangle);
1062 deallocate(sp->lines, XSegment);
1063 deallocate(sp->reason_to_not_attach, int);
1064 deallocate(sp->array, int);
1065 deallocate(sp->changed_array, int);
1070 #define set_allocate(p,type,size) p = (type *) malloc(size); \
1071 if ((p)==NULL) {free_polyominoes(sp);return 0;}
1073 #define copy_polyomino(dst,src,new_rand) \
1074 (dst).len=(src).len; \
1075 (dst).max_white = (src).max_white; \
1076 set_allocate((dst).point,point_type,sizeof(point_type)*(src).len); \
1077 (dst).len = (src).len; \
1079 random_permutation((src).len,perm_point); \
1080 for (i=0;i<(src).len;i++) \
1081 (dst).point[i] = (src).point[perm_point[i]]; \
1082 (dst).transform_len = (src).transform_len; \
1084 random_permutation((src).transform_len,perm_transform); \
1085 for (i=0;i<(src).transform_len;i++) \
1086 (dst).transform_list[i] = (src).transform_list[perm_transform[i]]; \
1090 /***************************************************
1091 Puzzle specific initialization routines.
1092 ***************************************************/
1095 int check_pentomino_puzzle(polyominoesstruct *sp)
1097 return check_all_regions_multiple_of(sp, 5) && whites_ok(sp);
1101 int check_hexomino_puzzle(polyominoesstruct *sp)
1103 return check_all_regions_multiple_of(sp, 6) && whites_ok(sp);
1107 int check_tetr_pentomino_puzzle(polyominoesstruct *sp)
1109 return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp);
1113 int check_pent_hexomino_puzzle(polyominoesstruct *sp)
1115 return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp);
1119 int check_heptomino_puzzle(polyominoesstruct *sp)
1121 return check_all_regions_multiple_of(sp, 7) && whites_ok(sp);
1125 int check_octomino_puzzle(polyominoesstruct *sp)
1127 return check_all_regions_multiple_of(sp, 8) && whites_ok(sp);
1131 int check_dekomino_puzzle(polyominoesstruct *sp)
1133 return check_all_regions_multiple_of(sp, 10) && whites_ok(sp);
1137 int check_elevenomino_puzzle(polyominoesstruct *sp)
1139 return check_all_regions_multiple_of(sp, 11) && whites_ok(sp);
1142 static struct {int len; point_type point[4];
1143 int transform_len, transform_list[8], max_white;} tetromino[5] =
1148 {4, {{0,0}, {1,0}, {2,0}, {3,0}},
1149 2, {0, 1, -1, -1, -1, -1, -1, -1}, 2},
1154 {4, {{0,0}, {1,0}, {2,0}, {2,1}},
1155 8, {0, 1, 2, 3, 4, 5, 6, 7}, 2},
1160 {4, {{0,0}, {1,0}, {1,1}, {2,0}},
1161 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1166 {4, {{0,0}, {1,0}, {1,1}, {2,1}},
1167 4, {0, 1, 4, 5, -1, -1, -1, -1}, 2},
1172 {4, {{0,0}, {0,1}, {1,0}, {1,1}},
1173 1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}};
1176 static struct pentomino_struct {int len; point_type point[5];
1177 int transform_len, transform_list[8], max_white;}
1183 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}},
1184 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1189 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}},
1190 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1195 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}},
1196 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1202 {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}},
1203 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1208 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}},
1209 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1214 {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}},
1215 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1221 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}},
1222 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1228 {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}},
1229 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1234 {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}},
1235 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1241 {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}},
1242 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1248 {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}},
1249 1, {0, -1, -1, -1, -1, -1, -1, -1}, 4},
1255 {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}},
1256 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}};
1259 static struct hexomino_struct {int len; point_type point[6];
1260 int transform_len, transform_list[8], max_white;}
1266 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}},
1267 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1272 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}},
1273 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1278 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}},
1279 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1284 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}},
1285 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1291 {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}},
1292 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1297 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}},
1298 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1303 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}},
1304 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1310 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}},
1311 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1317 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}},
1318 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1323 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}},
1324 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1330 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}},
1331 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1336 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}},
1337 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1343 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}},
1344 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1350 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}},
1351 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1356 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}},
1357 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1363 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}},
1364 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1370 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}},
1371 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1377 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}},
1378 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1384 {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1385 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1391 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1392 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1397 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}},
1398 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1404 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}},
1405 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1410 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}},
1411 4, {0, 1, 4, 5, -1, -1, -1, -1}, 4},
1417 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}},
1418 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1424 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}},
1425 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1430 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}},
1431 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1437 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}},
1438 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1444 {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}},
1445 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1450 {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}},
1451 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1457 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}},
1458 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1464 {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}},
1465 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1471 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}},
1472 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1478 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}},
1479 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1485 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}},
1486 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1492 {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}},
1493 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}};
1495 static struct pentomino_struct one_sided_pentomino[60];
1497 static void make_one_sided_pentomino(void)
1502 for (i=0;i<18;i++) {
1503 one_sided_pentomino[j] = pentomino[i];
1505 if (one_sided_pentomino[j].transform_list[t]>=4) {
1506 one_sided_pentomino[j].transform_len = t;
1508 one_sided_pentomino[j] = pentomino[i];
1509 for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u];
1510 one_sided_pentomino[j].transform_len -= t;
1517 static struct hexomino_struct one_sided_hexomino[60];
1519 static void make_one_sided_hexomino(void)
1524 for (i=0;i<35;i++) {
1525 one_sided_hexomino[j] = hexomino[i];
1527 if (one_sided_hexomino[j].transform_list[t]>=4) {
1528 one_sided_hexomino[j].transform_len = t;
1530 one_sided_hexomino[j] = hexomino[i];
1531 for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u];
1532 one_sided_hexomino[j].transform_len -= t;
1540 Find all the ways of placing all twelve pentominoes
1541 into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6.
1545 int set_pentomino_puzzle(polyominoesstruct *sp)
1547 int perm_poly[12], perm_point[5], perm_transform[8], i, p;
1568 sp->nr_polyominoes = 12;
1569 set_allocate(sp->polyomino,polyomino_type,12*sizeof(polyomino_type));
1570 random_permutation(12,perm_poly);
1571 for (p=0;p<12;p++) {
1572 copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1);
1575 sp->check_ok = check_pentomino_puzzle;
1581 Many of the following puzzles are inspired by
1582 http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
1586 Find all the ways of placing all eighteen one-sided pentominoes
1591 int set_one_sided_pentomino_puzzle(polyominoesstruct *sp)
1593 int perm_poly[18], perm_point[5], perm_transform[8], i, p;
1595 make_one_sided_pentomino();
1616 sp->nr_polyominoes = 18;
1617 set_allocate(sp->polyomino,polyomino_type,18*sizeof(polyomino_type));
1618 random_permutation(18,perm_poly);
1619 for (p=0;p<18;p++) {
1620 copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1);
1623 sp->check_ok = check_pentomino_puzzle;
1629 Find all the ways of placing all sixty one-sided hexominoes
1634 int set_one_sided_hexomino_puzzle(polyominoesstruct *sp)
1636 int perm_poly[60], perm_point[6], perm_transform[8], i, p;
1638 make_one_sided_hexomino();
1675 sp->nr_polyominoes = 60;
1676 set_allocate(sp->polyomino,polyomino_type,60*sizeof(polyomino_type));
1677 random_permutation(60,perm_poly);
1678 for (p=0;p<60;p++) {
1679 copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1);
1682 sp->check_ok = check_hexomino_puzzle;
1688 Find all the ways of placing all five tetrominoes and all twelve
1689 pentominoes into a rectangle.
1693 int set_tetr_pentomino_puzzle(polyominoesstruct *sp)
1695 int perm_poly[17], perm_point[5], perm_transform[8], i, p;
1712 sp->nr_polyominoes = 17;
1713 set_allocate(sp->polyomino,polyomino_type,17*sizeof(polyomino_type));
1714 random_permutation(17,perm_poly);
1716 copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1);
1718 for (p=0;p<12;p++) {
1719 copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1);
1722 sp->check_ok = check_tetr_pentomino_puzzle;
1727 Find all the ways of placing all twelve pentominoes and all thirty five
1728 hexominoes into a rectangle whose size is 18x15.
1732 int set_pent_hexomino_puzzle(polyominoesstruct *sp)
1734 int perm_poly[47], perm_point[6], perm_transform[8], i, p;
1759 sp->nr_polyominoes = 47;
1760 set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type));
1761 random_permutation(47,perm_poly);
1762 for (p=0;p<12;p++) {
1763 copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1);
1765 for (p=0;p<35;p++) {
1766 copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1);
1769 sp->check_ok = check_pent_hexomino_puzzle;
1777 Science News September 20, 1986 Vol 130, No 12
1778 Science News November 14, 1987 Vol 132, Pg 310
1784 **** fills a 10x5 rectangle
1788 static struct {int len; point_type point[5];
1789 int transform_len, transform_list[8], max_white;} pentomino1 =
1790 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}},
1791 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3};
1794 int set_pentomino_puzzle1(polyominoesstruct *sp)
1796 int perm_point[5], perm_transform[8], i, p;
1801 sp->nr_polyominoes = 10;
1802 set_allocate(sp->polyomino,polyomino_type,10*sizeof(polyomino_type));
1803 for (p=0;p<10;p++) {
1804 copy_polyomino(sp->polyomino[p],pentomino1,1);
1807 sp->check_ok = check_pentomino_puzzle;
1815 ***** fills a 24x23 rectangle
1819 static struct {int len; point_type point[6];
1820 int transform_len, transform_list[8], max_white;} hexomino1 =
1821 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}},
1822 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1825 int set_hexomino_puzzle1(polyominoesstruct *sp)
1827 int perm_point[6], perm_transform[8], i, p;
1832 sp->nr_polyominoes = 92;
1833 set_allocate(sp->polyomino,polyomino_type,92*sizeof(polyomino_type));
1834 for (p=0;p<92;p++) {
1835 copy_polyomino(sp->polyomino[p],hexomino1,1);
1838 sp->check_ok = check_hexomino_puzzle;
1846 ***** fills a 21x26 rectangle
1848 (All solutions have 180 degree rotational symmetry)
1852 static struct {int len; point_type point[7];
1853 int transform_len, transform_list[8], max_white;} heptomino1 =
1854 {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}},
1855 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1858 int set_heptomino_puzzle1(polyominoesstruct *sp)
1860 int perm_point[7], perm_transform[8], i, p;
1867 sp->nr_polyominoes = 78;
1868 set_allocate(sp->polyomino,polyomino_type,78*sizeof(polyomino_type));
1869 for (p=0;p<78;p+=2) {
1870 copy_polyomino(sp->polyomino[p],heptomino1,1);
1871 copy_polyomino(sp->polyomino[p+1],heptomino1,0);
1874 sp->check_ok = check_heptomino_puzzle;
1879 /* The following puzzles from
1880 Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition
1881 by Solomon W. Golomb Princeton University Press 1994
1887 ***** fills a 28x19 rectangle
1891 int set_heptomino_puzzle2(polyominoesstruct *sp)
1893 int perm_point[7], perm_transform[8], i, p;
1898 sp->nr_polyominoes = 76;
1899 set_allocate(sp->polyomino,polyomino_type,76*sizeof(polyomino_type));
1900 for (p=0;p<76;p++) {
1901 copy_polyomino(sp->polyomino[p],heptomino1,1);
1904 sp->check_ok = check_heptomino_puzzle;
1912 **** fills a 25x22 rectangle
1917 static struct {int len; point_type point[11];
1918 int transform_len, transform_list[8], max_white;} elevenomino1 =
1919 {11, {{0,0}, {1,0}, {2,0},
1920 {0,1}, {1,1}, {2,1}, {3,1},
1921 {0,2}, {1,2}, {2,2}, {3,2}},
1922 8, {0, 1, 2, 3, 4, 5, 6, 7}, 6};
1925 int set_elevenomino_puzzle1(polyominoesstruct *sp)
1927 int perm_point[11], perm_transform[8], i, p;
1934 sp->nr_polyominoes = 50;
1935 set_allocate(sp->polyomino,polyomino_type,50*sizeof(polyomino_type));
1936 for (p=0;p<50;p+=2) {
1937 copy_polyomino(sp->polyomino[p],elevenomino1,1);
1938 copy_polyomino(sp->polyomino[p+1],elevenomino1,0);
1941 sp->check_ok = check_elevenomino_puzzle;
1950 **** fills 32 x 30 rectangle
1955 static struct {int len; point_type point[10];
1956 int transform_len, transform_list[8], max_white;} dekomino1 =
1959 {0,1}, {1,1}, {2,1}, {3,1},
1960 {0,2}, {1,2}, {2,2}, {3,2}},
1961 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1964 int set_dekomino_puzzle1(polyominoesstruct *sp)
1966 int perm_point[10], perm_transform[8], i, p;
1971 sp->nr_polyominoes = 96;
1972 set_allocate(sp->polyomino,polyomino_type,96*sizeof(polyomino_type));
1973 for (p=0;p<96;p++) {
1974 copy_polyomino(sp->polyomino[p],dekomino1,1);
1977 sp->check_ok = check_dekomino_puzzle;
1985 *** fills 96 x 26 rectangle
1990 static struct {int len; point_type point[10];
1991 int transform_len, transform_list[8], max_white;} octomino1 =
1993 {0,1}, {1,1}, {2,1},
1994 {0,2}, {1,2}, {2,2}, {3,2}},
1995 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1998 int set_octomino_puzzle1(polyominoesstruct *sp)
2000 int perm_point[8], perm_transform[8], i, p;
2005 sp->nr_polyominoes = 312;
2006 set_allocate(sp->polyomino,polyomino_type,312*sizeof(polyomino_type));
2007 for (p=0;p<312;p++) {
2008 copy_polyomino(sp->polyomino[p],octomino1,1);
2011 sp->check_ok = check_octomino_puzzle;
2018 * fills 15 x 15 rectangle
2024 int set_pentomino_puzzle2(polyominoesstruct *sp)
2026 int perm_point[5], perm_transform[8], i, p;
2031 sp->nr_polyominoes = 45;
2032 set_allocate(sp->polyomino,polyomino_type,45*sizeof(polyomino_type));
2033 for (p=0;p<45;p++) {
2034 copy_polyomino(sp->polyomino[p],pentomino1,1);
2037 sp->check_ok = check_pentomino_puzzle;
2045 **** fills a 47x33 rectangle
2051 int set_elevenomino_puzzle2(polyominoesstruct *sp)
2053 int perm_point[11], perm_transform[8], i, p;
2058 sp->nr_polyominoes = 141;
2059 set_allocate(sp->polyomino,polyomino_type,141*sizeof(polyomino_type));
2060 for (p=0;p<141;p++) {
2061 copy_polyomino(sp->polyomino[p],elevenomino1,1);
2064 sp->check_ok = check_elevenomino_puzzle;
2069 /**************************************************
2071 **************************************************/
2073 #define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes(sp); return;}
2076 init_polyominoes (ModeInfo * mi)
2078 polyominoesstruct *sp;
2083 if (polyominoeses == NULL) {
2085 = (polyominoesstruct *) calloc(MI_NUM_SCREENS(mi),sizeof (polyominoesstruct)))
2089 sp = &polyominoeses[MI_SCREEN(mi)];
2091 free_polyominoes(sp);
2096 if (MI_IS_FULLRANDOM(mi)) {
2097 sp->identical = (Bool) (LRAND() & 1);
2098 sp->use3D = (Bool) (NRAND(4));
2100 sp->identical = identical;
2103 if (sp->identical) {
2106 if (!set_pentomino_puzzle1(sp))
2110 if (!set_hexomino_puzzle1(sp))
2114 if (!set_heptomino_puzzle1(sp))
2118 if (!set_heptomino_puzzle2(sp))
2122 if (!set_elevenomino_puzzle1(sp))
2126 if (!set_dekomino_puzzle1(sp))
2130 if (!set_octomino_puzzle1(sp))
2134 if (!set_pentomino_puzzle2(sp))
2138 if (!set_elevenomino_puzzle2(sp))
2145 if (!set_pentomino_puzzle(sp))
2149 if (!set_one_sided_pentomino_puzzle(sp))
2153 if (!set_one_sided_hexomino_puzzle(sp))
2157 if (!set_pent_hexomino_puzzle(sp))
2161 if (!set_tetr_pentomino_puzzle(sp))
2167 allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int));
2168 sp->nr_attached = 0;
2170 if (sp->identical) {
2171 allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int));
2174 allocate(sp->array,int,sp->width*sp->height*sizeof(int));
2175 allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int));
2176 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1;
2178 sp->left_right = NRAND(2);
2179 sp->top_bottom = NRAND(2);
2181 box1 = MI_WIDTH(mi)/(sp->width+2);
2182 box2 = MI_HEIGHT(mi)/(sp->height+2);
2188 if (sp->box >= 12) {
2189 sp->box = (sp->box/12)*12;
2190 create_bitmaps(mi,sp);
2191 if (!sp->use_bitmaps)
2195 sp->use_bitmaps = 0;
2197 if (!sp->use_bitmaps) {
2198 allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle));
2199 allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment));
2202 allocate(perm,int,sp->nr_polyominoes*sizeof(int));
2203 random_permutation(sp->nr_polyominoes, perm);
2204 sp->mono = MI_NPIXELS(mi) < 12;
2205 start = NRAND(MI_NPIXELS(mi));
2206 for (i=0;i<sp->nr_polyominoes;i++)
2208 sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi));
2210 sp->polyomino[i+1].color = sp->polyomino[i].color;
2216 sp->polyomino[i].color = MI_WHITE_PIXEL(mi);
2218 sp->polyomino[i].color = MI_BLACK_PIXEL(mi);
2221 if (sp->use_bitmaps) {
2223 sp->border_color = MI_WHITE_PIXEL(mi);
2225 sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi)));
2228 sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2;
2229 sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2;
2234 /* Clear the background. */
2241 draw_polyominoes (ModeInfo * mi)
2243 polyominoesstruct *sp;
2244 int poly_no,point_no,transform_index,done,another_attachment_try;
2245 point_type attach_point;
2248 if (polyominoeses == NULL)
2250 sp = &polyominoeses[MI_SCREEN(mi)];
2254 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2259 if (MI_CYCLES(mi) != 0) {
2260 if (++sp->counter > MI_CYCLES(mi)) {
2262 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2263 #endif /* STANDALONE */
2264 init_polyominoes(mi);
2271 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2272 #endif /* STANDALONE */
2273 init_polyominoes(mi);
2277 MI_IS_DRAWN(mi) = True;
2279 if (sp->wait>0) return;
2281 memset(sp->changed_array,0,sp->width*sp->height*sizeof(int));
2283 poly_no = first_poly_no(sp);
2285 transform_index = 0;
2287 another_attachment_try = 1;
2288 find_blank(sp,&attach_point);
2289 if (sp->identical && sp->nr_attached < sp->nr_polyominoes)
2290 memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int));
2292 if (sp->nr_attached < sp->nr_polyominoes) {
2293 while (!done && another_attachment_try) {
2294 done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0));
2295 if (done && sp->rot180) {
2296 poly_no = first_poly_no(sp);
2297 done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0));
2299 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2302 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2306 if (sp->identical) {
2308 if (sp->nr_attached == 0)
2311 detach_until=sp->nr_attached-1;
2312 if (sp->nr_attached < sp->nr_polyominoes)
2313 while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0)
2315 while (sp->nr_attached>detach_until) {
2317 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2318 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2319 if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes)
2320 for (i=0;i<sp->nr_polyominoes;i++)
2321 REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i);
2323 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2329 if (sp->nr_attached == 0)
2333 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2334 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2336 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2341 if (sp->use_bitmaps)
2342 draw_with_bitmaps(mi,sp);
2344 draw_without_bitmaps(mi,sp);
2346 if (sp->nr_attached == sp->nr_polyominoes)
2353 release_polyominoes(ModeInfo * mi)
2357 if (polyominoeses != NULL) {
2358 for (screen=0;screen<MI_NUM_SCREENS(mi); screen++)
2359 free_polyominoes(&polyominoeses[screen]);
2360 (void) free((void *) polyominoeses);
2361 polyominoeses = (polyominoesstruct *) NULL;
2366 refresh_polyominoes (ModeInfo * mi)
2371 XSCREENSAVER_MODULE ("Polyominoes", polyominoes)
2373 #endif /* MODE_polyominoes */