diff options
Diffstat (limited to 'hacks/polyominoes.c')
| -rw-r--r-- | hacks/polyominoes.c | 2368 |
1 files changed, 2368 insertions, 0 deletions
diff --git a/hacks/polyominoes.c b/hacks/polyominoes.c new file mode 100644 index 0000000..b87c3d3 --- /dev/null +++ b/hacks/polyominoes.c @@ -0,0 +1,2368 @@ +/* -*- Mode: C; tab-width: 4 -*- */ +/* polyominoes --- Shows attempts to place polyominoes into a rectangle */ + +#if 0 +static const char sccsid[] = "@(#)polyominoes.c 5.01 2000/12/18 xlockmore"; +#endif + +/* + * Copyright (c) 2000 by Stephen Montgomery-Smith <stephen@math.missouri.edu> + * + * Permission to use, copy, modify, and distribute this software and its + * documentation for any purpose and without fee is hereby granted, + * provided that the above copyright notice appear in all copies and that + * both that copyright notice and this permission notice appear in + * supporting documentation. + * + * This file is provided AS IS with no warranties of any kind. The author + * shall have no liability with respect to the infringement of copyrights, + * trade secrets or any patents by this file or any part thereof. In no + * event will the author be liable for any lost revenue or profits or + * other special, indirect and consequential damages. + * + * Revision History: + * 07-Jan-2001: Made improvement to the search algorithm for the puzzles + * involving identical polyominoes (via the variable + * reason_to_not_attach). By Stephen Montgomery-Smith. + * 20-Dec-2000: Added more puzzles at David Bagley's request. + * 27-Nov-2000: Adapted from euler2d.c Copyright (c) 2000 by Stephen + * Montgomery-Smith + * 05-Jun-2000: Adapted from flow.c Copyright (c) 1996 by Tim Auckland + * 18-Jul-1996: Adapted from swarm.c Copyright (c) 1991 by Patrick J. Naughton. + * 31-Aug-1990: Adapted from xswarm by Jeff Butterworth. (butterwo@ncsc.org) + */ + +#ifdef STANDALONE +# define MODE_polyominoes +#define DEFAULTS "*delay: 10000 \n" \ + "*cycles: 2000 \n" \ + "*ncolors: 64 \n" \ + "*fpsSolid: true \n" \ + +# define release_polyominoes 0 +# define reshape_polyominoes 0 +# define polyominoes_handle_event 0 +# define SMOOTH_COLORS +# include "xlockmore.h" /* in xscreensaver distribution */ +#else /* STANDALONE */ +# include "xlock.h" /* in xlockmore distribution */ +#endif /* STANDALONE */ + +#ifdef MODE_polyominoes +#define DEF_IDENTICAL "False" +#define DEF_PLAIN "False" + +static Bool identical; +static Bool plain; + +#undef countof +#define countof(x) (sizeof((x))/sizeof((*x))) + +static XrmOptionDescRec opts[] = +{ + {"-identical", ".polyominoes.identical", XrmoptionNoArg, "on"}, + {"+identical", ".polyominoes.identical", XrmoptionNoArg, "off"}, + {"-plain", ".polyominoes.plain", XrmoptionNoArg, "on"}, + {"+plain", ".polyominoes.plain", XrmoptionNoArg, "off"} +}; +static argtype vars[] = +{ + {&identical, "identical", "Identical", DEF_IDENTICAL, t_Bool}, + {&plain, "plain", "Plain", DEF_PLAIN, t_Bool} +}; +static OptionStruct desc[] = +{ + {"-/+identical", "turn on/off puzzles where the polyomino pieces are identical"}, + {"-/+plain", "turn on/off plain pieces"} +}; + +ENTRYPOINT ModeSpecOpt polyominoes_opts = +{sizeof opts / sizeof opts[0], opts, + sizeof vars / sizeof vars[0], vars, desc}; + +#ifdef USE_MODULES +ModStruct polyominoes_description = { + "polyominoes", "init_polyominoes", "draw_polyominoes", (char *) NULL, + "refresh_polyominoes", "init_polyominoes", "free_polyominoes", + &polyominoes_opts, 6000, 1, 8192, 1, 64, 1.0, "", + "Shows attempts to place polyominoes into a rectangle", 0, NULL +}; + +#endif + +/* Each polyomino is described by several quantities: + len: the number of squares in the polyomino; + point: the list of points; + tranform_len: the number of items in transform_list; + transform_list: a list of transformations that need to be done in order + to get all rotations and reflections (see the function + transform below); + max_white: the maximum number of white squares covered if polyomino + is placed on a chess board; + color: it's display color; + attached: whether it is currently attached to the rectangle; + attach_point: point on rectangle where attached; + point_no: the number of the point where it is attached; + transform_index: which element of transform_list is currently being used. +*/ + +typedef struct {int x,y;} point_type; + +typedef struct {int len; point_type *point; + int transform_len, transform_list[8], max_white; + unsigned long color; + int attached; + point_type attach_point; + int point_no, transform_index;} polyomino_type; + + +typedef struct _polyominoesstruct{ + int wait; + + int width, height; + unsigned border_color; + int mono; + + polyomino_type *polyomino; + int nr_polyominoes; + Bool identical, use3D; + int *attach_list; + int nr_attached; + +/* The array that tells where the polyominoes are attached. */ + int *array, *changed_array; + +/* These specify the dimensions of how things appear on the screen. */ + int box, x_margin, y_margin; + +/* These booleans decide in which way to try to attach the polyominoes. */ + int left_right, top_bottom; + +/* Bitmaps for display purposes. */ + int use_bitmaps; + XImage *bitmaps[256]; + +/* Structures used for display purposes if there is not enough memory + to allocate bitmaps (or if the screen is small). */ + XSegment *lines; + XRectangle *rectangles; + +/* A procedure that may be used to see if certain configurations + are permissible. */ + int (*check_ok)(struct _polyominoesstruct *sp); + +/* Tells program that solutions are invariant under 180 degree + rotation. */ + int rot180; + +/* This is a variable used in the case that all the polyominoes are identical + that will further prune the search tree. Essentially it will be + int reason_to_not_attach[nr_polynominoes][nr_polynominoes]; + Let me first explain the effect it is trying to overcome. Often + in the search process, the computer will first try to fit shapes into + a region (call it A), and then into another region (call it B) that is + essentially disjoint from A. But it may be that it just is not possible + to fit shapes into region B. So it fits something into A, and then + tries to fit something into B. Failing it fits something else into A, + and then tried again to fit something into B. Thus the program is trying + again and again to fit something into B, when it should have figured out + the first time that it was impossible. + + To overcome this, everytime we try to attach a piece, we collect the reasons + why it cannot be attached (a boolean for each piece that got in the way). + If we see that a piece cannot be attached, we detach the other pieces until + we have detached at least one piece for which the boolean reason_to_not_attach + is set. +*/ + int *reason_to_not_attach; + + int counter; +} polyominoesstruct; + +#define ARRAY(x,y) (sp->array[(x)*sp->height+(y)]) +#define CHANGED_ARRAY(x,y) (sp->changed_array[(x)*sp->height+(y)]) +#define ARRAY_P(p) (sp->array[(p).x*sp->height+(p).y]) +#define CHANGED_ARRAY_P(p) (sp->changed_array[(p).x*sp->height+(p).y]) +#define ARR(x,y) (((x)<0||(x)>=sp->width||(y)<0||(y)>=sp->height)?-2:ARRAY(x,y)) + +#define REASON_TO_NOT_ATTACH(x,y) (sp->reason_to_not_attach[(x)*sp->nr_polyominoes+(y)]) + +#define ROUND8(n) ((((n)+7)/8)*8) + +/* Defines to index the bitmaps. A set bit indicates that an edge or + corner is required. */ +#define LEFT (1<<0) +#define RIGHT (1<<1) +#define UP (1<<2) +#define DOWN (1<<3) +#define LEFT_UP (1<<4) +#define LEFT_DOWN (1<<5) +#define RIGHT_UP (1<<6) +#define RIGHT_DOWN (1<<7) +#define IS_LEFT(n) ((n) & LEFT) +#define IS_RIGHT(n) ((n) & RIGHT) +#define IS_UP(n) ((n) & UP) +#define IS_DOWN(n) ((n) & DOWN) +#define IS_LEFT_UP(n) ((n) & LEFT_UP) +#define IS_LEFT_DOWN(n) ((n) & LEFT_DOWN) +#define IS_RIGHT_UP(n) ((n) & RIGHT_UP) +#define IS_RIGHT_DOWN(n) ((n) & RIGHT_DOWN) + +/* Defines to access the bitmaps. */ +#define BITNO(x,y) ((x)+(y)*ROUND8(sp->box)) +#define SETBIT(n,x,y) {data[BITNO(x,y)/8] |= 1<<(BITNO(x,y)%8);} +#define RESBIT(n,x,y) {data[BITNO(x,y)/8] &= ~(1<<(BITNO(x,y)%8));} +#define TWOTHIRDSBIT(n,x,y) {if ((x+y-1)%3) SETBIT(n,x,y) else RESBIT(n,x,y)} +#define HALFBIT(n,x,y) {if ((x-y)%2) SETBIT(n,x,y) else RESBIT(n,x,y)} +#define THIRDBIT(n,x,y) {if (!((x-y-1)%3)) SETBIT(n,x,y) else RESBIT(n,x,y)} +#define THREEQUARTERSBIT(n,x,y) \ + {if ((y%2)||((x+2+y/2+1)%2)) SETBIT(n,x,y) else RESBIT(n,x,y)} +#define NOTHALFBIT(n,x,y) {if ((x-y)%2) RESBIT(n,x,y) else SETBIT(n,x,y)} + +/* Parameters for bitmaps. */ +#define G ((sp->box/45)+1) /* 1/2 of gap between polyominoes. */ +#define T ((sp->box<=12)?1:(G*2)) /* Thickness of walls of polyominoes. */ +#define R ((sp->box<=12)?1:(G*6)) /* Amount of rounding. */ +#define RT ((sp->box<=12)?1:(G*3)) /* Thickness of wall of rounded parts. + Here 3 is an approximation to 2 sqrt(2). */ +#define RR 0 /* Roof ridge thickness */ + +#if 0 +/* A list of those bitmaps we need to create to display any pentomino. */ +/* (not used right now because it does not seem to work for hexonimoes.) */ + +static int bitmaps_needed[] = +{ + LEFT_UP|LEFT_DOWN|RIGHT_UP|RIGHT_DOWN, + + LEFT|RIGHT_UP|RIGHT_DOWN, + RIGHT|LEFT_UP|LEFT_DOWN, + UP|LEFT_DOWN|RIGHT_DOWN, + DOWN|LEFT_UP|RIGHT_UP, + LEFT|RIGHT_UP, + RIGHT|LEFT_UP, + UP|LEFT_DOWN, + DOWN|LEFT_UP, + LEFT|RIGHT_DOWN, + RIGHT|LEFT_DOWN, + UP|RIGHT_DOWN, + DOWN|RIGHT_UP, + +/* These needed for hexonimoes*/ + LEFT, + RIGHT, + UP, + DOWN, + LEFT_DOWN|RIGHT_UP|RIGHT_DOWN, + LEFT_UP|RIGHT_UP|RIGHT_DOWN, + LEFT_UP|LEFT_DOWN|RIGHT_DOWN, + LEFT_UP|LEFT_DOWN|RIGHT_UP, + + LEFT|UP|RIGHT_DOWN, + LEFT|DOWN|RIGHT_UP, + RIGHT|UP|LEFT_DOWN, + RIGHT|DOWN|LEFT_UP, + LEFT|UP, + LEFT|DOWN, + RIGHT|UP, + RIGHT|DOWN, + + LEFT|RIGHT, + UP|DOWN, + + RIGHT|UP|DOWN, + LEFT|UP|DOWN, + LEFT|RIGHT|DOWN, + LEFT|RIGHT|UP, + + -1 +}; + +static int bitmap_needed(int n) +{ + int i; + + for (i=0;bitmaps_needed[i]!=-1;i++) + if (n == bitmaps_needed[i]) + return 1; + return 0; +} + +#endif + +/* Some debugging routines. + +static void print_board(polyominoesstruct *sp) +{ + int x,y; + for (y=0;y<sp->height;y++) { + for (x=0;x<sp->width;x++) + if (ARRAY(x,y) == -1) + fprintf(stderr," "); + else + fprintf(stderr,"%c",'a'+ARRAY(x,y)); + fprintf(stderr,"\n"); + } + fprintf(stderr,"\n"); +} + +static void print_points(point_type *point, int len) +{ + int i; + + for (i=0;i<len;i++) + fprintf(stderr,"(%d %d) ",point[i].x,point[i].y); +} + +static void print_polyomino(polyomino_type poly) +{ + int i; + + print_points(poly.point,poly.len); + fprintf(stderr,"\n"); + for (i=0;i<poly.transform_len;i++) + fprintf(stderr,"%d ",poly.transform_list[i]); + fprintf(stderr,"\n"); +} +*/ + +static polyominoesstruct *polyominoeses = (polyominoesstruct *) NULL; + +static +void random_permutation(int n, int a[]) +{ + int i,j,k,r; + + for (i=0;i<n;i++) a[i] = -1; + for (i=0;i<n;i++) { + r=NRAND(n-i); + k=0; + while(a[k]!=-1) k++; + for (j=0;j<r;j++) { + k++; + while(a[k]!=-1) k++; + } + a[k]=i; + } +} + + +/************************************************************ +These are the routines for manipulating the polyominoes and +attaching and detaching them from the rectangle. +************************************************************/ + +static void transform(point_type in, point_type offset, int transform_no, + point_type attach_point, point_type *out) { + switch (transform_no) { + case 0: out->x=in.x-offset.x+attach_point.x; + out->y=in.y-offset.y+attach_point.y; + break; + case 1: out->x=-(in.y-offset.y)+attach_point.x; + out->y=in.x-offset.x+attach_point.y; + break; + case 2: out->x=-(in.x-offset.x)+attach_point.x; + out->y=-(in.y-offset.y)+attach_point.y; + break; + case 3: out->x=in.y-offset.y+attach_point.x; + out->y=-(in.x-offset.x)+attach_point.y; + break; + case 4: out->x=-(in.x-offset.x)+attach_point.x; + out->y=in.y-offset.y+attach_point.y; + break; + case 5: out->x=in.y-offset.y+attach_point.x; + out->y=in.x-offset.x+attach_point.y; + break; + case 6: out->x=in.x-offset.x+attach_point.x; + out->y=-(in.y-offset.y)+attach_point.y; + break; + case 7: out->x=-(in.y-offset.y)+attach_point.x; + out->y=-(in.x-offset.x)+attach_point.y; + break; + } +} + +static int first_poly_no(polyominoesstruct *sp) +{ + int poly_no; + + poly_no = 0; + while(poly_no<sp->nr_polyominoes && sp->polyomino[poly_no].attached) + poly_no++; + return poly_no; +} + +static void next_poly_no(polyominoesstruct *sp, int *poly_no) +{ + + if (sp->identical) { + *poly_no = sp->nr_polyominoes; + } else { + do { + (*poly_no)++; + } while (*poly_no<sp->nr_polyominoes && sp->polyomino[*poly_no].attached); + } +} + +/* check_all_regions_multiple_of looks for connected regions of + blank spaces, and returns 0 if it finds a connected region containing + a number of blanks that is not a multiple of n. +*/ + +static void count_adjacent_blanks(polyominoesstruct *sp, int *count, int x, int y, int blank_mark) +{ + + if (ARRAY(x,y) == -1) { + (*count)++; + ARRAY(x,y) = blank_mark; + if (x>=1) count_adjacent_blanks(sp, count,x-1,y,blank_mark); + if (x<sp->width-1) count_adjacent_blanks(sp, count,x+1,y,blank_mark); + if (y>=1) count_adjacent_blanks(sp, count,x,y-1,blank_mark); + if (y<sp->height-1) count_adjacent_blanks(sp, count,x,y+1,blank_mark); + } +} + +static int check_all_regions_multiple_of(polyominoesstruct *sp, int n) +{ + int x,y,count,good = 1; + + for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) { + count = 0; + count_adjacent_blanks(sp, &count,x,y,-2); + good = count%n == 0; + } + + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) + if (ARRAY(x,y) == -2) + ARRAY(x,y) = -1; + + return good; +} + +static int check_all_regions_positive_combination_of(polyominoesstruct *sp, int m, int n) +{ + int x,y,count,good = 1; + + for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) { + count = 0; + count_adjacent_blanks(sp, &count,x,y,-2); + good = 0; + for (;count>=0 && !good;count-=m) + good = count%n == 0; + } + + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) + if (ARRAY(x,y) == -2) + ARRAY(x,y) = -1; + + return good; +} + +static int find_smallest_blank_component(polyominoesstruct *sp) +{ + int x,y,size,smallest_size,blank_mark,smallest_mark; + + smallest_mark = blank_mark = -10; + smallest_size = 1000000000; + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y) == -1) { + size = 0; + count_adjacent_blanks(sp, &size,x,y,blank_mark); + if (size<smallest_size) { + smallest_mark = blank_mark; + smallest_size = size; + } + blank_mark--; + } + + return smallest_mark; +} + +/* "Chess board" check - see init_max_whites_list above for more details. +*/ +/* If the rectangle is alternatively covered by white and black + squares (chess board style), then this gives the list of + the maximal possible whites covered by each polyomino. It + is used by the function whites_ok which makes sure that the + array has a valid number of white or black remaining blanks left. +*/ + +static int whites_ok(polyominoesstruct *sp) +{ + int x,y,poly_no,whites=0,blacks=0,max_white=0,min_white=0; + + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) { + if (ARRAY(x,y) == -1 && (x+y)%2) whites++; + if (ARRAY(x,y) == -1 && (x+y+1)%2) blacks++; + } + for (poly_no=0;poly_no<sp->nr_polyominoes;poly_no++) if (!sp->polyomino[poly_no].attached) { + max_white += sp->polyomino[poly_no].max_white; + min_white += sp->polyomino[poly_no].len - sp->polyomino[poly_no].max_white; + } + return (min_white <= blacks && min_white <= whites + && blacks <= max_white && whites <= max_white); +} + +/* This routine looks at the point (x,y) and sees how many polyominoes + and all their various transforms may be attached there. +*/ + +static int +score_point(polyominoesstruct *sp, int x, int y, int min_score_so_far) +{ + int poly_no, point_no, transform_index, i, attachable; + point_type attach_point = { 0, 0 }, target_point = { 0, 0 }; + int score = 0; + + if (x>=1 && x<sp->width-1 && y>=1 && y<sp->height-1 && + ARRAY(x-1,y-1)<0 && ARRAY(x-1,y)<0 && ARRAY(x-1,y+1)<0 && + ARRAY(x+1,y-1)<0 && ARRAY(x+1,y)<0 && ARRAY(x+1,y+1)<0 && + ARRAY(x,y-1)<0 && ARRAY(x,y+1)<0) + return 10000; + + attach_point.x = x; + attach_point.y = y; + for (poly_no=first_poly_no(sp);poly_no<sp->nr_polyominoes;next_poly_no(sp,&poly_no)) + if (!sp->polyomino[poly_no].attached) { + for (point_no=0;point_no<sp->polyomino[poly_no].len;point_no++) + for (transform_index=0;transform_index<sp->polyomino[poly_no].transform_len;transform_index++) { + attachable = 1; + for (i=0;i<sp->polyomino[poly_no].len;i++) { + transform(sp->polyomino[poly_no].point[i], + sp->polyomino[poly_no].point[point_no], + sp->polyomino[poly_no].transform_list[transform_index], + attach_point, &target_point); + if ( ! ((target_point.x>=0) && (target_point.x<sp->width) + && (target_point.y>=0) && (target_point.y<sp->height) + && (ARRAY_P(target_point)<0))) { + attachable = 0; + break; + } + } + if (attachable) { + score++; + if (score>=min_score_so_far) + return score; + } + } + } + + return score; +} + +static void find_blank(polyominoesstruct *sp, point_type *point) +{ + int score, worst_score; + int x, y; + int blank_mark; + + blank_mark = find_smallest_blank_component(sp); + + worst_score = 1000000; + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) if (ARRAY(x,y)==blank_mark) { + score = 100*score_point(sp,x,y,worst_score); + if (score>0) { + if (sp->left_right) score += 10*x; + else score += 10*(sp->width-1-x); + if (sp->top_bottom) score += y; + else score += (sp->height-1-y); + } + if (score<worst_score) { + point->x = x; + point->y = y; + worst_score = score; + } + } + + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) + if (ARRAY(x,y)<0) ARRAY(x,y) = -1; +} + +/* Detaches the most recently attached polyomino. */ + +static +void detach(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index, point_type *attach_point, int rot180) +{ + int i; + point_type target_point = { 0, 0 }; + + if (sp->nr_attached == 0) return; + sp->nr_attached--; + *poly_no = sp->attach_list[sp->nr_attached]; + *point_no = sp->polyomino[*poly_no].point_no; + *transform_index = sp->polyomino[*poly_no].transform_index; + *attach_point = sp->polyomino[*poly_no].attach_point; + for (i=0;i<sp->polyomino[*poly_no].len;i++) { + transform(sp->polyomino[*poly_no].point[i], + sp->polyomino[*poly_no].point[*point_no], + sp->polyomino[*poly_no].transform_list[*transform_index]^(rot180<<1), + *attach_point, &target_point); + ARRAY_P(target_point) = -1; + CHANGED_ARRAY_P(target_point) = 1; + } + + sp->polyomino[*poly_no].attached = 0; +} + +/* Attempts to attach a polyomino at point (x,y) at the + point_no-th point of that polyomino, using the transform + transform_no. Returns 1 if successful. +*/ + +static +int attach(polyominoesstruct *sp, int poly_no, int point_no, int transform_index, point_type attach_point, int rot180, + int *reason_to_not_attach) { + point_type target_point = { 0, 0 }; + int i; + int attachable = 1, worst_reason_not_to_attach = 1000000000; + + if (rot180) { + attach_point.x = sp->width-1-attach_point.x; + attach_point.y = sp->height-1-attach_point.y; + } + + if (sp->polyomino[poly_no].attached) + return 0; + + for (i=0;i<sp->polyomino[poly_no].len;i++) { + transform(sp->polyomino[poly_no].point[i], + sp->polyomino[poly_no].point[point_no], + sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1), + attach_point, &target_point); + if ( ! ((target_point.x>=0) && (target_point.x<sp->width) + && (target_point.y>=0) && (target_point.y<sp->height) + && (ARRAY_P(target_point) == -1))) { + if (sp->identical) { + attachable = 0; + if ((target_point.x>=0) && (target_point.x<sp->width) + && (target_point.y>=0) && (target_point.y<sp->height) + && (ARRAY_P(target_point) >= 0) + && (ARRAY_P(target_point)<worst_reason_not_to_attach)) + worst_reason_not_to_attach = ARRAY_P(target_point); + } + else + return 0; + } + } + + if (sp->identical && !attachable) { + if (worst_reason_not_to_attach < 1000000000) + reason_to_not_attach[worst_reason_not_to_attach] = 1; + return 0; + } + + for (i=0;i<sp->polyomino[poly_no].len;i++) { + transform(sp->polyomino[poly_no].point[i], + sp->polyomino[poly_no].point[point_no], + sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1), + attach_point, &target_point); + ARRAY_P(target_point) = poly_no; + CHANGED_ARRAY_P(target_point) = 1; + } + + sp->attach_list[sp->nr_attached] = poly_no; + sp->nr_attached++; + + sp->polyomino[poly_no].attached = 1; + sp->polyomino[poly_no].point_no = point_no; + sp->polyomino[poly_no].attach_point = attach_point; + sp->polyomino[poly_no].transform_index = transform_index; + + if (!sp->check_ok(sp)) { + detach(sp,&poly_no,&point_no,&transform_index,&attach_point,rot180); + return 0; + } + + return 1; +} + +static +int next_attach_try(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index) +{ + + (*transform_index)++; + if (*transform_index>=sp->polyomino[*poly_no].transform_len) { + *transform_index = 0; + (*point_no)++; + if (*point_no>=sp->polyomino[*poly_no].len) { + *point_no = 0; + next_poly_no(sp,poly_no); + if (*poly_no>=sp->nr_polyominoes) { + *poly_no = first_poly_no(sp); + return 0; + } + } + } + return 1; +} + + +/******************************************************* +Display routines. +*******************************************************/ + +static void +draw_without_bitmaps(ModeInfo * mi, polyominoesstruct *sp) +{ + Display *display = MI_DISPLAY(mi); + Window window = MI_WINDOW(mi); + GC gc = MI_GC(mi); + int x,y,poly_no,nr_lines,nr_rectangles; + + XSetLineAttributes(display,gc,sp->box/10+1,LineSolid,CapRound,JoinRound); + + for (poly_no=-1;poly_no<sp->nr_polyominoes;poly_no++) { + nr_rectangles = 0; + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) + if (CHANGED_ARRAY(x,y) && ARRAY(x,y) == poly_no) { + sp->rectangles[nr_rectangles].x = sp->x_margin + sp->box*x; + sp->rectangles[nr_rectangles].y = sp->y_margin + sp->box*y; + sp->rectangles[nr_rectangles].width = sp->box; + sp->rectangles[nr_rectangles].height = sp->box; + nr_rectangles++; + } + if (poly_no == -1) + XSetForeground(display, gc, MI_BLACK_PIXEL(mi)); + else + XSetForeground(display, gc, sp->polyomino[poly_no].color); + XFillRectangles(display, window, gc, sp->rectangles, nr_rectangles); + } + + XSetForeground(display, gc, MI_BLACK_PIXEL(mi)); + + nr_lines = 0; + for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) { + if (ARRAY(x,y) == -1 && ARRAY(x+1,y) == -1 + && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x+1,y))) { + sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1); + sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y; + sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1); + sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1); + nr_lines++; + } + } + XDrawSegments(display, window, gc, sp->lines, nr_lines); + + nr_lines = 0; + for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) { + if (ARRAY(x,y) == -1 && ARRAY(x,y+1) == -1 + && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x,y+1))) { + sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x; + sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1); + sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1); + sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1); + nr_lines++; + } + } + XDrawSegments(display, window, gc, sp->lines, nr_lines); + + XSetForeground(display, gc, MI_WHITE_PIXEL(mi)); + XDrawRectangle(display, window, gc, sp->x_margin, sp->y_margin, sp->box*sp->width, sp->box*sp->height); + + XSetForeground(display, gc, MI_WHITE_PIXEL(mi)); + + nr_lines = 0; + for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) { + if (ARRAY(x+1,y) != ARRAY(x,y)) { + sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1); + sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y; + sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1); + sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1); + nr_lines++; + } + } + XDrawSegments(display, window, gc, sp->lines, nr_lines); + + nr_lines = 0; + for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) { + if (ARRAY(x,y+1) != ARRAY(x,y)) { + sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x; + sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1); + sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1); + sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1); + nr_lines++; + } + } + XDrawSegments(display, window, gc, sp->lines, nr_lines); + XSetLineAttributes(display,gc,1,LineSolid,CapRound,JoinRound); +} + +static void create_bitmaps(ModeInfo * mi, polyominoesstruct *sp) +{ + int x,y,n; + char *data; + + for (n=0;n<countof(sp->bitmaps);n++) { + +/* Avoid duplication of identical bitmaps. */ + if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n))) + sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_UP]; + else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n))) + sp->bitmaps[n] = sp->bitmaps[n & ~LEFT_DOWN]; + else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n))) + sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_UP]; + else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n))) + sp->bitmaps[n] = sp->bitmaps[n & ~RIGHT_DOWN]; + + else /* if (bitmap_needed(n)) */ { + data = (char *) malloc(sizeof(char)*(sp->box*ROUND8(sp->box)/8)); + if (data == NULL) { + sp->use_bitmaps = 0; + return; + } + + for (y=0;y<sp->box;y++) for (x=0;x<sp->box;x++) { + if (!sp->use3D) { +#ifdef SMALL_BELLYBUTTON + if (x >= sp->box / 2 && x <= sp->box / 2 + 1 && + y >= sp->box / 2 && y <= sp->box / 2 + 1) + NOTHALFBIT(n,x,y) + else +#endif + HALFBIT(n,x,y) + } else if ((x>=y && x<=sp->box-y-1 && IS_UP(n)) + || (x<=y && x<=sp->box-y-1 && y<sp->box/2 && !IS_LEFT(n)) + || (x>=y && x>=sp->box-y-1 && y<sp->box/2 && !IS_RIGHT(n))) + SETBIT(n,x,y) + else if ((x<=y && x<=sp->box-y-1 && IS_LEFT(n)) + || (x>=y && x<=sp->box-y-1 && x<sp->box/2 && !IS_UP(n)) + || (x<=y && x>=sp->box-y-1 && x<sp->box/2 && !IS_DOWN(n))) + TWOTHIRDSBIT(n,x,y) + else if ((x>=y && x>=sp->box-y-1 && IS_RIGHT(n)) + || (x>=y && x<=sp->box-y-1 && x>=sp->box/2 && !IS_UP(n)) + || (x<=y && x>=sp->box-y-1 && x>=sp->box/2 && !IS_DOWN(n))) + HALFBIT(n,x,y) + else if ((x<=y && x>=sp->box-y-1 && IS_DOWN(n)) + || (x<=y && x<=sp->box-y-1 && y>=sp->box/2 && !IS_LEFT(n)) + || (x>=y && x>=sp->box-y-1 && y>=sp->box/2 && !IS_RIGHT(n))) + THIRDBIT(n,x,y) + } + + if (IS_LEFT(n)) + for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++) + SETBIT(n,x,y) + if (IS_RIGHT(n)) + for (y=0;y<sp->box;y++) for (x=G;x<G+T;x++) + SETBIT(n,sp->box-1-x,y) + if (IS_UP(n)) + for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++) + SETBIT(n,x,y) + if (IS_DOWN(n)) + for (x=0;x<sp->box;x++) for (y=G;y<G+T;y++) + SETBIT(n,x,sp->box-1-y) + if (IS_LEFT(n)) + for (y=0;y<sp->box;y++) for (x=0;x<G;x++) + RESBIT(n,x,y) + if (IS_RIGHT(n)) + for (y=0;y<sp->box;y++) for (x=0;x<G;x++) + RESBIT(n,sp->box-1-x,y) + if (IS_UP(n)) + for (x=0;x<sp->box;x++) for (y=0;y<G;y++) + RESBIT(n,x,y) + if (IS_DOWN(n)) + for (x=0;x<sp->box;x++) for (y=0;y<G;y++) + RESBIT(n,x,sp->box-1-y) + + if (IS_LEFT(n) && IS_UP(n)) + for (x=G;x<=G+R;x++) + for (y=G;y<=R+2*G-x;y++) { + if (x+y>R+2*G-RT) + SETBIT(n,x,y) + else + RESBIT(n,x,y) + } + if (IS_LEFT(n) && IS_DOWN(n)) + for (x=G;x<=G+R;x++) + for (y=G;y<=R+2*G-x;y++) { + if (x+y>R+2*G-RT) + SETBIT(n,x,sp->box-1-y) + else + RESBIT(n,x,sp->box-1-y) + } + if (IS_RIGHT(n) && IS_UP(n)) + for (x=G;x<=G+R;x++) + for (y=G;y<=R+2*G-x;y++) { + if (x+y>R+2*G-RT) + SETBIT(n,sp->box-1-x,y) + else + RESBIT(n,sp->box-1-x,y) + } + if (IS_RIGHT(n) && IS_DOWN(n)) + for (x=G;x<=G+R;x++) + for (y=G;y<=R+2*G-x;y++) { + if (x+y>R+2*G-RT) + SETBIT(n,sp->box-1-x,sp->box-1-y) + else + RESBIT(n,sp->box-1-x,sp->box-1-y) + } + + if (!IS_LEFT(n) && !IS_UP(n) && IS_LEFT_UP(n)) { + for (x=0;x<G;x++) for(y=0;y<G;y++) + RESBIT(n,x,y) + for (x=G;x<G+T;x++) for(y=0;y<G;y++) + SETBIT(n,x,y) + for (x=0;x<G+T;x++) for(y=G;y<G+T;y++) + SETBIT(n,x,y) + } + if (!IS_LEFT(n) && !IS_DOWN(n) && IS_LEFT_DOWN(n)) { + for (x=0;x<G;x++) for(y=0;y<G;y++) + RESBIT(n,x,sp->box-1-y) + for (x=G;x<G+T;x++) for(y=0;y<G;y++) + SETBIT(n,x,sp->box-1-y) + for (x=0;x<G+T;x++) for(y=G;y<G+T;y++) + SETBIT(n,x,sp->box-1-y) + } + if (!IS_RIGHT(n) && !IS_UP(n) && IS_RIGHT_UP(n)) { + for (x=0;x<G;x++) for(y=0;y<G;y++) + RESBIT(n,sp->box-1-x,y) + for (x=G;x<G+T;x++) for(y=0;y<G;y++) + SETBIT(n,sp->box-1-x,y) + for (x=0;x<G+T;x++) for(y=G;y<G+T;y++) + SETBIT(n,sp->box-1-x,y) + } + if (!IS_RIGHT(n) && !IS_DOWN(n) && IS_RIGHT_DOWN(n)) { + for (x=0;x<G;x++) for(y=0;y<G;y++) + RESBIT(n,sp->box-1-x,sp->box-1-y) + for (x=G;x<G+T;x++) for(y=0;y<G;y++) + SETBIT(n,sp->box-1-x,sp->box-1-y) + for (x=0;x<G+T;x++) for(y=G;y<G+T;y++) + SETBIT(n,sp->box-1-x,sp->box-1-y) + } + +#ifdef LARGE_BELLYBUTTON + if (!sp->use3D) { + if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n)) + for (x=0;x<G+T;x++) for(y=0;y<G+T;y++) + SETBIT(n,x,y) + if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n)) + for (x=0;x<G+T;x++) for(y=sp->box-G-T;y<sp->box;y++) + SETBIT(n,x,y) + if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n)) + for (x=sp->box-G-T;x<sp->box;x++) for(y=0;y<G+T;y++) + SETBIT(n,x,y) + if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n)) + for (x=sp->box-G-T;x<sp->box;x++) for(y=sp->box-G-T;y<sp->box;y++) + SETBIT(n,x,y) + } else +#else + if (sp->use3D) +#endif + { + if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n)) + for (x=0;x<sp->box/2-RR;x++) for(y=0;y<sp->box/2-RR;y++) + THREEQUARTERSBIT(n,x,y) + if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n)) + for (x=0;x<sp->box/2-RR;x++) for(y=sp->box/2+RR;y<sp->box;y++) + THREEQUARTERSBIT(n,x,y) + if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n)) + for (x=sp->box/2+RR;x<sp->box;x++) for(y=0;y<sp->box/2-RR;y++) + THREEQUARTERSBIT(n,x,y) + if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n)) + for (x=sp->box/2+RR;x<sp->box;x++) for(y=sp->box/2+RR;y<sp->box;y++) + THREEQUARTERSBIT(n,x,y) + } + + sp->bitmaps[n] = XCreateImage(MI_DISPLAY(mi), MI_VISUAL(mi), 1, XYBitmap, + 0, data, sp->box, sp->box, 8, 0); + if (sp->bitmaps[n] == None) { + free(data); + sp->use_bitmaps = 0; + return; + } + sp->bitmaps[n]->byte_order = MSBFirst; + sp->bitmaps[n]->bitmap_unit = 8; + sp->bitmaps[n]->bitmap_bit_order = LSBFirst; + } + } + + sp->use_bitmaps = 1; +} + +static void draw_with_bitmaps(ModeInfo * mi, polyominoesstruct *sp) +{ + Display *display = MI_DISPLAY(mi); + Window window = MI_WINDOW(mi); + GC gc = MI_GC(mi); + int x,y,t,bitmap_index; + + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) { + if (ARRAY(x,y) == -1) { + if (CHANGED_ARRAY(x,y)) { + XSetForeground(display, gc, MI_BLACK_PIXEL(mi)); + XFillRectangle(display,window,gc, + sp->x_margin + sp->box*x, + sp->y_margin + sp->box*y, + sp->box,sp->box); + } + } + else { + XSetForeground(display, gc, sp->polyomino[ARRAY(x,y)].color); + bitmap_index = 0; + if (ARR(x,y) != ARR(x-1,y)) bitmap_index |= LEFT; + if (ARR(x,y) != ARR(x+1,y)) bitmap_index |= RIGHT; + if (ARR(x,y) != ARR(x,y-1)) bitmap_index |= UP; + if (ARR(x,y) != ARR(x,y+1)) bitmap_index |= DOWN; + if (ARR(x,y) != ARR(x-1,y-1)) bitmap_index |= LEFT_UP; + if (ARR(x,y) != ARR(x-1,y+1)) bitmap_index |= LEFT_DOWN; + if (ARR(x,y) != ARR(x+1,y-1)) bitmap_index |= RIGHT_UP; + if (ARR(x,y) != ARR(x+1,y+1)) bitmap_index |= RIGHT_DOWN; + (void) XPutImage(display,window,gc, + sp->bitmaps[bitmap_index], + 0,0, + sp->x_margin + sp->box*x, + sp->y_margin + sp->box*y, + sp->box,sp->box); + } + } + + XSetForeground(display, gc, sp->border_color); + for (t=G;t<G+T;t++) + XDrawRectangle(display,window,gc, + sp->x_margin-t-1,sp->y_margin-t-1, + sp->box*sp->width+1+2*t, sp->box*sp->height+1+2*t); +} + + +/*************************************************** +Routines to initialise and close down polyominoes. +***************************************************/ + +static void free_bitmaps(polyominoesstruct *sp) +{ + int n; + + for (n=0;n<countof(sp->bitmaps);n++) +/* Don't bother to free duplicates */ + if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n))) + sp->bitmaps[n] = None; + else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n))) + sp->bitmaps[n] = None; + else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n))) + sp->bitmaps[n] = None; + else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n))) + sp->bitmaps[n] = None; + + else if (sp->bitmaps[n] != None) { + XDestroyImage(sp->bitmaps[n]); + sp->bitmaps[n] = None; + } +} + +#define deallocate(p,t) if ((p)!=NULL) {free(p); p=(t*)NULL;} + +ENTRYPOINT void free_polyominoes(ModeInfo * mi) +{ + polyominoesstruct *sp = &polyominoeses[MI_SCREEN(mi)]; + int n; + + for (n=0;n<sp->nr_polyominoes;n++) { + deallocate(sp->polyomino[n].point, point_type); + } + + deallocate(sp->polyomino, polyomino_type); + deallocate(sp->attach_list, int); + deallocate(sp->rectangles, XRectangle); + deallocate(sp->lines, XSegment); + deallocate(sp->reason_to_not_attach, int); + deallocate(sp->array, int); + deallocate(sp->changed_array, int); + + free_bitmaps(sp); +} + +#define set_allocate(p,type,size) p = (type *) malloc(size); \ + if ((p)==NULL) {free_polyominoes(mi);return 0;} + +#define copy_polyomino(dst,src,new_rand) \ + (dst).len=(src).len; \ + (dst).max_white = (src).max_white; \ + set_allocate((dst).point,point_type,sizeof(point_type)*(src).len); \ + (dst).len = (src).len; \ + if (new_rand) \ + random_permutation((src).len,perm_point); \ + for (i=0;i<(src).len;i++) \ + (dst).point[i] = (src).point[perm_point[i]]; \ + (dst).transform_len = (src).transform_len; \ + if (new_rand) \ + random_permutation((src).transform_len,perm_transform); \ + for (i=0;i<(src).transform_len;i++) \ + (dst).transform_list[i] = (src).transform_list[perm_transform[i]]; \ + (dst).attached = 0 + + +/*************************************************** +Puzzle specific initialization routines. +***************************************************/ + +static +int check_pentomino_puzzle(polyominoesstruct *sp) +{ + return check_all_regions_multiple_of(sp, 5) && whites_ok(sp); +} + +static +int check_hexomino_puzzle(polyominoesstruct *sp) +{ + return check_all_regions_multiple_of(sp, 6) && whites_ok(sp); +} + +static +int check_tetr_pentomino_puzzle(polyominoesstruct *sp) +{ + return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp); +} + +static +int check_pent_hexomino_puzzle(polyominoesstruct *sp) +{ + return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp); +} + +static +int check_heptomino_puzzle(polyominoesstruct *sp) +{ + return check_all_regions_multiple_of(sp, 7) && whites_ok(sp); +} + +static +int check_octomino_puzzle(polyominoesstruct *sp) +{ + return check_all_regions_multiple_of(sp, 8) && whites_ok(sp); +} + +static +int check_dekomino_puzzle(polyominoesstruct *sp) +{ + return check_all_regions_multiple_of(sp, 10) && whites_ok(sp); +} + +static +int check_elevenomino_puzzle(polyominoesstruct *sp) +{ + return check_all_regions_multiple_of(sp, 11) && whites_ok(sp); +} + +static struct {int len; point_type point[4]; + int transform_len, transform_list[8], max_white;} tetromino[5] = +{ +/* +xxxx +*/ + {4, {{0,0}, {1,0}, {2,0}, {3,0}}, + 2, {0, 1, -1, -1, -1, -1, -1, -1}, 2}, +/* +xxx + x +*/ + {4, {{0,0}, {1,0}, {2,0}, {2,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 2}, +/* +xxx + x +*/ + {4, {{0,0}, {1,0}, {1,1}, {2,0}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}, +/* +xx + xx +*/ + {4, {{0,0}, {1,0}, {1,1}, {2,1}}, + 4, {0, 1, 4, 5, -1, -1, -1, -1}, 2}, +/* +xx +xx +*/ + {4, {{0,0}, {0,1}, {1,0}, {1,1}}, + 1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}}; + + +static struct pentomino_struct {int len; point_type point[5]; + int transform_len, transform_list[8], max_white;} + pentomino[12] = +{ +/* +xxxxx +*/ + {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}}, + 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3}, +/* +xxxx + x +*/ + {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxxx + x +*/ + {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* + x +xxx + x +*/ + {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}, +/* +xxx + xx +*/ + {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxx + xx +*/ + {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxx + x + x +*/ + {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}, +/* + x +xxx + x +*/ + {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxx +x x +*/ + {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}, +/* + x +xxx +x +*/ + {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}}, + 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}, +/* + x +xxx + x +*/ + {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}}, + 1, {0, -1, -1, -1, -1, -1, -1, -1}, 4}, +/* +xx + xx + x +*/ + {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}}; + + +static struct hexomino_struct {int len; point_type point[6]; + int transform_len, transform_list[8], max_white;} + hexomino[35] = +{ +/* +xxxxxx +*/ + {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}}, + 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3}, +/* +xxxxx + x +*/ + {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxxxx + x +*/ + {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4}, +/* +xxxxx + x +*/ + {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}, +/* + x +xxxx + x +*/ + {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4}, +/* +xxxx + xx +*/ + {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxxx + xx +*/ + {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxxx + x + x +*/ + {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* + x +xxxx + x +*/ + {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxxx + x x +*/ + {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4}, +/* + x +xxxx + x +*/ + {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4}, +/* +xxxx +x x +*/ + {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}, +/* + x +xxxx +x +*/ + {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}}, + 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}, +/* + x +xxxx + x +*/ + {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4}, +/* +xxxx + xx +*/ + {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}, +/* +xxxx + x + x +*/ + {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* + x +xxxx + x +*/ + {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}}, + 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}, +/* + xx +xxx + x +*/ + {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* + xx +xxx + x +*/ + {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* + x +xxx +x x +*/ + {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4}, +/* +xxx + xxx +*/ + {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}}, + 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}, +/* +xxx + xx + x +*/ + {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxx + xxx +*/ + {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}}, + 4, {0, 1, 4, 5, -1, -1, -1, -1}, 4}, +/* +xxx + xx + x +*/ + {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4}, +/* + x +xxx + xx +*/ + {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4}, +/* +xxx +x xx +*/ + {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxx + xx + x +*/ + {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4}, +/* + x +xxx + xx +*/ + {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 4}, +/* +xxx +xxx +*/ + {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}}, + 2, {0, 1, -1, -1, -1, -1, -1, -1}, 3}, +/* +xxx + x + xx +*/ + {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xxx + x + xx +*/ + {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* + x +xxx +x x +*/ + {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}}, + 4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}, +/* + xx +xxx +x +*/ + {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* + xx +xxx +x +*/ + {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}, +/* +xx + xx + xx +*/ + {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}}, + 4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}}; + +static struct pentomino_struct one_sided_pentomino[60]; + +static void make_one_sided_pentomino(void) +{ + int i,j,t,u; + + j=0; + for (i=0;i<countof(pentomino);i++) { + one_sided_pentomino[j] = pentomino[i]; + for (t=0;t<8;t++) + if (one_sided_pentomino[j].transform_list[t]>=4) { + one_sided_pentomino[j].transform_len = t; + j++; + one_sided_pentomino[j] = pentomino[i]; + for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u]; + one_sided_pentomino[j].transform_len -= t; + break; + } + j++; + } +} + +static struct hexomino_struct one_sided_hexomino[60]; + +static void make_one_sided_hexomino(void) +{ + int i,j,t,u; + + j=0; + for (i=0;i<countof(hexomino);i++) { + one_sided_hexomino[j] = hexomino[i]; + for (t=0;t<8;t++) + if (one_sided_hexomino[j].transform_list[t]>=4) { + one_sided_hexomino[j].transform_len = t; + j++; + one_sided_hexomino[j] = hexomino[i]; + for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u]; + one_sided_hexomino[j].transform_len -= t; + break; + } + j++; + } +} + +/* +Find all the ways of placing all twelve pentominoes +into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6. +*/ + +static +int set_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_poly[12], perm_point[5], perm_transform[8], i, p; + + switch (NRAND(4)) { + case 0: + sp->width = 20; + sp->height = 3; + break; + case 1: + sp->width = 15; + sp->height = 4; + break; + case 2: + sp->width = 12; + sp->height = 5; + break; + case 3: + sp->width = 10; + sp->height = 6; + break; + } + + sp->nr_polyominoes = 12; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + random_permutation(sp->nr_polyominoes,perm_poly); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1); + } + + sp->check_ok = check_pentomino_puzzle; + + return 1; +} + +/* +Many of the following puzzles are inspired by +http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html +*/ + +/* +Find all the ways of placing all eighteen one-sided pentominoes +into a rectangle. +*/ + +static +int set_one_sided_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_poly[18], perm_point[5], perm_transform[8], i, p; + + make_one_sided_pentomino(); + + switch (NRAND(4)) { + case 0: + sp->width = 30; + sp->height = 3; + break; + case 1: + sp->width = 18; + sp->height = 5; + break; + case 2: + sp->width = 15; + sp->height = 6; + break; + case 3: + sp->width = 10; + sp->height = 9; + break; + } + + sp->nr_polyominoes = 18; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + random_permutation(sp->nr_polyominoes,perm_poly); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1); + } + + sp->check_ok = check_pentomino_puzzle; + + return 1; +} + +/* +Find all the ways of placing all sixty one-sided hexominoes +into a rectangle. +*/ + +static +int set_one_sided_hexomino_puzzle(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_poly[60], perm_point[6], perm_transform[8], i, p; + + make_one_sided_hexomino(); + + switch (NRAND(8)) { + case 0: + sp->width = 20; + sp->height = 18; + break; + case 1: + sp->width = 24; + sp->height = 15; + break; + case 2: + sp->width = 30; + sp->height = 12; + break; + case 3: + sp->width = 36; + sp->height = 10; + break; + case 4: + sp->width = 40; + sp->height = 9; + break; + case 5: + sp->width = 45; + sp->height = 8; + break; + case 6: + sp->width = 60; + sp->height = 6; + break; + case 7: + sp->width = 72; + sp->height = 5; + break; + } + + sp->nr_polyominoes = 60; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + random_permutation(sp->nr_polyominoes,perm_poly); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1); + } + + sp->check_ok = check_hexomino_puzzle; + + return 1; +} + +/* +Find all the ways of placing all five tetrominoes and all twelve +pentominoes into a rectangle. +*/ + +static +int set_tetr_pentomino_puzzle(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_poly[17], perm_point[5], perm_transform[8], i, p; + + switch (NRAND(3)) { + case 0: + sp->width = 20; + sp->height = 4; + break; + case 1: + sp->width = 16; + sp->height = 5; + break; + case 2: + sp->width = 10; + sp->height = 8; + break; + } + + sp->nr_polyominoes = 17; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + random_permutation(sp->nr_polyominoes,perm_poly); + for (p=0;p<countof(tetromino);p++) { + copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1); + } + for (p=0;p<countof(pentomino);p++) { + copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1); + } + + sp->check_ok = check_tetr_pentomino_puzzle; + + return 1; +} +/* +Find all the ways of placing all twelve pentominoes and all thirty five +hexominoes into a rectangle whose size is 18x15. +*/ + +static +int set_pent_hexomino_puzzle(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_poly[47], perm_point[6], perm_transform[8], i, p; + + switch (NRAND(5)) { + case 0: + sp->width = 54; + sp->height = 5; + break; + case 1: + sp->width = 45; + sp->height = 6; + break; + case 2: + sp->width = 30; + sp->height = 9; + break; + case 3: + sp->width = 27; + sp->height = 10; + break; + case 4: + sp->width = 18; + sp->height = 15; + break; + } + + sp->nr_polyominoes = 47; + set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type)); + random_permutation(47,perm_poly); + for (p=0;p<countof(pentomino);p++) { + copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1); + } + for (p=0;p<countof(hexomino);p++) { + copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1); + } + + sp->check_ok = check_pent_hexomino_puzzle; + + return 1; +} + +/* +Other puzzles: + +Science News September 20, 1986 Vol 130, No 12 +Science News November 14, 1987 Vol 132, Pg 310 +*/ + +/* + + * +**** fills a 10x5 rectangle + +*/ + +static struct {int len; point_type point[5]; + int transform_len, transform_list[8], max_white;} pentomino1 = + {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 3}; + +static +int set_pentomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[5], perm_transform[8], i, p; + + sp->width = 10; + sp->height =5; + + sp->nr_polyominoes = 10; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],pentomino1,1); + } + + sp->check_ok = check_pentomino_puzzle; + + return 1; +} + +/* + + * +***** fills a 24x23 rectangle + +*/ + +static struct {int len; point_type point[6]; + int transform_len, transform_list[8], max_white;} hexomino1 = + {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4}; + +static +int set_hexomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[6], perm_transform[8], i, p; + + sp->width = 24; + sp->height =23; + + sp->nr_polyominoes = 92; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],hexomino1,1); + } + + sp->check_ok = check_hexomino_puzzle; + + return 1; +} + +/* + + ** +***** fills a 21x26 rectangle + +(All solutions have 180 degree rotational symmetry) + +*/ + +static struct {int len; point_type point[7]; + int transform_len, transform_list[8], max_white;} heptomino1 = + {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 4}; + +static +int set_heptomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[7], perm_transform[8], i, p; + + sp->rot180 = 1; + + sp->width = 26; + sp->height =21; + + sp->nr_polyominoes = 78; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p+=2) { + copy_polyomino(sp->polyomino[p],heptomino1,1); + copy_polyomino(sp->polyomino[p+1],heptomino1,0); + } + + sp->check_ok = check_heptomino_puzzle; + + return 1; +} + +/* The following puzzles from +Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition +by Solomon W. Golomb Princeton University Press 1994 +*/ + +/* + + ** +***** fills a 28x19 rectangle + +*/ +static +int set_heptomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[7], perm_transform[8], i, p; + + sp->width = 28; + sp->height =19; + + sp->nr_polyominoes = 76; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],heptomino1,1); + } + + sp->check_ok = check_heptomino_puzzle; + + return 1; +} + +/* + +*** +**** fills a 25x22 rectangle +**** + +*/ + +static struct {int len; point_type point[11]; + int transform_len, transform_list[8], max_white;} elevenomino1 = + {11, {{0,0}, {1,0}, {2,0}, + {0,1}, {1,1}, {2,1}, {3,1}, + {0,2}, {1,2}, {2,2}, {3,2}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 6}; + +static +int set_elevenomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[11], perm_transform[8], i, p; + + sp->rot180 = 1; + + sp->width = 25; + sp->height =22; + + sp->nr_polyominoes = 50; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p+=2) { + copy_polyomino(sp->polyomino[p],elevenomino1,1); + copy_polyomino(sp->polyomino[p+1],elevenomino1,0); + } + + sp->check_ok = check_elevenomino_puzzle; + + return 1; +} + +/* + + * + * +**** fills 32 x 30 rectangle +**** + +*/ + +static struct {int len; point_type point[10]; + int transform_len, transform_list[8], max_white;} dekomino1 = + {10, { {1,-1}, + {1,0}, + {0,1}, {1,1}, {2,1}, {3,1}, + {0,2}, {1,2}, {2,2}, {3,2}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5}; + +static +int set_dekomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[10], perm_transform[8], i, p; + + sp->width = 32; + sp->height =30; + + sp->nr_polyominoes = 96; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],dekomino1,1); + } + + sp->check_ok = check_dekomino_puzzle; + + return 1; +} + +/* + + * +*** fills 96 x 26 rectangle +**** + +*/ + +static struct {int len; point_type point[10]; + int transform_len, transform_list[8], max_white;} octomino1 = + {8, { {1,0}, + {0,1}, {1,1}, {2,1}, + {0,2}, {1,2}, {2,2}, {3,2}}, + 8, {0, 1, 2, 3, 4, 5, 6, 7}, 5}; + +static +int set_octomino_puzzle1(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[8], perm_transform[8], i, p; + + sp->width = 96; + sp->height =26; + + sp->nr_polyominoes = 312; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],octomino1,1); + } + + sp->check_ok = check_octomino_puzzle; + + return 1; +} + +/* + + * fills 15 x 15 rectangle +**** + +*/ + +static +int set_pentomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[5], perm_transform[8], i, p; + + sp->width = 15; + sp->height =15; + + sp->nr_polyominoes = 45; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],pentomino1,1); + } + + sp->check_ok = check_pentomino_puzzle; + + return 1; +} + +/* + +*** +**** fills a 47x33 rectangle +**** + +*/ + +static +int set_elevenomino_puzzle2(ModeInfo * mi, polyominoesstruct *sp) +{ + int perm_point[11], perm_transform[8], i, p; + + sp->width = 47; + sp->height =33; + + sp->nr_polyominoes = 141; + set_allocate(sp->polyomino,polyomino_type, + sp->nr_polyominoes*sizeof(polyomino_type)); + for (p=0;p<sp->nr_polyominoes;p++) { + copy_polyomino(sp->polyomino[p],elevenomino1,1); + } + + sp->check_ok = check_elevenomino_puzzle; + + return 1; +} + +/************************************************** +The main functions. +**************************************************/ + +#define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes(mi); return;} + +ENTRYPOINT void +init_polyominoes (ModeInfo * mi) +{ + polyominoesstruct *sp; + int i,x,y, start; + int box1, box2; + int *perm; + + MI_INIT (mi, polyominoeses); + sp = &polyominoeses[MI_SCREEN(mi)]; + + sp->rot180 = 0; + sp->counter = 0; + + if (MI_IS_FULLRANDOM(mi)) { + sp->identical = (Bool) (LRAND() & 1); + sp->use3D = (Bool) (NRAND(4)); + } else { + sp->identical = identical; + sp->use3D = !plain; + } + if (sp->identical) { + switch (NRAND(9)) { + case 0: + if (!set_pentomino_puzzle1(mi, sp)) + return; + break; + case 1: + if (!set_hexomino_puzzle1(mi, sp)) + return; + break; + case 2: + if (!set_heptomino_puzzle1(mi, sp)) + return; + break; + case 3: + if (!set_heptomino_puzzle2(mi, sp)) + return; + break; + case 4: + if (!set_elevenomino_puzzle1(mi, sp)) + return; + break; + case 5: + if (!set_dekomino_puzzle1(mi, sp)) + return; + break; + case 6: + if (!set_octomino_puzzle1(mi, sp)) + return; + break; + case 7: + if (!set_pentomino_puzzle2(mi, sp)) + return; + break; + case 8: + if (!set_elevenomino_puzzle2(mi, sp)) + return; + break; + } + } else { + switch (NRAND(5)) { + case 0: + if (!set_pentomino_puzzle(mi, sp)) + return; + break; + case 1: + if (!set_one_sided_pentomino_puzzle(mi, sp)) + return; + break; + case 2: + if (!set_one_sided_hexomino_puzzle(mi, sp)) + return; + break; + case 3: + if (!set_pent_hexomino_puzzle(mi, sp)) + return; + break; + case 4: + if (!set_tetr_pentomino_puzzle(mi, sp)) + return; + break; + } + } + + if (MI_HEIGHT(mi) > MI_WIDTH(mi)) { /* rotate if portrait */ + int swap = sp->height; + sp->height = sp->width; + sp->width = swap; + } + + allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int)); + sp->nr_attached = 0; + + if (sp->identical) { + allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int)); + } + + allocate(sp->array,int,sp->width*sp->height*sizeof(int)); + allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int)); + for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1; + + sp->left_right = NRAND(2); + sp->top_bottom = NRAND(2); + + box1 = MI_WIDTH(mi)/(sp->width+2); + box2 = MI_HEIGHT(mi)/(sp->height+2); + if (box1<box2) + sp->box = box1; + else + sp->box = box2; + + if (MI_WIDTH(mi) > MI_HEIGHT(mi) * 5 || /* weird window aspect ratio */ + MI_HEIGHT(mi) > MI_WIDTH(mi)* 5) { + sp->box *= (MI_WIDTH(mi) > MI_HEIGHT(mi) + ? MI_WIDTH(mi) / (double) MI_HEIGHT(mi) + : MI_HEIGHT(mi) / (double) MI_WIDTH(mi)); + } + + if (sp->box >= 12) { + sp->box = (sp->box/12)*12; + create_bitmaps(mi,sp); + if (!sp->use_bitmaps) + free_bitmaps(sp); + } + else + sp->use_bitmaps = 0; + + if (!sp->use_bitmaps) { + allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle)); + allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment)); + } + + allocate(perm,int,sp->nr_polyominoes*sizeof(int)); + random_permutation(sp->nr_polyominoes, perm); + sp->mono = MI_NPIXELS(mi) < 12; + start = NRAND(MI_NPIXELS(mi)); + for (i=0;i<sp->nr_polyominoes;i++) + if (!sp->mono) { + sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi)); + if (sp->rot180) { + sp->polyomino[i+1].color = sp->polyomino[i].color; + i++; + } + } + else + if(sp->use_bitmaps) + sp->polyomino[i].color = MI_WHITE_PIXEL(mi); + else + sp->polyomino[i].color = MI_BLACK_PIXEL(mi); + free(perm); + + if (sp->use_bitmaps) { + if (sp->mono) + sp->border_color = MI_WHITE_PIXEL(mi); + else + sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi))); + } + + sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2; + sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2; + + sp->wait = 0; + + /* Clear the background. */ + MI_CLEARWINDOW(mi); + +} + +ENTRYPOINT void +draw_polyominoes (ModeInfo * mi) +{ + polyominoesstruct *sp; + int poly_no,point_no,transform_index,done,another_attachment_try; + point_type attach_point; + int i,detach_until; + + if (polyominoeses == NULL) + return; + sp = &polyominoeses[MI_SCREEN(mi)]; + + if (MI_CYCLES(mi) != 0) { + if (++sp->counter > MI_CYCLES(mi)) { + init_polyominoes(mi); + return; + } + } + + if (sp->box == 0) { + init_polyominoes(mi); + return; + } + + MI_IS_DRAWN(mi) = True; + sp->wait--; + if (sp->wait>0) return; + + memset(sp->changed_array,0,sp->width*sp->height*sizeof(int)); + + poly_no = first_poly_no(sp); + point_no = 0; + transform_index = 0; + done = 0; + another_attachment_try = 1; + find_blank(sp,&attach_point); + if (sp->identical && sp->nr_attached < sp->nr_polyominoes) + memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int)); + while(!done) { + if (sp->nr_attached < sp->nr_polyominoes) { + while (!done && another_attachment_try) { + done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0)); + if (done && sp->rot180) { + poly_no = first_poly_no(sp); + done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0)); + if (!done) + detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0); + } + if (!done) + another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index); + } + } + + if (sp->identical) { + if (!done) { + if (sp->nr_attached == 0) + done = 1; + else { + detach_until=sp->nr_attached-1; + if (sp->nr_attached < sp->nr_polyominoes) + while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0) + detach_until--; + while (sp->nr_attached>detach_until) { + if (sp->rot180) + detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1); + detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0); + if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes) + for (i=0;i<sp->nr_polyominoes;i++) + REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i); + } + another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index); + } + } + } + else { + if (!done) { + if (sp->nr_attached == 0) + done = 1; + else { + if (sp->rot180) + detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1); + detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0); + } + another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index); + } + } + } + + if (sp->use_bitmaps) + draw_with_bitmaps(mi,sp); + else + draw_without_bitmaps(mi,sp); + + if (sp->nr_attached == sp->nr_polyominoes) + sp->wait = 100; + else + sp->wait = 0; +} + +#ifndef STANDALONE +ENTRYPOINT void +refresh_polyominoes (ModeInfo * mi) +{ + MI_CLEARWINDOW(mi); +} +#endif + +XSCREENSAVER_MODULE ("Polyominoes", polyominoes) + +#endif /* MODE_polyominoes */ |