1 /* -*- Mode: C; tab-width: 4 -*- */
2 /* polyominoes --- Shows attempts to place polyominoes into a rectangle */
5 static const char sccsid[] = "@(#)polyominoes.c 5.01 2000/12/18 xlockmore";
9 * Copyright (c) 2000 by Stephen Montgomery-Smith <stephen@math.missouri.edu>
11 * Permission to use, copy, modify, and distribute this software and its
12 * documentation for any purpose and without fee is hereby granted,
13 * provided that the above copyright notice appear in all copies and that
14 * both that copyright notice and this permission notice appear in
15 * supporting documentation.
17 * This file is provided AS IS with no warranties of any kind. The author
18 * shall have no liability with respect to the infringement of copyrights,
19 * trade secrets or any patents by this file or any part thereof. In no
20 * event will the author be liable for any lost revenue or profits or
21 * other special, indirect and consequential damages.
24 * 07-Jan-2001: Made improvement to the search algorithm for the puzzles
25 * involving identical polyominoes (via the variable
26 * reason_to_not_attach). By Stephen Montgomery-Smith.
27 * 20-Dec-2000: Added more puzzles at David Bagley's request.
28 * 27-Nov-2000: Adapted from euler2d.c Copyright (c) 2000 by Stephen
30 * 05-Jun-2000: Adapted from flow.c Copyright (c) 1996 by Tim Auckland
31 * 18-Jul-1996: Adapted from swarm.c Copyright (c) 1991 by Patrick J. Naughton.
32 * 31-Aug-1990: Adapted from xswarm by Jeff Butterworth. (butterwo@ncsc.org)
36 # define MODE_polyominoes
37 #define DEFAULTS "*delay: 10000 \n" \
40 "*fpsSolid: true \n" \
42 # define polyominoes_handle_event 0
43 # define SMOOTH_COLORS
44 # include "xlockmore.h" /* in xscreensaver distribution */
46 #else /* STANDALONE */
47 # include "xlock.h" /* in xlockmore distribution */
48 #endif /* STANDALONE */
50 #ifdef MODE_polyominoes
51 #define DEF_IDENTICAL "False"
52 #define DEF_PLAIN "False"
54 static Bool identical;
57 static XrmOptionDescRec opts[] =
59 {"-identical", ".polyominoes.identical", XrmoptionNoArg, "on"},
60 {"+identical", ".polyominoes.identical", XrmoptionNoArg, "off"},
61 {"-plain", ".polyominoes.plain", XrmoptionNoArg, "on"},
62 {"+plain", ".polyominoes.plain", XrmoptionNoArg, "off"}
64 static argtype vars[] =
66 {&identical, "identical", "Identical", DEF_IDENTICAL, t_Bool},
67 {&plain, "plain", "Plain", DEF_PLAIN, t_Bool}
69 static OptionStruct desc[] =
71 {"-/+identical", "turn on/off puzzles where the polyomino pieces are identical"},
72 {"-/+plain", "turn on/off plain pieces"}
75 ENTRYPOINT ModeSpecOpt polyominoes_opts =
76 {sizeof opts / sizeof opts[0], opts,
77 sizeof vars / sizeof vars[0], vars, desc};
80 ModStruct polyominoes_description = {
81 "polyominoes", "init_polyominoes", "draw_polyominoes", "release_polyominoes",
82 "refresh_polyominoes", "init_polyominoes", (char *) NULL, &polyominoes_opts,
83 6000, 1, 8192, 1, 64, 1.0, "",
84 "Shows attempts to place polyominoes into a rectangle", 0, NULL
89 /* Each polyomino is described by several quantities:
90 len: the number of squares in the polyomino;
91 point: the list of points;
92 tranform_len: the number of items in transform_list;
93 transform_list: a list of transformations that need to be done in order
94 to get all rotations and reflections (see the function
96 max_white: the maximum number of white squares covered if polyomino
97 is placed on a chess board;
98 color: it's display color;
99 attached: whether it is currently attached to the rectangle;
100 attach_point: point on rectangle where attached;
101 point_no: the number of the point where it is attached;
102 transform_index: which element of transform_list is currently being used.
105 typedef struct {int x,y;} point_type;
107 typedef struct {int len; point_type *point;
108 int transform_len, transform_list[8], max_white;
111 point_type attach_point;
112 int point_no, transform_index;} polyomino_type;
115 typedef struct _polyominoesstruct{
119 unsigned border_color;
122 polyomino_type *polyomino;
124 Bool identical, use3D;
128 /* The array that tells where the polyominoes are attached. */
129 int *array, *changed_array;
131 /* These specify the dimensions of how things appear on the screen. */
132 int box, x_margin, y_margin;
134 /* These booleans decide in which way to try to attach the polyominoes. */
135 int left_right, top_bottom;
137 /* Bitmaps for display purposes. */
139 XImage *bitmaps[256];
141 /* Structures used for display purposes if there is not enough memory
142 to allocate bitmaps (or if the screen is small). */
144 XRectangle *rectangles;
146 /* A procedure that may be used to see if certain configurations
148 int (*check_ok)(struct _polyominoesstruct *sp);
150 /* Tells program that solutions are invariant under 180 degree
154 /* This is a variable used in the case that all the polyominoes are identical
155 that will further prune the search tree. Essentially it will be
156 int reason_to_not_attach[nr_polynominoes][nr_polynominoes];
157 Let me first explain the effect it is trying to overcome. Often
158 in the search process, the computer will first try to fit shapes into
159 a region (call it A), and then into another region (call it B) that is
160 essentially disjoint from A. But it may be that it just is not possible
161 to fit shapes into region B. So it fits something into A, and then
162 tries to fit something into B. Failing it fits something else into A,
163 and then tried again to fit something into B. Thus the program is trying
164 again and again to fit something into B, when it should have figured out
165 the first time that it was impossible.
167 To overcome this, everytime we try to attach a piece, we collect the reasons
168 why it cannot be attached (a boolean for each piece that got in the way).
169 If we see that a piece cannot be attached, we detach the other pieces until
170 we have detached at least one piece for which the boolean reason_to_not_attach
173 int *reason_to_not_attach;
178 eraser_state *eraser;
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, target_point;
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;
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;
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<256;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)
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 static void free_polyominoes(polyominoesstruct *sp)
1056 for (n=0;n<sp->nr_polyominoes;n++) {
1057 deallocate(sp->polyomino[n].point, point_type);
1060 deallocate(sp->polyomino, polyomino_type);
1061 deallocate(sp->attach_list, int);
1062 deallocate(sp->rectangles, XRectangle);
1063 deallocate(sp->lines, XSegment);
1064 deallocate(sp->reason_to_not_attach, int);
1065 deallocate(sp->array, int);
1066 deallocate(sp->changed_array, int);
1071 #define set_allocate(p,type,size) p = (type *) malloc(size); \
1072 if ((p)==NULL) {free_polyominoes(sp);return 0;}
1074 #define copy_polyomino(dst,src,new_rand) \
1075 (dst).len=(src).len; \
1076 (dst).max_white = (src).max_white; \
1077 set_allocate((dst).point,point_type,sizeof(point_type)*(src).len); \
1078 (dst).len = (src).len; \
1080 random_permutation((src).len,perm_point); \
1081 for (i=0;i<(src).len;i++) \
1082 (dst).point[i] = (src).point[perm_point[i]]; \
1083 (dst).transform_len = (src).transform_len; \
1085 random_permutation((src).transform_len,perm_transform); \
1086 for (i=0;i<(src).transform_len;i++) \
1087 (dst).transform_list[i] = (src).transform_list[perm_transform[i]]; \
1091 /***************************************************
1092 Puzzle specific initialization routines.
1093 ***************************************************/
1096 int check_pentomino_puzzle(polyominoesstruct *sp)
1098 return check_all_regions_multiple_of(sp, 5) && whites_ok(sp);
1102 int check_hexomino_puzzle(polyominoesstruct *sp)
1104 return check_all_regions_multiple_of(sp, 6) && whites_ok(sp);
1108 int check_tetr_pentomino_puzzle(polyominoesstruct *sp)
1110 return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp);
1114 int check_pent_hexomino_puzzle(polyominoesstruct *sp)
1116 return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp);
1120 int check_heptomino_puzzle(polyominoesstruct *sp)
1122 return check_all_regions_multiple_of(sp, 7) && whites_ok(sp);
1126 int check_octomino_puzzle(polyominoesstruct *sp)
1128 return check_all_regions_multiple_of(sp, 8) && whites_ok(sp);
1132 int check_dekomino_puzzle(polyominoesstruct *sp)
1134 return check_all_regions_multiple_of(sp, 10) && whites_ok(sp);
1138 int check_elevenomino_puzzle(polyominoesstruct *sp)
1140 return check_all_regions_multiple_of(sp, 11) && whites_ok(sp);
1143 static struct {int len; point_type point[4];
1144 int transform_len, transform_list[8], max_white;} tetromino[5] =
1149 {4, {{0,0}, {1,0}, {2,0}, {3,0}},
1150 2, {0, 1, -1, -1, -1, -1, -1, -1}, 2},
1155 {4, {{0,0}, {1,0}, {2,0}, {2,1}},
1156 8, {0, 1, 2, 3, 4, 5, 6, 7}, 2},
1161 {4, {{0,0}, {1,0}, {1,1}, {2,0}},
1162 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1167 {4, {{0,0}, {1,0}, {1,1}, {2,1}},
1168 4, {0, 1, 4, 5, -1, -1, -1, -1}, 2},
1173 {4, {{0,0}, {0,1}, {1,0}, {1,1}},
1174 1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}};
1177 static struct pentomino_struct {int len; point_type point[5];
1178 int transform_len, transform_list[8], max_white;}
1184 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}},
1185 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1190 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}},
1191 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1196 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}},
1197 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1203 {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}},
1204 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1209 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}},
1210 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1215 {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}},
1216 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1222 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}},
1223 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1229 {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}},
1230 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1235 {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}},
1236 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1242 {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}},
1243 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1249 {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}},
1250 1, {0, -1, -1, -1, -1, -1, -1, -1}, 4},
1256 {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}},
1257 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}};
1260 static struct hexomino_struct {int len; point_type point[6];
1261 int transform_len, transform_list[8], max_white;}
1267 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}},
1268 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1273 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}},
1274 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1279 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}},
1280 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1285 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}},
1286 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1292 {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}},
1293 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1298 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}},
1299 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1304 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}},
1305 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1311 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}},
1312 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1318 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}},
1319 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1324 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}},
1325 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1331 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}},
1332 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1337 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}},
1338 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1344 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}},
1345 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1351 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}},
1352 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1357 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}},
1358 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1364 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}},
1365 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1371 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}},
1372 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1378 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}},
1379 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1385 {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1386 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1392 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1393 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1398 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}},
1399 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1405 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}},
1406 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1411 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}},
1412 4, {0, 1, 4, 5, -1, -1, -1, -1}, 4},
1418 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}},
1419 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1425 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}},
1426 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1431 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}},
1432 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1438 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}},
1439 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1445 {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}},
1446 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1451 {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}},
1452 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1458 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}},
1459 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1465 {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}},
1466 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1472 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}},
1473 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1479 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}},
1480 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1486 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}},
1487 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1493 {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}},
1494 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}};
1496 static struct pentomino_struct one_sided_pentomino[60];
1498 static void make_one_sided_pentomino(void)
1503 for (i=0;i<18;i++) {
1504 one_sided_pentomino[j] = pentomino[i];
1506 if (one_sided_pentomino[j].transform_list[t]>=4) {
1507 one_sided_pentomino[j].transform_len = t;
1509 one_sided_pentomino[j] = pentomino[i];
1510 for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u];
1511 one_sided_pentomino[j].transform_len -= t;
1518 static struct hexomino_struct one_sided_hexomino[60];
1520 static void make_one_sided_hexomino(void)
1525 for (i=0;i<35;i++) {
1526 one_sided_hexomino[j] = hexomino[i];
1528 if (one_sided_hexomino[j].transform_list[t]>=4) {
1529 one_sided_hexomino[j].transform_len = t;
1531 one_sided_hexomino[j] = hexomino[i];
1532 for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u];
1533 one_sided_hexomino[j].transform_len -= t;
1541 Find all the ways of placing all twelve pentominoes
1542 into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6.
1546 int set_pentomino_puzzle(polyominoesstruct *sp)
1548 int perm_poly[12], perm_point[5], perm_transform[8], i, p;
1569 sp->nr_polyominoes = 12;
1570 set_allocate(sp->polyomino,polyomino_type,12*sizeof(polyomino_type));
1571 random_permutation(12,perm_poly);
1572 for (p=0;p<12;p++) {
1573 copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1);
1576 sp->check_ok = check_pentomino_puzzle;
1582 Many of the following puzzles are inspired by
1583 http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
1587 Find all the ways of placing all eighteen one-sided pentominoes
1592 int set_one_sided_pentomino_puzzle(polyominoesstruct *sp)
1594 int perm_poly[18], perm_point[5], perm_transform[8], i, p;
1596 make_one_sided_pentomino();
1617 sp->nr_polyominoes = 18;
1618 set_allocate(sp->polyomino,polyomino_type,18*sizeof(polyomino_type));
1619 random_permutation(18,perm_poly);
1620 for (p=0;p<18;p++) {
1621 copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1);
1624 sp->check_ok = check_pentomino_puzzle;
1630 Find all the ways of placing all sixty one-sided hexominoes
1635 int set_one_sided_hexomino_puzzle(polyominoesstruct *sp)
1637 int perm_poly[60], perm_point[6], perm_transform[8], i, p;
1639 make_one_sided_hexomino();
1676 sp->nr_polyominoes = 60;
1677 set_allocate(sp->polyomino,polyomino_type,60*sizeof(polyomino_type));
1678 random_permutation(60,perm_poly);
1679 for (p=0;p<60;p++) {
1680 copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1);
1683 sp->check_ok = check_hexomino_puzzle;
1689 Find all the ways of placing all five tetrominoes and all twelve
1690 pentominoes into a rectangle.
1694 int set_tetr_pentomino_puzzle(polyominoesstruct *sp)
1696 int perm_poly[17], perm_point[5], perm_transform[8], i, p;
1713 sp->nr_polyominoes = 17;
1714 set_allocate(sp->polyomino,polyomino_type,17*sizeof(polyomino_type));
1715 random_permutation(17,perm_poly);
1717 copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1);
1719 for (p=0;p<12;p++) {
1720 copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1);
1723 sp->check_ok = check_tetr_pentomino_puzzle;
1728 Find all the ways of placing all twelve pentominoes and all thirty five
1729 hexominoes into a rectangle whose size is 18x15.
1733 int set_pent_hexomino_puzzle(polyominoesstruct *sp)
1735 int perm_poly[47], perm_point[6], perm_transform[8], i, p;
1760 sp->nr_polyominoes = 47;
1761 set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type));
1762 random_permutation(47,perm_poly);
1763 for (p=0;p<12;p++) {
1764 copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1);
1766 for (p=0;p<35;p++) {
1767 copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1);
1770 sp->check_ok = check_pent_hexomino_puzzle;
1778 Science News September 20, 1986 Vol 130, No 12
1779 Science News November 14, 1987 Vol 132, Pg 310
1785 **** fills a 10x5 rectangle
1789 static struct {int len; point_type point[5];
1790 int transform_len, transform_list[8], max_white;} pentomino1 =
1791 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}},
1792 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3};
1795 int set_pentomino_puzzle1(polyominoesstruct *sp)
1797 int perm_point[5], perm_transform[8], i, p;
1802 sp->nr_polyominoes = 10;
1803 set_allocate(sp->polyomino,polyomino_type,10*sizeof(polyomino_type));
1804 for (p=0;p<10;p++) {
1805 copy_polyomino(sp->polyomino[p],pentomino1,1);
1808 sp->check_ok = check_pentomino_puzzle;
1816 ***** fills a 24x23 rectangle
1820 static struct {int len; point_type point[6];
1821 int transform_len, transform_list[8], max_white;} hexomino1 =
1822 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}},
1823 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1826 int set_hexomino_puzzle1(polyominoesstruct *sp)
1828 int perm_point[6], perm_transform[8], i, p;
1833 sp->nr_polyominoes = 92;
1834 set_allocate(sp->polyomino,polyomino_type,92*sizeof(polyomino_type));
1835 for (p=0;p<92;p++) {
1836 copy_polyomino(sp->polyomino[p],hexomino1,1);
1839 sp->check_ok = check_hexomino_puzzle;
1847 ***** fills a 21x26 rectangle
1849 (All solutions have 180 degree rotational symmetry)
1853 static struct {int len; point_type point[7];
1854 int transform_len, transform_list[8], max_white;} heptomino1 =
1855 {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}},
1856 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1859 int set_heptomino_puzzle1(polyominoesstruct *sp)
1861 int perm_point[7], perm_transform[8], i, p;
1868 sp->nr_polyominoes = 78;
1869 set_allocate(sp->polyomino,polyomino_type,78*sizeof(polyomino_type));
1870 for (p=0;p<78;p+=2) {
1871 copy_polyomino(sp->polyomino[p],heptomino1,1);
1872 copy_polyomino(sp->polyomino[p+1],heptomino1,0);
1875 sp->check_ok = check_heptomino_puzzle;
1880 /* The following puzzles from
1881 Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition
1882 by Solomon W. Golomb Princeton University Press 1994
1888 ***** fills a 28x19 rectangle
1892 int set_heptomino_puzzle2(polyominoesstruct *sp)
1894 int perm_point[7], perm_transform[8], i, p;
1899 sp->nr_polyominoes = 76;
1900 set_allocate(sp->polyomino,polyomino_type,76*sizeof(polyomino_type));
1901 for (p=0;p<76;p++) {
1902 copy_polyomino(sp->polyomino[p],heptomino1,1);
1905 sp->check_ok = check_heptomino_puzzle;
1913 **** fills a 25x22 rectangle
1918 static struct {int len; point_type point[11];
1919 int transform_len, transform_list[8], max_white;} elevenomino1 =
1920 {11, {{0,0}, {1,0}, {2,0},
1921 {0,1}, {1,1}, {2,1}, {3,1},
1922 {0,2}, {1,2}, {2,2}, {3,2}},
1923 8, {0, 1, 2, 3, 4, 5, 6, 7}, 6};
1926 int set_elevenomino_puzzle1(polyominoesstruct *sp)
1928 int perm_point[11], perm_transform[8], i, p;
1935 sp->nr_polyominoes = 50;
1936 set_allocate(sp->polyomino,polyomino_type,50*sizeof(polyomino_type));
1937 for (p=0;p<50;p+=2) {
1938 copy_polyomino(sp->polyomino[p],elevenomino1,1);
1939 copy_polyomino(sp->polyomino[p+1],elevenomino1,0);
1942 sp->check_ok = check_elevenomino_puzzle;
1951 **** fills 32 x 30 rectangle
1956 static struct {int len; point_type point[10];
1957 int transform_len, transform_list[8], max_white;} dekomino1 =
1960 {0,1}, {1,1}, {2,1}, {3,1},
1961 {0,2}, {1,2}, {2,2}, {3,2}},
1962 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1965 int set_dekomino_puzzle1(polyominoesstruct *sp)
1967 int perm_point[10], perm_transform[8], i, p;
1972 sp->nr_polyominoes = 96;
1973 set_allocate(sp->polyomino,polyomino_type,96*sizeof(polyomino_type));
1974 for (p=0;p<96;p++) {
1975 copy_polyomino(sp->polyomino[p],dekomino1,1);
1978 sp->check_ok = check_dekomino_puzzle;
1986 *** fills 96 x 26 rectangle
1991 static struct {int len; point_type point[10];
1992 int transform_len, transform_list[8], max_white;} octomino1 =
1994 {0,1}, {1,1}, {2,1},
1995 {0,2}, {1,2}, {2,2}, {3,2}},
1996 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1999 int set_octomino_puzzle1(polyominoesstruct *sp)
2001 int perm_point[8], perm_transform[8], i, p;
2006 sp->nr_polyominoes = 312;
2007 set_allocate(sp->polyomino,polyomino_type,312*sizeof(polyomino_type));
2008 for (p=0;p<312;p++) {
2009 copy_polyomino(sp->polyomino[p],octomino1,1);
2012 sp->check_ok = check_octomino_puzzle;
2019 * fills 15 x 15 rectangle
2025 int set_pentomino_puzzle2(polyominoesstruct *sp)
2027 int perm_point[5], perm_transform[8], i, p;
2032 sp->nr_polyominoes = 45;
2033 set_allocate(sp->polyomino,polyomino_type,45*sizeof(polyomino_type));
2034 for (p=0;p<45;p++) {
2035 copy_polyomino(sp->polyomino[p],pentomino1,1);
2038 sp->check_ok = check_pentomino_puzzle;
2046 **** fills a 47x33 rectangle
2052 int set_elevenomino_puzzle2(polyominoesstruct *sp)
2054 int perm_point[11], perm_transform[8], i, p;
2059 sp->nr_polyominoes = 141;
2060 set_allocate(sp->polyomino,polyomino_type,141*sizeof(polyomino_type));
2061 for (p=0;p<141;p++) {
2062 copy_polyomino(sp->polyomino[p],elevenomino1,1);
2065 sp->check_ok = check_elevenomino_puzzle;
2070 /**************************************************
2072 **************************************************/
2074 #define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes(sp); return;}
2077 init_polyominoes (ModeInfo * mi)
2079 polyominoesstruct *sp;
2084 if (polyominoeses == NULL) {
2086 = (polyominoesstruct *) calloc(MI_NUM_SCREENS(mi),sizeof (polyominoesstruct)))
2090 sp = &polyominoeses[MI_SCREEN(mi)];
2092 free_polyominoes(sp);
2097 if (MI_IS_FULLRANDOM(mi)) {
2098 sp->identical = (Bool) (LRAND() & 1);
2099 sp->use3D = (Bool) (NRAND(4));
2101 sp->identical = identical;
2104 if (sp->identical) {
2107 if (!set_pentomino_puzzle1(sp))
2111 if (!set_hexomino_puzzle1(sp))
2115 if (!set_heptomino_puzzle1(sp))
2119 if (!set_heptomino_puzzle2(sp))
2123 if (!set_elevenomino_puzzle1(sp))
2127 if (!set_dekomino_puzzle1(sp))
2131 if (!set_octomino_puzzle1(sp))
2135 if (!set_pentomino_puzzle2(sp))
2139 if (!set_elevenomino_puzzle2(sp))
2146 if (!set_pentomino_puzzle(sp))
2150 if (!set_one_sided_pentomino_puzzle(sp))
2154 if (!set_one_sided_hexomino_puzzle(sp))
2158 if (!set_pent_hexomino_puzzle(sp))
2162 if (!set_tetr_pentomino_puzzle(sp))
2168 allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int));
2169 sp->nr_attached = 0;
2171 if (sp->identical) {
2172 allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int));
2175 allocate(sp->array,int,sp->width*sp->height*sizeof(int));
2176 allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int));
2177 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1;
2179 sp->left_right = NRAND(2);
2180 sp->top_bottom = NRAND(2);
2182 box1 = MI_WIDTH(mi)/(sp->width+2);
2183 box2 = MI_HEIGHT(mi)/(sp->height+2);
2189 if (sp->box >= 12) {
2190 sp->box = (sp->box/12)*12;
2191 create_bitmaps(mi,sp);
2192 if (!sp->use_bitmaps)
2196 sp->use_bitmaps = 0;
2198 if (!sp->use_bitmaps) {
2199 allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle));
2200 allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment));
2203 allocate(perm,int,sp->nr_polyominoes*sizeof(int));
2204 random_permutation(sp->nr_polyominoes, perm);
2205 sp->mono = MI_NPIXELS(mi) < 12;
2206 start = NRAND(MI_NPIXELS(mi));
2207 for (i=0;i<sp->nr_polyominoes;i++)
2209 sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi));
2211 sp->polyomino[i+1].color = sp->polyomino[i].color;
2217 sp->polyomino[i].color = MI_WHITE_PIXEL(mi);
2219 sp->polyomino[i].color = MI_BLACK_PIXEL(mi);
2222 if (sp->use_bitmaps) {
2224 sp->border_color = MI_WHITE_PIXEL(mi);
2226 sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi)));
2229 sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2;
2230 sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2;
2235 /* Clear the background. */
2242 draw_polyominoes (ModeInfo * mi)
2244 polyominoesstruct *sp;
2245 int poly_no,point_no,transform_index,done,another_attachment_try;
2246 point_type attach_point;
2249 if (polyominoeses == NULL)
2251 sp = &polyominoeses[MI_SCREEN(mi)];
2255 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2260 if (MI_CYCLES(mi) != 0) {
2261 if (++sp->counter > MI_CYCLES(mi)) {
2263 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2264 #endif /* STANDALONE */
2265 init_polyominoes(mi);
2272 sp->eraser = erase_window (MI_DISPLAY(mi), MI_WINDOW(mi), sp->eraser);
2273 #endif /* STANDALONE */
2274 init_polyominoes(mi);
2278 MI_IS_DRAWN(mi) = True;
2280 if (sp->wait>0) return;
2282 memset(sp->changed_array,0,sp->width*sp->height*sizeof(int));
2284 poly_no = first_poly_no(sp);
2286 transform_index = 0;
2288 another_attachment_try = 1;
2289 find_blank(sp,&attach_point);
2290 if (sp->identical && sp->nr_attached < sp->nr_polyominoes)
2291 memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int));
2293 if (sp->nr_attached < sp->nr_polyominoes) {
2294 while (!done && another_attachment_try) {
2295 done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0));
2296 if (done && sp->rot180) {
2297 poly_no = first_poly_no(sp);
2298 done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0));
2300 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2303 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2307 if (sp->identical) {
2309 if (sp->nr_attached == 0)
2312 detach_until=sp->nr_attached-1;
2313 if (sp->nr_attached < sp->nr_polyominoes)
2314 while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0)
2316 while (sp->nr_attached>detach_until) {
2318 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2319 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2320 if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes)
2321 for (i=0;i<sp->nr_polyominoes;i++)
2322 REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i);
2324 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2330 if (sp->nr_attached == 0)
2334 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2335 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2337 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2342 if (sp->use_bitmaps)
2343 draw_with_bitmaps(mi,sp);
2345 draw_without_bitmaps(mi,sp);
2347 if (sp->nr_attached == sp->nr_polyominoes)
2354 reshape_polyominoes(ModeInfo * mi, int width, int height)
2356 XClearWindow (MI_DISPLAY (mi), MI_WINDOW(mi));
2357 init_polyominoes (mi);
2361 release_polyominoes(ModeInfo * mi)
2365 if (polyominoeses != NULL) {
2366 for (screen=0;screen<MI_NUM_SCREENS(mi); screen++)
2367 free_polyominoes(&polyominoeses[screen]);
2368 (void) free((void *) polyominoeses);
2369 polyominoeses = (polyominoesstruct *) NULL;
2374 refresh_polyominoes (ModeInfo * mi)
2379 XSCREENSAVER_MODULE ("Polyominoes", polyominoes)
2381 #endif /* MODE_polyominoes */