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 PROGCLASS "Polyominoes"
38 #define HACK_INIT init_polyominoes
39 #define HACK_DRAW draw_polyominoes
40 #define polyominoes_opts xlockmore_opts
41 #define DEFAULTS "*delay: 10000 \n" \
45 #include "xlockmore.h" /* in xscreensaver distribution */
47 #include <X11/Xutil.h>
48 #else /* STANDALONE */
49 #include "xlock.h" /* in xlockmore distribution */
50 #endif /* STANDALONE */
52 #ifdef MODE_polyominoes
53 #define DEF_IDENTICAL "False"
54 #define DEF_PLAIN "False"
56 static Bool identical;
59 static XrmOptionDescRec opts[] =
61 {"-identical", ".polyominoes.identical", XrmoptionNoArg, "on"},
62 {"+identical", ".polyominoes.identical", XrmoptionNoArg, "off"},
63 {"-plain", ".polyominoes.plain", XrmoptionNoArg, "on"},
64 {"+plain", ".polyominoes.plain", XrmoptionNoArg, "off"}
66 static argtype vars[] =
68 {&identical, "identical", "Identical", DEF_IDENTICAL, t_Bool},
69 {&plain, "plain", "Plain", DEF_PLAIN, t_Bool}
71 static OptionStruct desc[] =
73 {"-/+identical", "turn on/off puzzles where the polyomino pieces are identical"},
74 {"-/+plain", "turn on/off plain pieces"}
77 ModeSpecOpt polyominoes_opts =
78 {sizeof opts / sizeof opts[0], opts,
79 sizeof vars / sizeof vars[0], vars, desc};
82 ModStruct polyominoes_description = {
83 "polyominoes", "init_polyominoes", "draw_polyominoes", "release_polyominoes",
84 "refresh_polyominoes", "init_polyominoes", (char *) NULL, &polyominoes_opts,
85 6000, 1, 8192, 1, 64, 1.0, "",
86 "Shows attempts to place polyominoes into a rectangle", 0, NULL
91 /* Each polyomino is described by several quantities:
92 len: the number of squares in the polyomino;
93 point: the list of points;
94 tranform_len: the number of items in transform_list;
95 transform_list: a list of transformations that need to be done in order
96 to get all rotations and reflections (see the function
98 max_white: the maximum number of white squares covered if polyomino
99 is placed on a chess board;
100 color: it's display color;
101 attached: whether it is currently attached to the rectangle;
102 attach_point: point on rectangle where attached;
103 point_no: the number of the point where it is attached;
104 transform_index: which element of transform_list is currently being used.
107 typedef struct {int x,y;} point_type;
109 typedef struct {int len; point_type *point;
110 int transform_len, transform_list[8], max_white;
113 point_type attach_point;
114 int point_no, transform_index;} polyomino_type;
117 typedef struct _polyominoesstruct{
121 unsigned border_color;
124 polyomino_type *polyomino;
126 Bool identical, use3D;
130 /* The array that tells where the polyominoes are attached. */
131 int *array, *changed_array;
133 /* These specify the dimensions of how things appear on the screen. */
134 int box, x_margin, y_margin;
136 /* These booleans decide in which way to try to attach the polyominoes. */
137 int left_right, top_bottom;
139 /* Bitmaps for display purposes. */
141 XImage *bitmaps[256];
143 /* Structures used for display purposes if there is not enough memory
144 to allocate bitmaps (or if the screen is small). */
146 XRectangle *rectangles;
148 /* A procedure that may be used to see if certain configurations
150 int (*check_ok)(struct _polyominoesstruct *sp);
152 /* Tells program that solutions are invariant under 180 degree
156 /* This is a variable used in the case that all the polyominoes are identical
157 that will further prune the search tree. Essentially it will be
158 int reason_to_not_attach[nr_polynominoes][nr_polynominoes];
159 Let me first explain the effect it is trying to overcome. Often
160 in the search process, the computer will first try to fit shapes into
161 a region (call it A), and then into another region (call it B) that is
162 essentially disjoint from A. But it may be that it just is not possible
163 to fit shapes into region B. So it fits something into A, and then
164 tries to fit something into B. Failing it fits something else into A,
165 and then tried again to fit something into B. Thus the program is trying
166 again and again to fit something into B, when it should have figured out
167 the first time that it was impossible.
169 To overcome this, everytime we try to attach a piece, we collect the reasons
170 why it cannot be attached (a boolean for each piece that got in the way).
171 If we see that a piece cannot be attached, we detach the other pieces until
172 we have detached at least one piece for which the boolean reason_to_not_attach
175 int *reason_to_not_attach;
180 #define ARRAY(x,y) (sp->array[(x)*sp->height+(y)])
181 #define CHANGED_ARRAY(x,y) (sp->changed_array[(x)*sp->height+(y)])
182 #define ARRAY_P(p) (sp->array[(p).x*sp->height+(p).y])
183 #define CHANGED_ARRAY_P(p) (sp->changed_array[(p).x*sp->height+(p).y])
184 #define ARR(x,y) (((x)<0||(x)>=sp->width||(y)<0||(y)>=sp->height)?-2:ARRAY(x,y))
186 #define REASON_TO_NOT_ATTACH(x,y) (sp->reason_to_not_attach[(x)*sp->nr_polyominoes+(y)])
188 #define ROUND8(n) ((((n)+7)/8)*8)
190 /* Defines to index the bitmaps. A set bit indicates that an edge or
191 corner is required. */
196 #define LEFT_UP (1<<4)
197 #define LEFT_DOWN (1<<5)
198 #define RIGHT_UP (1<<6)
199 #define RIGHT_DOWN (1<<7)
200 #define IS_LEFT(n) ((n) & LEFT)
201 #define IS_RIGHT(n) ((n) & RIGHT)
202 #define IS_UP(n) ((n) & UP)
203 #define IS_DOWN(n) ((n) & DOWN)
204 #define IS_LEFT_UP(n) ((n) & LEFT_UP)
205 #define IS_LEFT_DOWN(n) ((n) & LEFT_DOWN)
206 #define IS_RIGHT_UP(n) ((n) & RIGHT_UP)
207 #define IS_RIGHT_DOWN(n) ((n) & RIGHT_DOWN)
209 /* Defines to access the bitmaps. */
210 #define BITNO(x,y) ((x)+(y)*ROUND8(sp->box))
211 #define SETBIT(n,x,y) {data[BITNO(x,y)/8] |= 1<<(BITNO(x,y)%8);}
212 #define RESBIT(n,x,y) {data[BITNO(x,y)/8] &= ~(1<<(BITNO(x,y)%8));}
213 #define TWOTHIRDSBIT(n,x,y) {if ((x+y-1)%3) SETBIT(n,x,y) else RESBIT(n,x,y)}
214 #define HALFBIT(n,x,y) {if ((x-y)%2) SETBIT(n,x,y) else RESBIT(n,x,y)}
215 #define THIRDBIT(n,x,y) {if (!((x-y-1)%3)) SETBIT(n,x,y) else RESBIT(n,x,y)}
216 #define THREEQUARTERSBIT(n,x,y) \
217 {if ((y%2)||((x+2+y/2+1)%2)) SETBIT(n,x,y) else RESBIT(n,x,y)}
218 #define NOTHALFBIT(n,x,y) {if ((x-y)%2) RESBIT(n,x,y) else SETBIT(n,x,y)}
220 /* Parameters for bitmaps. */
221 #define G ((sp->box/45)+1) /* 1/2 of gap between polyominoes. */
222 #define T ((sp->box<=12)?1:(G*2)) /* Thickness of walls of polyominoes. */
223 #define R ((sp->box<=12)?1:(G*6)) /* Amount of rounding. */
224 #define RT ((sp->box<=12)?1:(G*3)) /* Thickness of wall of rounded parts.
225 Here 3 is an approximation to 2 sqrt(2). */
226 #define RR 0 /* Roof ridge thickness */
229 /* A list of those bitmaps we need to create to display any pentomino. */
230 /* (not used right now because it does not seem to work for hexonimoes.) */
232 static int bitmaps_needed[] =
234 LEFT_UP|LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
236 LEFT|RIGHT_UP|RIGHT_DOWN,
237 RIGHT|LEFT_UP|LEFT_DOWN,
238 UP|LEFT_DOWN|RIGHT_DOWN,
239 DOWN|LEFT_UP|RIGHT_UP,
249 /* These needed for hexonimoes*/
254 LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
255 LEFT_UP|RIGHT_UP|RIGHT_DOWN,
256 LEFT_UP|LEFT_DOWN|RIGHT_DOWN,
257 LEFT_UP|LEFT_DOWN|RIGHT_UP,
279 static int bitmap_needed(int n) {
282 for (i=0;bitmaps_needed[i]!=-1;i++)
283 if (n == bitmaps_needed[i])
290 /* Some debugging routines.
292 static void print_board(polyominoesstruct *sp) {
294 for (y=0;y<sp->height;y++) {
295 for (x=0;x<sp->width;x++)
296 if (ARRAY(x,y) == -1)
299 fprintf(stderr,"%c",'a'+ARRAY(x,y));
300 fprintf(stderr,"\n");
302 fprintf(stderr,"\n");
305 static void print_points(point_type *point, int len) {
309 fprintf(stderr,"(%d %d) ",point[i].x,point[i].y);
312 static void print_polyomino(polyomino_type poly) {
315 print_points(poly.point,poly.len);
316 fprintf(stderr,"\n");
317 for (i=0;i<poly.transform_len;i++)
318 fprintf(stderr,"%d ",poly.transform_list[i]);
319 fprintf(stderr,"\n");
323 static polyominoesstruct *polyominoeses = (polyominoesstruct *) NULL;
326 void random_permutation(int n, int a[]) {
329 for (i=0;i<n;i++) a[i] = -1;
343 /************************************************************
344 These are the routines for manipulating the polyominoes and
345 attaching and detaching them from the rectangle.
346 ************************************************************/
348 static void transform(point_type in, point_type offset, int transform_no,
349 point_type attach_point, point_type *out) {
350 switch (transform_no) {
351 case 0: out->x=in.x-offset.x+attach_point.x;
352 out->y=in.y-offset.y+attach_point.y;
354 case 1: out->x=-(in.y-offset.y)+attach_point.x;
355 out->y=in.x-offset.x+attach_point.y;
357 case 2: out->x=-(in.x-offset.x)+attach_point.x;
358 out->y=-(in.y-offset.y)+attach_point.y;
360 case 3: out->x=in.y-offset.y+attach_point.x;
361 out->y=-(in.x-offset.x)+attach_point.y;
363 case 4: out->x=-(in.x-offset.x)+attach_point.x;
364 out->y=in.y-offset.y+attach_point.y;
366 case 5: out->x=in.y-offset.y+attach_point.x;
367 out->y=in.x-offset.x+attach_point.y;
369 case 6: out->x=in.x-offset.x+attach_point.x;
370 out->y=-(in.y-offset.y)+attach_point.y;
372 case 7: out->x=-(in.y-offset.y)+attach_point.x;
373 out->y=-(in.x-offset.x)+attach_point.y;
378 static int first_poly_no(polyominoesstruct *sp) {
382 while(poly_no<sp->nr_polyominoes && sp->polyomino[poly_no].attached)
387 static void next_poly_no(polyominoesstruct *sp, int *poly_no) {
390 *poly_no = sp->nr_polyominoes;
394 } while (*poly_no<sp->nr_polyominoes && sp->polyomino[*poly_no].attached);
398 /* check_all_regions_multiple_of looks for connected regions of
399 blank spaces, and returns 0 if it finds a connected region containing
400 a number of blanks that is not a multiple of n.
403 static void count_adjacent_blanks(polyominoesstruct *sp, int *count, int x, int y, int blank_mark) {
405 if (ARRAY(x,y) == -1) {
407 ARRAY(x,y) = blank_mark;
408 if (x>=1) count_adjacent_blanks(sp, count,x-1,y,blank_mark);
409 if (x<sp->width-1) count_adjacent_blanks(sp, count,x+1,y,blank_mark);
410 if (y>=1) count_adjacent_blanks(sp, count,x,y-1,blank_mark);
411 if (y<sp->height-1) count_adjacent_blanks(sp, count,x,y+1,blank_mark);
415 static int check_all_regions_multiple_of(polyominoesstruct *sp, int n) {
416 int x,y,count,good = 1;
418 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
420 count_adjacent_blanks(sp, &count,x,y,-2);
424 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
425 if (ARRAY(x,y) == -2)
431 static int check_all_regions_positive_combination_of(polyominoesstruct *sp, int m, int n) {
432 int x,y,count,good = 1;
434 for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
436 count_adjacent_blanks(sp, &count,x,y,-2);
438 for (;count>=0 && !good;count-=m)
442 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
443 if (ARRAY(x,y) == -2)
449 static int find_smallest_blank_component(polyominoesstruct *sp) {
450 int x,y,size,smallest_size,blank_mark,smallest_mark;
452 smallest_mark = blank_mark = -10;
453 smallest_size = 1000000000;
454 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y) == -1) {
456 count_adjacent_blanks(sp, &size,x,y,blank_mark);
457 if (size<smallest_size) {
458 smallest_mark = blank_mark;
459 smallest_size = size;
464 return smallest_mark;
467 /* "Chess board" check - see init_max_whites_list above for more details.
469 /* If the rectangle is alternatively covered by white and black
470 squares (chess board style), then this gives the list of
471 the maximal possible whites covered by each polyomino. It
472 is used by the function whites_ok which makes sure that the
473 array has a valid number of white or black remaining blanks left.
476 static int whites_ok(polyominoesstruct *sp) {
477 int x,y,poly_no,whites=0,blacks=0,max_white=0,min_white=0;
479 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
480 if (ARRAY(x,y) == -1 && (x+y)%2) whites++;
481 if (ARRAY(x,y) == -1 && (x+y+1)%2) blacks++;
483 for (poly_no=0;poly_no<sp->nr_polyominoes;poly_no++) if (!sp->polyomino[poly_no].attached) {
484 max_white += sp->polyomino[poly_no].max_white;
485 min_white += sp->polyomino[poly_no].len - sp->polyomino[poly_no].max_white;
487 return (min_white <= blacks && min_white <= whites
488 && blacks <= max_white && whites <= max_white);
491 /* This routine looks at the point (x,y) and sees how many polyominoes
492 and all their various transforms may be attached there.
496 score_point(polyominoesstruct *sp, int x, int y, int min_score_so_far) {
497 int poly_no, point_no, transform_index, i, attachable;
498 point_type attach_point, target_point;
501 if (x>=1 && x<sp->width-1 && y>=1 && y<sp->height-1 &&
502 ARRAY(x-1,y-1)<0 && ARRAY(x-1,y)<0 && ARRAY(x-1,y+1)<0 &&
503 ARRAY(x+1,y-1)<0 && ARRAY(x+1,y)<0 && ARRAY(x+1,y+1)<0 &&
504 ARRAY(x,y-1)<0 && ARRAY(x,y+1)<0)
509 for (poly_no=first_poly_no(sp);poly_no<sp->nr_polyominoes;next_poly_no(sp,&poly_no))
510 if (!sp->polyomino[poly_no].attached) {
511 for (point_no=0;point_no<sp->polyomino[poly_no].len;point_no++)
512 for (transform_index=0;transform_index<sp->polyomino[poly_no].transform_len;transform_index++) {
514 for (i=0;i<sp->polyomino[poly_no].len;i++) {
515 transform(sp->polyomino[poly_no].point[i],
516 sp->polyomino[poly_no].point[point_no],
517 sp->polyomino[poly_no].transform_list[transform_index],
518 attach_point, &target_point);
519 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
520 && (target_point.y>=0) && (target_point.y<sp->height)
521 && (ARRAY_P(target_point)<0))) {
528 if (score>=min_score_so_far)
537 static void find_blank(polyominoesstruct *sp, point_type *point) {
538 int score, worst_score;
542 blank_mark = find_smallest_blank_component(sp);
544 worst_score = 1000000;
545 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y)==blank_mark) {
546 score = 100*score_point(sp,x,y,worst_score);
548 if (sp->left_right) score += 10*x;
549 else score += 10*(sp->width-1-x);
550 if (sp->top_bottom) score += y;
551 else score += (sp->height-1-y);
553 if (score<worst_score) {
560 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
561 if (ARRAY(x,y)<0) ARRAY(x,y) = -1;
564 /* Detaches the most recently attached polyomino. */
567 void detach(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index, point_type *attach_point, int rot180) {
569 point_type target_point;
571 if (sp->nr_attached == 0) return;
573 *poly_no = sp->attach_list[sp->nr_attached];
574 *point_no = sp->polyomino[*poly_no].point_no;
575 *transform_index = sp->polyomino[*poly_no].transform_index;
576 *attach_point = sp->polyomino[*poly_no].attach_point;
577 for (i=0;i<sp->polyomino[*poly_no].len;i++) {
578 transform(sp->polyomino[*poly_no].point[i],
579 sp->polyomino[*poly_no].point[*point_no],
580 sp->polyomino[*poly_no].transform_list[*transform_index]^(rot180<<1),
581 *attach_point, &target_point);
582 ARRAY_P(target_point) = -1;
583 CHANGED_ARRAY_P(target_point) = 1;
586 sp->polyomino[*poly_no].attached = 0;
589 /* Attempts to attach a polyomino at point (x,y) at the
590 point_no-th point of that polyomino, using the transform
591 transform_no. Returns 1 if successful.
595 int attach(polyominoesstruct *sp, int poly_no, int point_no, int transform_index, point_type attach_point, int rot180,
596 int *reason_to_not_attach) {
597 point_type target_point;
599 int attachable = 1, worst_reason_not_to_attach = 1000000000;
602 attach_point.x = sp->width-1-attach_point.x;
603 attach_point.y = sp->height-1-attach_point.y;
606 if (sp->polyomino[poly_no].attached)
609 for (i=0;i<sp->polyomino[poly_no].len;i++) {
610 transform(sp->polyomino[poly_no].point[i],
611 sp->polyomino[poly_no].point[point_no],
612 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
613 attach_point, &target_point);
614 if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
615 && (target_point.y>=0) && (target_point.y<sp->height)
616 && (ARRAY_P(target_point) == -1))) {
619 if ((target_point.x>=0) && (target_point.x<sp->width)
620 && (target_point.y>=0) && (target_point.y<sp->height)
621 && (ARRAY_P(target_point) >= 0)
622 && (ARRAY_P(target_point)<worst_reason_not_to_attach))
623 worst_reason_not_to_attach = ARRAY_P(target_point);
630 if (sp->identical && !attachable) {
631 if (worst_reason_not_to_attach < 1000000000)
632 reason_to_not_attach[worst_reason_not_to_attach] = 1;
636 for (i=0;i<sp->polyomino[poly_no].len;i++) {
637 transform(sp->polyomino[poly_no].point[i],
638 sp->polyomino[poly_no].point[point_no],
639 sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
640 attach_point, &target_point);
641 ARRAY_P(target_point) = poly_no;
642 CHANGED_ARRAY_P(target_point) = 1;
645 sp->attach_list[sp->nr_attached] = poly_no;
648 sp->polyomino[poly_no].attached = 1;
649 sp->polyomino[poly_no].point_no = point_no;
650 sp->polyomino[poly_no].attach_point = attach_point;
651 sp->polyomino[poly_no].transform_index = transform_index;
653 if (!sp->check_ok(sp)) {
654 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,rot180);
662 int next_attach_try(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index) {
664 (*transform_index)++;
665 if (*transform_index>=sp->polyomino[*poly_no].transform_len) {
666 *transform_index = 0;
668 if (*point_no>=sp->polyomino[*poly_no].len) {
670 next_poly_no(sp,poly_no);
671 if (*poly_no>=sp->nr_polyominoes) {
672 *poly_no = first_poly_no(sp);
681 /*******************************************************
683 *******************************************************/
686 draw_without_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
687 Display *display = MI_DISPLAY(mi);
688 Window window = MI_WINDOW(mi);
690 int x,y,poly_no,nr_lines,nr_rectangles;
692 XSetLineAttributes(display,gc,sp->box/10+1,LineSolid,CapRound,JoinRound);
694 for (poly_no=-1;poly_no<sp->nr_polyominoes;poly_no++) {
696 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++)
697 if (CHANGED_ARRAY(x,y) && ARRAY(x,y) == poly_no) {
698 sp->rectangles[nr_rectangles].x = sp->x_margin + sp->box*x;
699 sp->rectangles[nr_rectangles].y = sp->y_margin + sp->box*y;
700 sp->rectangles[nr_rectangles].width = sp->box;
701 sp->rectangles[nr_rectangles].height = sp->box;
705 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
707 XSetForeground(display, gc, sp->polyomino[poly_no].color);
708 XFillRectangles(display, window, gc, sp->rectangles, nr_rectangles);
711 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
714 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
715 if (ARRAY(x,y) == -1 && ARRAY(x+1,y) == -1
716 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x+1,y))) {
717 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
718 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
719 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
720 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
724 XDrawSegments(display, window, gc, sp->lines, nr_lines);
727 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
728 if (ARRAY(x,y) == -1 && ARRAY(x,y+1) == -1
729 && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x,y+1))) {
730 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
731 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
732 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
733 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
737 XDrawSegments(display, window, gc, sp->lines, nr_lines);
739 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
740 XDrawRectangle(display, window, gc, sp->x_margin, sp->y_margin, sp->box*sp->width, sp->box*sp->height);
742 XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
745 for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
746 if (ARRAY(x+1,y) != ARRAY(x,y)) {
747 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
748 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
749 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
750 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
754 XDrawSegments(display, window, gc, sp->lines, nr_lines);
757 for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
758 if (ARRAY(x,y+1) != ARRAY(x,y)) {
759 sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
760 sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
761 sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
762 sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
766 XDrawSegments(display, window, gc, sp->lines, nr_lines);
767 XSetLineAttributes(display,gc,1,LineSolid,CapRound,JoinRound);
771 static void create_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
775 for (n=0;n<256;n++) {
777 /* Avoid duplication of identical bitmaps. */
778 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
779 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_UP];
780 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
781 sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_DOWN];
782 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
783 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_UP];
784 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
785 sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_DOWN];
787 else /* if (bitmap_needed(n)) */ {
788 data = (char *) malloc(sizeof(char)*(sp->box*ROUND8(sp->box)/8));
794 for (y=0;y<sp->box;y++) for (x=0;x<sp->box;x++) {
796 #ifdef SMALL_BELLYBUTTON
797 if (x >= sp->box / 2 && x <= sp->box / 2 + 1 &&
798 y >= sp->box / 2 && y <= sp->box / 2 + 1)
803 } else if ((x>=y && x<=sp->box-y-1 && IS_UP(n))
804 || (x<=y && x<=sp->box-y-1 && y<sp->box/2 && !IS_LEFT(n))
805 || (x>=y && x>=sp->box-y-1 && y<sp->box/2 && !IS_RIGHT(n)))
807 else if ((x<=y && x<=sp->box-y-1 && IS_LEFT(n))
808 || (x>=y && x<=sp->box-y-1 && x<sp->box/2 && !IS_UP(n))
809 || (x<=y && x>=sp->box-y-1 && x<sp->box/2 && !IS_DOWN(n)))
811 else if ((x>=y && x>=sp->box-y-1 && IS_RIGHT(n))
812 || (x>=y && x<=sp->box-y-1 && x>=sp->box/2 && !IS_UP(n))
813 || (x<=y && x>=sp->box-y-1 && x>=sp->box/2 && !IS_DOWN(n)))
815 else if ((x<=y && x>=sp->box-y-1 && IS_DOWN(n))
816 || (x<=y && x<=sp->box-y-1 && y>=sp->box/2 && !IS_LEFT(n))
817 || (x>=y && x>=sp->box-y-1 && y>=sp->box/2 && !IS_RIGHT(n)))
822 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
825 for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++)
826 SETBIT(n,sp->box-1-x,y)
828 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
831 for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++)
832 SETBIT(n,x,sp->box-1-y)
834 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
837 for (y=0;y<sp->box;y++) for (x=0;x<G;x++)
838 RESBIT(n,sp->box-1-x,y)
840 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
843 for (x=0;x<sp->box;x++) for (y=0;y<G;y++)
844 RESBIT(n,x,sp->box-1-y)
846 if (IS_LEFT(n) && IS_UP(n))
848 for (y=G;y<=R+2*G-x;y++) {
854 if (IS_LEFT(n) && IS_DOWN(n))
856 for (y=G;y<=R+2*G-x;y++) {
858 SETBIT(n,x,sp->box-1-y)
860 RESBIT(n,x,sp->box-1-y)
862 if (IS_RIGHT(n) && IS_UP(n))
864 for (y=G;y<=R+2*G-x;y++) {
866 SETBIT(n,sp->box-1-x,y)
868 RESBIT(n,sp->box-1-x,y)
870 if (IS_RIGHT(n) && IS_DOWN(n))
872 for (y=G;y<=R+2*G-x;y++) {
874 SETBIT(n,sp->box-1-x,sp->box-1-y)
876 RESBIT(n,sp->box-1-x,sp->box-1-y)
879 if (!IS_LEFT(n) && !IS_UP(n) && IS_LEFT_UP(n)) {
880 for (x=0;x<G;x++) for(y=0;y<G;y++)
882 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
884 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
887 if (!IS_LEFT(n) && !IS_DOWN(n) && IS_LEFT_DOWN(n)) {
888 for (x=0;x<G;x++) for(y=0;y<G;y++)
889 RESBIT(n,x,sp->box-1-y)
890 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
891 SETBIT(n,x,sp->box-1-y)
892 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
893 SETBIT(n,x,sp->box-1-y)
895 if (!IS_RIGHT(n) && !IS_UP(n) && IS_RIGHT_UP(n)) {
896 for (x=0;x<G;x++) for(y=0;y<G;y++)
897 RESBIT(n,sp->box-1-x,y)
898 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
899 SETBIT(n,sp->box-1-x,y)
900 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
901 SETBIT(n,sp->box-1-x,y)
903 if (!IS_RIGHT(n) && !IS_DOWN(n) && IS_RIGHT_DOWN(n)) {
904 for (x=0;x<G;x++) for(y=0;y<G;y++)
905 RESBIT(n,sp->box-1-x,sp->box-1-y)
906 for (x=G;x<G+T;x++) for(y=0;y<G;y++)
907 SETBIT(n,sp->box-1-x,sp->box-1-y)
908 for (x=0;x<G+T;x++) for(y=G;y<G+T;y++)
909 SETBIT(n,sp->box-1-x,sp->box-1-y)
912 #ifdef LARGE_BELLYBUTTON
914 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
915 for (x=0;x<G+T;x++) for(y=0;y<G+T;y++)
917 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
918 for (x=0;x<G+T;x++) for(y=sp->box-G-T;y<sp->box;y++)
920 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
921 for (x=sp->box-G-T;x<sp->box;x++) for(y=0;y<G+T;y++)
923 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
924 for (x=sp->box-G-T;x<sp->box;x++) for(y=sp->box-G-T;y<sp->box;y++)
931 if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
932 for (x=0;x<sp->box/2-RR;x++) for(y=0;y<sp->box/2-RR;y++)
933 THREEQUARTERSBIT(n,x,y)
934 if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
935 for (x=0;x<sp->box/2-RR;x++) for(y=sp->box/2+RR;y<sp->box;y++)
936 THREEQUARTERSBIT(n,x,y)
937 if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
938 for (x=sp->box/2+RR;x<sp->box;x++) for(y=0;y<sp->box/2-RR;y++)
939 THREEQUARTERSBIT(n,x,y)
940 if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
941 for (x=sp->box/2+RR;x<sp->box;x++) for(y=sp->box/2+RR;y<sp->box;y++)
942 THREEQUARTERSBIT(n,x,y)
945 sp->bitmaps[n] = XCreateImage(MI_DISPLAY(mi), MI_VISUAL(mi), 1, XYBitmap,
946 0, data, sp->box, sp->box, 8, 0);
947 if (sp->bitmaps[n] == None) {
952 sp->bitmaps[n]->byte_order = MSBFirst;
953 sp->bitmaps[n]->bitmap_unit = 8;
954 sp->bitmaps[n]->bitmap_bit_order = LSBFirst;
961 static void draw_with_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
962 Display *display = MI_DISPLAY(mi);
963 Window window = MI_WINDOW(mi);
965 int x,y,t,bitmap_index;
967 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
968 if (ARRAY(x,y) == -1) {
969 if (CHANGED_ARRAY(x,y)) {
970 XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
971 XFillRectangle(display,window,gc,
972 sp->x_margin + sp->box*x,
973 sp->y_margin + sp->box*y,
978 XSetForeground(display, gc, sp->polyomino[ARRAY(x,y)].color);
980 if (ARR(x,y) != ARR(x-1,y)) bitmap_index |= LEFT;
981 if (ARR(x,y) != ARR(x+1,y)) bitmap_index |= RIGHT;
982 if (ARR(x,y) != ARR(x,y-1)) bitmap_index |= UP;
983 if (ARR(x,y) != ARR(x,y+1)) bitmap_index |= DOWN;
984 if (ARR(x,y) != ARR(x-1,y-1)) bitmap_index |= LEFT_UP;
985 if (ARR(x,y) != ARR(x-1,y+1)) bitmap_index |= LEFT_DOWN;
986 if (ARR(x,y) != ARR(x+1,y-1)) bitmap_index |= RIGHT_UP;
987 if (ARR(x,y) != ARR(x+1,y+1)) bitmap_index |= RIGHT_DOWN;
988 (void) XPutImage(display,window,gc,
989 sp->bitmaps[bitmap_index],
991 sp->x_margin + sp->box*x,
992 sp->y_margin + sp->box*y,
997 XSetForeground(display, gc, sp->border_color);
999 XDrawRectangle(display,window,gc,
1000 sp->x_margin-t-1,sp->y_margin-t-1,
1001 sp->box*sp->width+1+2*t, sp->box*sp->height+1+2*t);
1006 /***************************************************
1007 Routines to initialise and close down polyominoes.
1008 ***************************************************/
1010 static void free_bitmaps(polyominoesstruct *sp) {
1014 /* Don't bother to free duplicates */
1015 if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
1016 sp->bitmaps[n] = None;
1017 else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
1018 sp->bitmaps[n] = None;
1019 else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
1020 sp->bitmaps[n] = None;
1021 else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
1022 sp->bitmaps[n] = None;
1024 else if (sp->bitmaps[n] != None) {
1025 XDestroyImage(sp->bitmaps[n]);
1026 sp->bitmaps[n] = None;
1030 #define deallocate(p,t) if ((p)!=NULL) {free(p); p=(t*)NULL;}
1032 static void free_polyominoes(polyominoesstruct *sp) {
1035 for (n=0;n<sp->nr_polyominoes;n++) {
1036 deallocate(sp->polyomino[n].point, point_type);
1039 deallocate(sp->polyomino, polyomino_type);
1040 deallocate(sp->attach_list, int);
1041 deallocate(sp->rectangles, XRectangle);
1042 deallocate(sp->lines, XSegment);
1043 deallocate(sp->reason_to_not_attach, int);
1044 deallocate(sp->array, int);
1045 deallocate(sp->changed_array, int);
1050 #define set_allocate(p,type,size) p = (type *) malloc(size); \
1051 if ((p)==NULL) {free_polyominoes(sp);return 0;}
1053 #define copy_polyomino(dst,src,new_rand) \
1054 (dst).len=(src).len; \
1055 (dst).max_white = (src).max_white; \
1056 set_allocate((dst).point,point_type,sizeof(point_type)*(src).len); \
1057 (dst).len = (src).len; \
1059 random_permutation((src).len,perm_point); \
1060 for (i=0;i<(src).len;i++) \
1061 (dst).point[i] = (src).point[perm_point[i]]; \
1062 (dst).transform_len = (src).transform_len; \
1064 random_permutation((src).transform_len,perm_transform); \
1065 for (i=0;i<(src).transform_len;i++) \
1066 (dst).transform_list[i] = (src).transform_list[perm_transform[i]]; \
1070 /***************************************************
1071 Puzzle specific initialization routines.
1072 ***************************************************/
1075 int check_pentomino_puzzle(polyominoesstruct *sp) {
1076 return check_all_regions_multiple_of(sp, 5) && whites_ok(sp);
1080 int check_hexomino_puzzle(polyominoesstruct *sp) {
1081 return check_all_regions_multiple_of(sp, 6) && whites_ok(sp);
1085 int check_tetr_pentomino_puzzle(polyominoesstruct *sp) {
1086 return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp);
1090 int check_pent_hexomino_puzzle(polyominoesstruct *sp) {
1091 return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp);
1095 int check_heptomino_puzzle(polyominoesstruct *sp) {
1096 return check_all_regions_multiple_of(sp, 7) && whites_ok(sp);
1100 int check_octomino_puzzle(polyominoesstruct *sp) {
1101 return check_all_regions_multiple_of(sp, 8) && whites_ok(sp);
1105 int check_dekomino_puzzle(polyominoesstruct *sp) {
1106 return check_all_regions_multiple_of(sp, 10) && whites_ok(sp);
1110 int check_elevenomino_puzzle(polyominoesstruct *sp) {
1111 return check_all_regions_multiple_of(sp, 11) && whites_ok(sp);
1114 static struct {int len; point_type point[4];
1115 int transform_len, transform_list[8], max_white;} tetromino[5] =
1120 {4, {{0,0}, {1,0}, {2,0}, {3,0}},
1121 2, {0, 1, -1, -1, -1, -1, -1, -1}, 2},
1126 {4, {{0,0}, {1,0}, {2,0}, {2,1}},
1127 8, {0, 1, 2, 3, 4, 5, 6, 7}, 2},
1132 {4, {{0,0}, {1,0}, {1,1}, {2,0}},
1133 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1138 {4, {{0,0}, {1,0}, {1,1}, {2,1}},
1139 4, {0, 1, 4, 5, -1, -1, -1, -1}, 2},
1144 {4, {{0,0}, {0,1}, {1,0}, {1,1}},
1145 1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}};
1148 static struct pentomino_struct {int len; point_type point[5];
1149 int transform_len, transform_list[8], max_white;}
1155 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}},
1156 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1161 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}},
1162 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1167 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}},
1168 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1174 {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}},
1175 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1180 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}},
1181 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1186 {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}},
1187 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1193 {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}},
1194 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1200 {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}},
1201 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1206 {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}},
1207 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1213 {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}},
1214 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1220 {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}},
1221 1, {0, -1, -1, -1, -1, -1, -1, -1}, 4},
1227 {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}},
1228 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}};
1231 static struct hexomino_struct {int len; point_type point[6];
1232 int transform_len, transform_list[8], max_white;}
1238 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}},
1239 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1244 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}},
1245 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1250 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}},
1251 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1256 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}},
1257 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1263 {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}},
1264 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1269 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}},
1270 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1275 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}},
1276 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1282 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}},
1283 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1289 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}},
1290 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1295 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}},
1296 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1302 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}},
1303 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1308 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}},
1309 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1315 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}},
1316 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1322 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}},
1323 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1328 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}},
1329 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1335 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}},
1336 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1342 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}},
1343 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1349 {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}},
1350 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1356 {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1357 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1363 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}},
1364 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1369 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}},
1370 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
1376 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}},
1377 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1382 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}},
1383 4, {0, 1, 4, 5, -1, -1, -1, -1}, 4},
1389 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}},
1390 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1396 {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}},
1397 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
1402 {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}},
1403 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1409 {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}},
1410 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1416 {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}},
1417 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
1422 {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}},
1423 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
1429 {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}},
1430 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1436 {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}},
1437 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1443 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}},
1444 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
1450 {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}},
1451 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1457 {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}},
1458 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
1464 {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}},
1465 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}};
1467 static struct pentomino_struct one_sided_pentomino[60];
1469 void make_one_sided_pentomino(void) {
1473 for (i=0;i<18;i++) {
1474 one_sided_pentomino[j] = pentomino[i];
1476 if (one_sided_pentomino[j].transform_list[t]>=4) {
1477 one_sided_pentomino[j].transform_len = t;
1479 one_sided_pentomino[j] = pentomino[i];
1480 for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u];
1481 one_sided_pentomino[j].transform_len -= t;
1488 static struct hexomino_struct one_sided_hexomino[60];
1490 void make_one_sided_hexomino(void) {
1494 for (i=0;i<35;i++) {
1495 one_sided_hexomino[j] = hexomino[i];
1497 if (one_sided_hexomino[j].transform_list[t]>=4) {
1498 one_sided_hexomino[j].transform_len = t;
1500 one_sided_hexomino[j] = hexomino[i];
1501 for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u];
1502 one_sided_hexomino[j].transform_len -= t;
1510 Find all the ways of placing all twelve pentominoes
1511 into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6.
1515 int set_pentomino_puzzle(polyominoesstruct *sp) {
1516 int perm_poly[12], perm_point[5], perm_transform[8], i, p;
1537 sp->nr_polyominoes = 12;
1538 set_allocate(sp->polyomino,polyomino_type,12*sizeof(polyomino_type));
1539 random_permutation(12,perm_poly);
1540 for (p=0;p<12;p++) {
1541 copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1);
1544 sp->check_ok = check_pentomino_puzzle;
1550 Many of the following puzzles are inspired by
1551 http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
1555 Find all the ways of placing all eighteen one-sided pentominoes
1560 int set_one_sided_pentomino_puzzle(polyominoesstruct *sp) {
1561 int perm_poly[18], perm_point[5], perm_transform[8], i, p;
1563 make_one_sided_pentomino();
1584 sp->nr_polyominoes = 18;
1585 set_allocate(sp->polyomino,polyomino_type,18*sizeof(polyomino_type));
1586 random_permutation(18,perm_poly);
1587 for (p=0;p<18;p++) {
1588 copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1);
1591 sp->check_ok = check_pentomino_puzzle;
1597 Find all the ways of placing all sixty one-sided hexominoes
1602 int set_one_sided_hexomino_puzzle(polyominoesstruct *sp) {
1603 int perm_poly[60], perm_point[6], perm_transform[8], i, p;
1605 make_one_sided_hexomino();
1642 sp->nr_polyominoes = 60;
1643 set_allocate(sp->polyomino,polyomino_type,60*sizeof(polyomino_type));
1644 random_permutation(60,perm_poly);
1645 for (p=0;p<60;p++) {
1646 copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1);
1649 sp->check_ok = check_hexomino_puzzle;
1655 Find all the ways of placing all five tetrominoes and all twelve
1656 pentominoes into a rectangle.
1660 int set_tetr_pentomino_puzzle(polyominoesstruct *sp) {
1661 int perm_poly[17], perm_point[5], perm_transform[8], i, p;
1678 sp->nr_polyominoes = 17;
1679 set_allocate(sp->polyomino,polyomino_type,17*sizeof(polyomino_type));
1680 random_permutation(17,perm_poly);
1682 copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1);
1684 for (p=0;p<12;p++) {
1685 copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1);
1688 sp->check_ok = check_tetr_pentomino_puzzle;
1693 Find all the ways of placing all twelve pentominoes and all thirty five
1694 hexominoes into a rectangle whose size is 18x15.
1698 int set_pent_hexomino_puzzle(polyominoesstruct *sp) {
1699 int perm_poly[47], perm_point[6], perm_transform[8], i, p;
1724 sp->nr_polyominoes = 47;
1725 set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type));
1726 random_permutation(47,perm_poly);
1727 for (p=0;p<12;p++) {
1728 copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1);
1730 for (p=0;p<35;p++) {
1731 copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1);
1734 sp->check_ok = check_pent_hexomino_puzzle;
1742 Science News September 20, 1986 Vol 130, No 12
1743 Science News November 14, 1987 Vol 132, Pg 310
1749 **** fills a 10x5 rectangle
1753 static struct {int len; point_type point[5];
1754 int transform_len, transform_list[8], max_white;} pentomino1 =
1755 {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}},
1756 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3};
1759 int set_pentomino_puzzle1(polyominoesstruct *sp) {
1760 int perm_point[5], perm_transform[8], i, p;
1765 sp->nr_polyominoes = 10;
1766 set_allocate(sp->polyomino,polyomino_type,10*sizeof(polyomino_type));
1767 for (p=0;p<10;p++) {
1768 copy_polyomino(sp->polyomino[p],pentomino1,1);
1771 sp->check_ok = check_pentomino_puzzle;
1779 ***** fills a 24x23 rectangle
1783 static struct {int len; point_type point[6];
1784 int transform_len, transform_list[8], max_white;} hexomino1 =
1785 {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}},
1786 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1789 int set_hexomino_puzzle1(polyominoesstruct *sp) {
1790 int perm_point[6], perm_transform[8], i, p;
1795 sp->nr_polyominoes = 92;
1796 set_allocate(sp->polyomino,polyomino_type,92*sizeof(polyomino_type));
1797 for (p=0;p<92;p++) {
1798 copy_polyomino(sp->polyomino[p],hexomino1,1);
1801 sp->check_ok = check_hexomino_puzzle;
1809 ***** fills a 21x26 rectangle
1811 (All solutions have 180 degree rotational symmetry)
1815 static struct {int len; point_type point[7];
1816 int transform_len, transform_list[8], max_white;} heptomino1 =
1817 {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}},
1818 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
1821 int set_heptomino_puzzle1(polyominoesstruct *sp) {
1822 int perm_point[7], perm_transform[8], i, p;
1829 sp->nr_polyominoes = 78;
1830 set_allocate(sp->polyomino,polyomino_type,78*sizeof(polyomino_type));
1831 for (p=0;p<78;p+=2) {
1832 copy_polyomino(sp->polyomino[p],heptomino1,1);
1833 copy_polyomino(sp->polyomino[p+1],heptomino1,0);
1836 sp->check_ok = check_heptomino_puzzle;
1841 /* The following puzzles from
1842 Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition
1843 by Solomon W. Golomb Princeton University Press 1994
1849 ***** fills a 28x19 rectangle
1853 int set_heptomino_puzzle2(polyominoesstruct *sp) {
1854 int perm_point[7], perm_transform[8], i, p;
1859 sp->nr_polyominoes = 76;
1860 set_allocate(sp->polyomino,polyomino_type,76*sizeof(polyomino_type));
1861 for (p=0;p<76;p++) {
1862 copy_polyomino(sp->polyomino[p],heptomino1,1);
1865 sp->check_ok = check_heptomino_puzzle;
1873 **** fills a 25x22 rectangle
1878 static struct {int len; point_type point[11];
1879 int transform_len, transform_list[8], max_white;} elevenomino1 =
1880 {11, {{0,0}, {1,0}, {2,0},
1881 {0,1}, {1,1}, {2,1}, {3,1},
1882 {0,2}, {1,2}, {2,2}, {3,2}},
1883 8, {0, 1, 2, 3, 4, 5, 6, 7}, 6};
1886 int set_elevenomino_puzzle1(polyominoesstruct *sp) {
1887 int perm_point[11], perm_transform[8], i, p;
1894 sp->nr_polyominoes = 50;
1895 set_allocate(sp->polyomino,polyomino_type,50*sizeof(polyomino_type));
1896 for (p=0;p<50;p+=2) {
1897 copy_polyomino(sp->polyomino[p],elevenomino1,1);
1898 copy_polyomino(sp->polyomino[p+1],elevenomino1,0);
1901 sp->check_ok = check_elevenomino_puzzle;
1910 **** fills 32 x 30 rectangle
1915 static struct {int len; point_type point[10];
1916 int transform_len, transform_list[8], max_white;} dekomino1 =
1919 {0,1}, {1,1}, {2,1}, {3,1},
1920 {0,2}, {1,2}, {2,2}, {3,2}},
1921 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1924 int set_dekomino_puzzle1(polyominoesstruct *sp) {
1925 int perm_point[10], perm_transform[8], i, p;
1930 sp->nr_polyominoes = 96;
1931 set_allocate(sp->polyomino,polyomino_type,96*sizeof(polyomino_type));
1932 for (p=0;p<96;p++) {
1933 copy_polyomino(sp->polyomino[p],dekomino1,1);
1936 sp->check_ok = check_dekomino_puzzle;
1944 *** fills 96 x 26 rectangle
1949 static struct {int len; point_type point[10];
1950 int transform_len, transform_list[8], max_white;} octomino1 =
1952 {0,1}, {1,1}, {2,1},
1953 {0,2}, {1,2}, {2,2}, {3,2}},
1954 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
1957 int set_octomino_puzzle1(polyominoesstruct *sp) {
1958 int perm_point[8], perm_transform[8], i, p;
1963 sp->nr_polyominoes = 312;
1964 set_allocate(sp->polyomino,polyomino_type,312*sizeof(polyomino_type));
1965 for (p=0;p<312;p++) {
1966 copy_polyomino(sp->polyomino[p],octomino1,1);
1969 sp->check_ok = check_octomino_puzzle;
1976 * fills 15 x 15 rectangle
1982 int set_pentomino_puzzle2(polyominoesstruct *sp) {
1983 int perm_point[5], perm_transform[8], i, p;
1988 sp->nr_polyominoes = 45;
1989 set_allocate(sp->polyomino,polyomino_type,45*sizeof(polyomino_type));
1990 for (p=0;p<45;p++) {
1991 copy_polyomino(sp->polyomino[p],pentomino1,1);
1994 sp->check_ok = check_pentomino_puzzle;
2002 **** fills a 47x33 rectangle
2008 int set_elevenomino_puzzle2(polyominoesstruct *sp) {
2009 int perm_point[11], perm_transform[8], i, p;
2014 sp->nr_polyominoes = 141;
2015 set_allocate(sp->polyomino,polyomino_type,141*sizeof(polyomino_type));
2016 for (p=0;p<141;p++) {
2017 copy_polyomino(sp->polyomino[p],elevenomino1,1);
2020 sp->check_ok = check_elevenomino_puzzle;
2025 /**************************************************
2027 **************************************************/
2029 #define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes(sp); return;}
2032 init_polyominoes(ModeInfo * mi) {
2033 polyominoesstruct *sp;
2038 if (polyominoeses == NULL) {
2040 = (polyominoesstruct *) calloc(MI_NUM_SCREENS(mi),sizeof (polyominoesstruct)))
2044 sp = &polyominoeses[MI_SCREEN(mi)];
2046 free_polyominoes(sp);
2051 if (MI_IS_FULLRANDOM(mi)) {
2052 sp->identical = (Bool) (LRAND() & 1);
2053 sp->use3D = (Bool) (NRAND(4));
2055 sp->identical = identical;
2058 if (sp->identical) {
2061 if (!set_pentomino_puzzle1(sp))
2065 if (!set_hexomino_puzzle1(sp))
2069 if (!set_heptomino_puzzle1(sp))
2073 if (!set_heptomino_puzzle2(sp))
2077 if (!set_elevenomino_puzzle1(sp))
2081 if (!set_dekomino_puzzle1(sp))
2085 if (!set_octomino_puzzle1(sp))
2089 if (!set_pentomino_puzzle2(sp))
2093 if (!set_elevenomino_puzzle2(sp))
2100 if (!set_pentomino_puzzle(sp))
2104 if (!set_one_sided_pentomino_puzzle(sp))
2108 if (!set_one_sided_hexomino_puzzle(sp))
2112 if (!set_pent_hexomino_puzzle(sp))
2116 if (!set_tetr_pentomino_puzzle(sp))
2122 allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int));
2123 sp->nr_attached = 0;
2125 if (sp->identical) {
2126 allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int));
2129 allocate(sp->array,int,sp->width*sp->height*sizeof(int));
2130 allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int));
2131 for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1;
2133 sp->left_right = NRAND(2);
2134 sp->top_bottom = NRAND(2);
2136 box1 = MI_WIDTH(mi)/(sp->width+2);
2137 box2 = MI_HEIGHT(mi)/(sp->height+2);
2143 if (sp->box >= 12) {
2144 sp->box = (sp->box/12)*12;
2145 create_bitmaps(mi,sp);
2146 if (!sp->use_bitmaps)
2150 sp->use_bitmaps = 0;
2152 if (!sp->use_bitmaps) {
2153 allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle));
2154 allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment));
2157 allocate(perm,int,sp->nr_polyominoes*sizeof(int));
2158 random_permutation(sp->nr_polyominoes, perm);
2159 sp->mono = MI_NPIXELS(mi) < 12;
2160 start = NRAND(MI_NPIXELS(mi));
2161 for (i=0;i<sp->nr_polyominoes;i++)
2163 sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi));
2165 sp->polyomino[i+1].color = sp->polyomino[i].color;
2171 sp->polyomino[i].color = MI_WHITE_PIXEL(mi);
2173 sp->polyomino[i].color = MI_BLACK_PIXEL(mi);
2176 if (sp->use_bitmaps) {
2178 sp->border_color = MI_WHITE_PIXEL(mi);
2180 sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi)));
2183 sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2;
2184 sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2;
2188 /* Clear the background. */
2194 draw_polyominoes(ModeInfo * mi) {
2195 polyominoesstruct *sp;
2196 int poly_no,point_no,transform_index,done,another_attachment_try;
2197 point_type attach_point;
2200 if (polyominoeses == NULL)
2202 sp = &polyominoeses[MI_SCREEN(mi)];
2204 if (MI_CYCLES(mi) != 0) {
2205 if (++sp->counter > MI_CYCLES(mi)) {
2207 erase_full_window(MI_DISPLAY(mi), MI_WINDOW(mi));
2208 #endif /* STANDALONE */
2209 init_polyominoes(mi);
2216 erase_full_window(MI_DISPLAY(mi), MI_WINDOW(mi));
2217 #endif /* STANDALONE */
2218 init_polyominoes(mi);
2222 MI_IS_DRAWN(mi) = True;
2224 if (sp->wait>0) return;
2226 memset(sp->changed_array,0,sp->width*sp->height*sizeof(int));
2228 poly_no = first_poly_no(sp);
2230 transform_index = 0;
2232 another_attachment_try = 1;
2233 find_blank(sp,&attach_point);
2234 if (sp->identical && sp->nr_attached < sp->nr_polyominoes)
2235 memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int));
2237 if (sp->nr_attached < sp->nr_polyominoes) {
2238 while (!done && another_attachment_try) {
2239 done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0));
2240 if (done && sp->rot180) {
2241 poly_no = first_poly_no(sp);
2242 done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0));
2244 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2247 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2251 if (sp->identical) {
2253 if (sp->nr_attached == 0)
2256 detach_until=sp->nr_attached-1;
2257 if (sp->nr_attached < sp->nr_polyominoes)
2258 while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0)
2260 while (sp->nr_attached>detach_until) {
2262 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2263 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2264 if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes)
2265 for (i=0;i<sp->nr_polyominoes;i++)
2266 REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i);
2268 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2274 if (sp->nr_attached == 0)
2278 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
2279 detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
2281 another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
2286 if (sp->use_bitmaps)
2287 draw_with_bitmaps(mi,sp);
2289 draw_without_bitmaps(mi,sp);
2291 if (sp->nr_attached == sp->nr_polyominoes)
2298 release_polyominoes(ModeInfo * mi) {
2301 if (polyominoeses != NULL) {
2302 for (screen=0;screen<MI_NUM_SCREENS(mi); screen++)
2303 free_polyominoes(&polyominoeses[screen]);
2304 (void) free((void *) polyominoeses);
2305 polyominoeses = (polyominoesstruct *) NULL;
2310 refresh_polyominoes(ModeInfo * mi) {
2314 #endif /* MODE_polyominoes */