"Fossies" - the Fresh Open Source Software Archive

Member "xlockmore-5.59/modes/polyominoes.c" (8 Sep 2019, 62262 Bytes) of package /linux/misc/xlockmore-5.59.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "polyominoes.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 5.58_vs_5.59.

    1 /* -*- Mode: C; tab-width: 4 -*- */
    2 /* polyominoes --- Shows attempts to place polyominoes into a rectangle */
    3 
    4 #if 0
    5 static const char sccsid[] = "@(#)polyominoes.c 5.01 2000/12/18 xlockmore";
    6 
    7 #endif
    8 
    9 /*
   10  * Copyright (c) 2000 by Stephen Montgomery-Smith <stephen@math.missouri.edu>
   11  *
   12  * Permission to use, copy, modify, and distribute this software and its
   13  * documentation for any purpose and without fee is hereby granted,
   14  * provided that the above copyright notice appear in all copies and that
   15  * both that copyright notice and this permission notice appear in
   16  * supporting documentation.
   17  *
   18  * This file is provided AS IS with no warranties of any kind.  The author
   19  * shall have no liability with respect to the infringement of copyrights,
   20  * trade secrets or any patents by this file or any part thereof.  In no
   21  * event will the author be liable for any lost revenue or profits or
   22  * other special, indirect and consequential damages.
   23  *
   24  * Revision History:
   25  * 07-Jan-2001: Made improvement to the search algorithm for the puzzles
   26  *              involving identical polyominoes (via the variable
   27  *              reason_to_not_attach).  By Stephen Montgomery-Smith.
   28  * 20-Dec-2000: Added more puzzles at David Bagley's request.
   29  * 27-Nov-2000: Adapted from euler2d.c Copyright (c) 2000 by Stephen
   30  *              Montgomery-Smith
   31  * 05-Jun-2000: Adapted from flow.c Copyright (c) 1996 by Tim Auckland
   32  * 18-Jul-1996: Adapted from swarm.c Copyright (c) 1991 by Patrick J. Naughton.
   33  * 31-Aug-1990: Adapted from xswarm by Jeff Butterworth. (butterwo@ncsc.org)
   34  */
   35 
   36 #ifdef STANDALONE
   37 #define MODE_polyominoes
   38 #define DEFAULTS "*delay: 1000 \n" \
   39     "*count: 1024 \n" \
   40     "*cycles: 3000 \n" \
   41     "*ncolors: 200 \n" \
   42 
   43 # define reshape_polyominoes 0
   44 # define polyominoes_handle_event 0
   45 #define SMOOTH_COLORS
   46 #include "xlockmore.h"      /* in xscreensaver distribution */
   47 #else /* STANDALONE */
   48 #include "xlock.h"      /* in xlockmore distribution */
   49 #endif /* STANDALONE */
   50 
   51 #ifdef MODE_polyominoes
   52 #define DEF_IDENTICAL "False"
   53 #define DEF_PLAIN "False"
   54 
   55 static Bool identical;
   56 static Bool plain;
   57 
   58 static XrmOptionDescRec opts[] =
   59 {
   60   {(char *) "-identical", (char *) ".polyominoes.identical", XrmoptionNoArg, (caddr_t) "on"},
   61   {(char *) "+identical", (char *) ".polyominoes.identical", XrmoptionNoArg, (caddr_t) "off"},
   62   {(char *) "-plain", (char *) ".polyominoes.plain", XrmoptionNoArg, (caddr_t) "on"},
   63   {(char *) "+plain", (char *) ".polyominoes.plain", XrmoptionNoArg, (caddr_t) "off"}
   64 };
   65 static argtype vars[] =
   66 {
   67   {(void *) &identical, (char *) "identical", (char *) "Identical", (char *) DEF_IDENTICAL, t_Bool},
   68   {(void *) & plain, (char *) "plain", (char *) "Plain", (char *) DEF_PLAIN, t_Bool}
   69 };
   70 static OptionStruct desc[] =
   71 {
   72   {(char *) "-/+identical", (char *) "turn on/off puzzles where the polyomino pieces are identical"},
   73   {(char *) "-/+plain", (char *) "turn on/off plain pieces"}
   74 };
   75 
   76 ENTRYPOINT ModeSpecOpt polyominoes_opts =
   77 {sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};
   78 
   79 #ifdef USE_MODULES
   80 ModStruct   polyominoes_description = {
   81   "polyominoes", "init_polyominoes", "draw_polyominoes", "release_polyominoes",
   82   "refresh_polyominoes", "init_polyominoes", "free_polyominoes", &polyominoes_opts,
   83   6000, 1, 8192, 1, 64, 1.0, "",
   84   "Shows attempts to place polyominoes into a rectangle", 0, NULL
   85 };
   86 
   87 #endif
   88 
   89 /* Each polyomino is described by several quantities:
   90    len:             the number of squares in the polyomino;
   91    point:           the list of points;
   92    tranform_len:    the number of items in transform_list;
   93    transform_list:  a list of transformations that need to be done in order
   94                     to get all rotations and reflections (see the function
   95                     transform below);
   96    max_white:       the maximum number of white squares covered if polyomino
   97                     is placed on a chess board;
   98    color:           it's display color;
   99    attached:        whether it is currently attached to the rectangle;
  100    attach_point:    point on rectangle where attached;
  101    point_no:        the number of the point where it is attached;
  102    transform_index: which element of transform_list is currently being used.
  103 */
  104 
  105 typedef struct {int x,y;} point_type;
  106 
  107 typedef struct {int len; point_type *point;
  108                 int transform_len, transform_list[8], max_white;
  109         unsigned long color;
  110         int attached;
  111         point_type attach_point;
  112         int point_no, transform_index;} polyomino_type;
  113 
  114 
  115 typedef struct _polyominoesstruct{
  116   int wait;
  117 
  118   int width, height;
  119   unsigned border_color;
  120   int mono;
  121 
  122   polyomino_type *polyomino;
  123   int nr_polyominoes;
  124   Bool identical, use3D;
  125   int *attach_list;
  126   int nr_attached;
  127 
  128 /* The array that tells where the polyominoes are attached. */
  129   int *array, *changed_array;
  130 
  131 /* These specify the dimensions of how things appear on the screen. */
  132   int box, x_margin, y_margin;
  133 
  134 /* These booleans decide in which way to try to attach the polyominoes. */
  135   int left_right, top_bottom;
  136 
  137 /* Bitmaps for display purposes. */
  138   int use_bitmaps;
  139   XImage *bitmaps[256];
  140 
  141 /* Structures used for display purposes if there is not enough memory
  142    to allocate bitmaps (or if the screen is small). */
  143   XSegment *lines;
  144   XRectangle *rectangles;
  145 
  146 /* A procedure that may be used to see if certain configurations
  147    are permissible. */
  148   int (*check_ok)(struct _polyominoesstruct *sp);
  149 
  150 /* Tells program that solutions are invariant under 180 degree
  151    rotation. */
  152   int rot180;
  153 
  154 /* This is a variable used in the case that all the polyominoes are identical
  155    that will further prune the search tree.  Essentially it will be
  156    int reason_to_not_attach[nr_polynominoes][nr_polynominoes];
  157    Let me first explain the effect it is trying to overcome.  Often
  158    in the search process, the computer will first try to fit shapes into
  159    a region (call it A), and then into another region (call it B) that is
  160    essentially disjoint from A.  But it may be that it just is not possible
  161    to fit shapes into region B.  So it fits something into A, and then
  162    tries to fit something into B.  Failing it fits something else into A,
  163    and then tried again to fit something into B.  Thus the program is trying
  164    again and again to fit something into B, when it should have figured out
  165    the first time that it was impossible.
  166 
  167    To overcome this, everytime we try to attach a piece, we collect the reasons
  168    why it cannot be attached (a boolean for each piece that got in the way).
  169    If we see that a piece cannot be attached, we detach the other pieces until
  170    we have detached at least one piece for which the boolean reason_to_not_attach
  171    is set.
  172 */
  173   int *reason_to_not_attach;
  174 
  175   int counter;
  176 } polyominoesstruct;
  177 
  178 #define ARRAY(x,y)         (sp->array[(x)*sp->height+(y)])
  179 #define CHANGED_ARRAY(x,y) (sp->changed_array[(x)*sp->height+(y)])
  180 #define ARRAY_P(p)         (sp->array[(p).x*sp->height+(p).y])
  181 #define CHANGED_ARRAY_P(p) (sp->changed_array[(p).x*sp->height+(p).y])
  182 #define ARR(x,y) (((x)<0||(x)>=sp->width||(y)<0||(y)>=sp->height)?-2:ARRAY(x,y))
  183 
  184 #define REASON_TO_NOT_ATTACH(x,y) (sp->reason_to_not_attach[(x)*sp->nr_polyominoes+(y)])
  185 
  186 #define ROUND8(n) ((((n)+7)/8)*8)
  187 
  188 /* Defines to index the bitmaps.  A set bit indicates that an edge or
  189    corner is required. */
  190 #define LEFT (1<<0)
  191 #define RIGHT (1<<1)
  192 #define UP (1<<2)
  193 #define DOWN (1<<3)
  194 #define LEFT_UP (1<<4)
  195 #define LEFT_DOWN (1<<5)
  196 #define RIGHT_UP (1<<6)
  197 #define RIGHT_DOWN (1<<7)
  198 #define IS_LEFT(n) ((n) & LEFT)
  199 #define IS_RIGHT(n) ((n) & RIGHT)
  200 #define IS_UP(n) ((n) & UP)
  201 #define IS_DOWN(n) ((n) & DOWN)
  202 #define IS_LEFT_UP(n) ((n) & LEFT_UP)
  203 #define IS_LEFT_DOWN(n) ((n) & LEFT_DOWN)
  204 #define IS_RIGHT_UP(n) ((n) & RIGHT_UP)
  205 #define IS_RIGHT_DOWN(n) ((n) & RIGHT_DOWN)
  206 
  207 /* Defines to access the bitmaps. */
  208 #define BITNO(x,y) ((x)+(y)*ROUND8(sp->box))
  209 #define SETBIT(n,x,y) {data[BITNO(x,y)/8] |= 1<<(BITNO(x,y)%8);}
  210 #define RESBIT(n,x,y) {data[BITNO(x,y)/8] &= ~(1<<(BITNO(x,y)%8));}
  211 #define TWOTHIRDSBIT(n,x,y) {if ((x+y-1)%3) SETBIT(n,x,y) else RESBIT(n,x,y)}
  212 #define HALFBIT(n,x,y) {if ((x-y)%2) SETBIT(n,x,y) else RESBIT(n,x,y)}
  213 #define THIRDBIT(n,x,y) {if (!((x-y-1)%3)) SETBIT(n,x,y) else RESBIT(n,x,y)}
  214 #define THREEQUARTERSBIT(n,x,y) \
  215   {if ((y%2)||((x+2+y/2+1)%2)) SETBIT(n,x,y) else RESBIT(n,x,y)}
  216 #define NOTHALFBIT(n,x,y) {if ((x-y)%2) RESBIT(n,x,y) else SETBIT(n,x,y)}
  217 
  218 /* Parameters for bitmaps. */
  219 #define G ((sp->box/45)+1)         /* 1/2 of gap between polyominoes. */
  220 #define T ((sp->box<=12)?1:(G*2))  /* Thickness of walls of polyominoes. */
  221 #define R ((sp->box<=12)?1:(G*6))  /* Amount of rounding. */
  222 #define RT ((sp->box<=12)?1:(G*3)) /* Thickness of wall of rounded parts.
  223                                       Here 3 is an approximation to 2 sqrt(2). */
  224 #define RR 0   /* Roof ridge thickness */
  225 
  226 #if 0
  227 /* A list of those bitmaps we need to create to display any pentomino. */
  228 /* (not used right now because it does not seem to work for hexonimoes.) */
  229 
  230 static int bitmaps_needed[] =
  231 {
  232  LEFT_UP|LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
  233 
  234  LEFT|RIGHT_UP|RIGHT_DOWN,
  235  RIGHT|LEFT_UP|LEFT_DOWN,
  236  UP|LEFT_DOWN|RIGHT_DOWN,
  237  DOWN|LEFT_UP|RIGHT_UP,
  238  LEFT|RIGHT_UP,
  239  RIGHT|LEFT_UP,
  240  UP|LEFT_DOWN,
  241  DOWN|LEFT_UP,
  242  LEFT|RIGHT_DOWN,
  243  RIGHT|LEFT_DOWN,
  244  UP|RIGHT_DOWN,
  245  DOWN|RIGHT_UP,
  246 
  247 /* These needed for hexonimoes*/
  248  LEFT,
  249  RIGHT,
  250  UP,
  251  DOWN,
  252  LEFT_DOWN|RIGHT_UP|RIGHT_DOWN,
  253  LEFT_UP|RIGHT_UP|RIGHT_DOWN,
  254  LEFT_UP|LEFT_DOWN|RIGHT_DOWN,
  255  LEFT_UP|LEFT_DOWN|RIGHT_UP,
  256 
  257  LEFT|UP|RIGHT_DOWN,
  258  LEFT|DOWN|RIGHT_UP,
  259  RIGHT|UP|LEFT_DOWN,
  260  RIGHT|DOWN|LEFT_UP,
  261  LEFT|UP,
  262  LEFT|DOWN,
  263  RIGHT|UP,
  264  RIGHT|DOWN,
  265 
  266  LEFT|RIGHT,
  267  UP|DOWN,
  268 
  269  RIGHT|UP|DOWN,
  270  LEFT|UP|DOWN,
  271  LEFT|RIGHT|DOWN,
  272  LEFT|RIGHT|UP,
  273 
  274  -1
  275 };
  276 
  277 static int bitmap_needed(int n) {
  278   int i;
  279 
  280   for (i=0;bitmaps_needed[i]!=-1;i++)
  281     if (n == bitmaps_needed[i])
  282       return 1;
  283   return 0;
  284 }
  285 
  286 #endif
  287 
  288 /* Some debugging routines.
  289 
  290 static void print_board(polyominoesstruct *sp) {
  291   int x,y;
  292   for (y=0;y<sp->height;y++) {
  293     for (x=0;x<sp->width;x++)
  294       if (ARRAY(x,y) == -1)
  295         (void) fprintf(stderr," ");
  296       else
  297         (void) fprintf(stderr,"%c",'a'+ARRAY(x,y));
  298     (void) fprintf(stderr,"\n");
  299   }
  300   (void) fprintf(stderr,"\n");
  301 }
  302 
  303 static void print_points(point_type *point, int len) {
  304   int i;
  305 
  306   for (i=0;i<len;i++)
  307     (void) fprintf(stderr,"(%d %d) ",point[i].x,point[i].y);
  308 }
  309 
  310 static void print_polyomino(polyomino_type poly) {
  311   int i;
  312 
  313   print_points(poly.point,poly.len);
  314   (void) fprintf(stderr,"\n");
  315   for (i=0;i<poly.transform_len;i++)
  316     (void) fprintf(stderr,"%d ",poly.transform_list[i]);
  317   (void) fprintf(stderr,"\n");
  318 }
  319 */
  320 
  321 static polyominoesstruct *polyominoeses = (polyominoesstruct *) NULL;
  322 
  323 static
  324 void random_permutation(int n, int a[]) {
  325   int i,j,k,r;
  326 
  327   for (i=0;i<n;i++) a[i] = -1;
  328   for (i=0;i<n;i++) {
  329     r=NRAND(n-i);
  330     k=0;
  331     while(a[k]!=-1) k++;
  332     for (j=0;j<r;j++) {
  333       k++;
  334       while(a[k]!=-1) k++;
  335     }
  336     a[k]=i;
  337   }
  338 }
  339 
  340 
  341 /************************************************************
  342 These are the routines for manipulating the polyominoes and
  343 attaching and detaching them from the rectangle.
  344 ************************************************************/
  345 
  346 static void transform(point_type in, point_type offset, int transform_no,
  347                       point_type attach_point, point_type *out) {
  348   switch (transform_no) {
  349     case 0: out->x=in.x-offset.x+attach_point.x;
  350             out->y=in.y-offset.y+attach_point.y;
  351             break;
  352     case 1: out->x=-(in.y-offset.y)+attach_point.x;
  353             out->y=in.x-offset.x+attach_point.y;
  354             break;
  355     case 2: out->x=-(in.x-offset.x)+attach_point.x;
  356             out->y=-(in.y-offset.y)+attach_point.y;
  357             break;
  358     case 3: out->x=in.y-offset.y+attach_point.x;
  359             out->y=-(in.x-offset.x)+attach_point.y;
  360             break;
  361     case 4: out->x=-(in.x-offset.x)+attach_point.x;
  362             out->y=in.y-offset.y+attach_point.y;
  363             break;
  364     case 5: out->x=in.y-offset.y+attach_point.x;
  365             out->y=in.x-offset.x+attach_point.y;
  366             break;
  367     case 6: out->x=in.x-offset.x+attach_point.x;
  368             out->y=-(in.y-offset.y)+attach_point.y;
  369             break;
  370     case 7: out->x=-(in.y-offset.y)+attach_point.x;
  371             out->y=-(in.x-offset.x)+attach_point.y;
  372             break;
  373   }
  374 }
  375 
  376 static int first_poly_no(polyominoesstruct *sp) {
  377   int poly_no;
  378 
  379   poly_no = 0;
  380   while(poly_no<sp->nr_polyominoes && sp->polyomino[poly_no].attached)
  381     poly_no++;
  382   return poly_no;
  383 }
  384 
  385 static void next_poly_no(polyominoesstruct *sp, int *poly_no) {
  386 
  387   if (sp->identical) {
  388     *poly_no = sp->nr_polyominoes;
  389   } else {
  390     do {
  391       (*poly_no)++;
  392     } while (*poly_no<sp->nr_polyominoes && sp->polyomino[*poly_no].attached);
  393   }
  394 }
  395 
  396 /* check_all_regions_multiple_of looks for connected regions of
  397    blank spaces, and returns 0 if it finds a connected region containing
  398    a number of blanks that is not a multiple of n.
  399 */
  400 
  401 static void count_adjacent_blanks(polyominoesstruct *sp, int *count, int x, int y, int blank_mark) {
  402 
  403   if (ARRAY(x,y) == -1) {
  404     (*count)++;
  405     ARRAY(x,y) = blank_mark;
  406     if (x>=1) count_adjacent_blanks(sp, count,x-1,y,blank_mark);
  407     if (x<sp->width-1) count_adjacent_blanks(sp, count,x+1,y,blank_mark);
  408     if (y>=1) count_adjacent_blanks(sp, count,x,y-1,blank_mark);
  409     if (y<sp->height-1) count_adjacent_blanks(sp, count,x,y+1,blank_mark);
  410   }
  411 }
  412 
  413 static int check_all_regions_multiple_of(polyominoesstruct *sp, int n) {
  414   int x,y,count,good = 1;
  415 
  416   for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
  417     count = 0;
  418     count_adjacent_blanks(sp, &count,x,y,-2);
  419     good = count%n == 0;
  420   }
  421 
  422   for (x=0;x<sp->width;x++)
  423     for (y=0;y<sp->height;y++)
  424       if (ARRAY(x,y) == -2)
  425         ARRAY(x,y) = -1;
  426 
  427   return good;
  428 }
  429 
  430 static int check_all_regions_positive_combination_of(polyominoesstruct *sp, int m, int n) {
  431   int x,y,count,good = 1;
  432 
  433   for (x=0;x<sp->width && good;x++) for (y=0;y<sp->height && good;y++) {
  434     count = 0;
  435     count_adjacent_blanks(sp, &count,x,y,-2);
  436     good = 0;
  437     for (;count>=0 && !good;count-=m)
  438       good = count%n == 0;
  439   }
  440 
  441   for (x=0;x<sp->width;x++)
  442     for (y=0;y<sp->height;y++)
  443       if (ARRAY(x,y) == -2)
  444         ARRAY(x,y) = -1;
  445 
  446   return good;
  447 }
  448 
  449 static int find_smallest_blank_component(polyominoesstruct *sp) {
  450   int x,y,size,smallest_size,blank_mark,smallest_mark;
  451 
  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) {
  455     size = 0;
  456     count_adjacent_blanks(sp, &size,x,y,blank_mark);
  457     if (size<smallest_size) {
  458       smallest_mark = blank_mark;
  459       smallest_size = size;
  460     }
  461     blank_mark--;
  462   }
  463 
  464   return smallest_mark;
  465 }
  466 
  467 /* "Chess board" check - see init_max_whites_list above for more details.
  468 */
  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.
  474 */
  475 
  476 static int whites_ok(polyominoesstruct *sp) {
  477   int x,y,poly_no,whites=0,blacks=0,max_white=0,min_white=0;
  478 
  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++;
  482   }
  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;
  486   }
  487   return (min_white <= blacks && min_white <= whites
  488           && blacks <= max_white && whites <= max_white);
  489 }
  490 
  491 /* This routine looks at the point (x,y) and sees how many polyominoes
  492    and all their various transforms may be attached there.
  493 */
  494 
  495 static int
  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;
  499   int score = 0;
  500 
  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)
  505     return 10000;
  506 
  507   attach_point.x = x;
  508   attach_point.y = y;
  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++) {
  513       attachable = 1;
  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))) {
  522           attachable = 0;
  523           break;
  524         }
  525       }
  526       if (attachable) {
  527         score++;
  528         if (score>=min_score_so_far)
  529           return score;
  530       }
  531      }
  532    }
  533 
  534   return score;
  535 }
  536 
  537 static void find_blank(polyominoesstruct *sp, point_type *point) {
  538   int score, worst_score;
  539   int x, y;
  540   int blank_mark;
  541 
  542   blank_mark = find_smallest_blank_component(sp);
  543 
  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);
  547     if (score>0) {
  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);
  552     }
  553     if (score<worst_score) {
  554       point->x = x;
  555       point->y = y;
  556       worst_score = score;
  557     }
  558   }
  559 
  560   for (x=0;x<sp->width;x++)
  561     for (y=0;y<sp->height;y++)
  562       if (ARRAY(x,y)<0) ARRAY(x,y) = -1;
  563 }
  564 
  565 /* Detaches the most recently attached polyomino. */
  566 
  567 static
  568 void detach(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index, point_type *attach_point, int rot180) {
  569   int i;
  570   point_type target_point;
  571 
  572   if (sp->nr_attached == 0) return;
  573   sp->nr_attached--;
  574   *poly_no = sp->attach_list[sp->nr_attached];
  575   *point_no = sp->polyomino[*poly_no].point_no;
  576   *transform_index = sp->polyomino[*poly_no].transform_index;
  577   *attach_point = sp->polyomino[*poly_no].attach_point;
  578   for (i=0;i<sp->polyomino[*poly_no].len;i++) {
  579     transform(sp->polyomino[*poly_no].point[i],
  580               sp->polyomino[*poly_no].point[*point_no],
  581               sp->polyomino[*poly_no].transform_list[*transform_index]^(rot180<<1),
  582               *attach_point, &target_point);
  583     ARRAY_P(target_point) = -1;
  584     CHANGED_ARRAY_P(target_point) = 1;
  585   }
  586 
  587   sp->polyomino[*poly_no].attached = 0;
  588 }
  589 
  590 /* Attempts to attach a polyomino at point (x,y) at the
  591    point_no-th point of that polyomino, using the transform
  592    transform_no.  Returns 1 if successful.
  593 */
  594 
  595 static
  596 int attach(polyominoesstruct *sp, int poly_no, int point_no, int transform_index, point_type attach_point, int rot180,
  597            int *reason_to_not_attach) {
  598   point_type target_point;
  599   int i;
  600   int attachable = 1, worst_reason_not_to_attach = 1000000000;
  601 
  602   if (rot180) {
  603     attach_point.x = sp->width-1-attach_point.x;
  604     attach_point.y = sp->height-1-attach_point.y;
  605   }
  606 
  607   if (sp->polyomino[poly_no].attached)
  608     return 0;
  609 
  610   for (i=0;i<sp->polyomino[poly_no].len;i++) {
  611     transform(sp->polyomino[poly_no].point[i],
  612               sp->polyomino[poly_no].point[point_no],
  613               sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
  614               attach_point, &target_point);
  615     if ( ! ((target_point.x>=0) && (target_point.x<sp->width)
  616               && (target_point.y>=0) && (target_point.y<sp->height)
  617               && (ARRAY_P(target_point) == -1))) {
  618       if (sp->identical) {
  619         attachable = 0;
  620         if ((target_point.x>=0) && (target_point.x<sp->width)
  621            && (target_point.y>=0) && (target_point.y<sp->height)
  622            && (ARRAY_P(target_point) >= 0)
  623            && (ARRAY_P(target_point)<worst_reason_not_to_attach))
  624           worst_reason_not_to_attach = ARRAY_P(target_point);
  625       }
  626       else
  627         return 0;
  628     }
  629   }
  630 
  631   if (sp->identical && !attachable) {
  632     if (worst_reason_not_to_attach < 1000000000)
  633       reason_to_not_attach[worst_reason_not_to_attach] = 1;
  634     return 0;
  635   }
  636 
  637   for (i=0;i<sp->polyomino[poly_no].len;i++) {
  638     transform(sp->polyomino[poly_no].point[i],
  639               sp->polyomino[poly_no].point[point_no],
  640               sp->polyomino[poly_no].transform_list[transform_index]^(rot180<<1),
  641               attach_point, &target_point);
  642     ARRAY_P(target_point) = poly_no;
  643     CHANGED_ARRAY_P(target_point) = 1;
  644   }
  645 
  646   sp->attach_list[sp->nr_attached] = poly_no;
  647   sp->nr_attached++;
  648 
  649   sp->polyomino[poly_no].attached = 1;
  650   sp->polyomino[poly_no].point_no = point_no;
  651   sp->polyomino[poly_no].attach_point = attach_point;
  652   sp->polyomino[poly_no].transform_index = transform_index;
  653 
  654   if (!sp->check_ok(sp)) {
  655     detach(sp,&poly_no,&point_no,&transform_index,&attach_point,rot180);
  656     return 0;
  657   }
  658 
  659   return 1;
  660 }
  661 
  662 static
  663 int next_attach_try(polyominoesstruct *sp, int *poly_no, int *point_no, int *transform_index) {
  664 
  665   (*transform_index)++;
  666   if (*transform_index>=sp->polyomino[*poly_no].transform_len) {
  667     *transform_index = 0;
  668     (*point_no)++;
  669     if (*point_no>=sp->polyomino[*poly_no].len) {
  670       *point_no = 0;
  671       next_poly_no(sp,poly_no);
  672       if (*poly_no>=sp->nr_polyominoes) {
  673         *poly_no = first_poly_no(sp);
  674         return 0;
  675       }
  676     }
  677   }
  678   return 1;
  679 }
  680 
  681 
  682 /*******************************************************
  683 Display routines.
  684 *******************************************************/
  685 
  686 static void
  687 draw_without_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
  688   Display *display = MI_DISPLAY(mi);
  689   Window  window = MI_WINDOW(mi);
  690   GC gc = MI_GC(mi);
  691   int x,y,poly_no,nr_lines,nr_rectangles;
  692 
  693   XSetLineAttributes(display,gc,sp->box/10+1,LineSolid,CapRound,JoinRound);
  694 
  695   for (poly_no=-1;poly_no<sp->nr_polyominoes;poly_no++) {
  696     nr_rectangles = 0;
  697     for (x=0;x<sp->width;x++)
  698       for (y=0;y<sp->height;y++)
  699         if (CHANGED_ARRAY(x,y) && ARRAY(x,y) == poly_no) {
  700           sp->rectangles[nr_rectangles].x = sp->x_margin + sp->box*x;
  701           sp->rectangles[nr_rectangles].y = sp->y_margin + sp->box*y;
  702           sp->rectangles[nr_rectangles].width = sp->box;
  703           sp->rectangles[nr_rectangles].height = sp->box;
  704           nr_rectangles++;
  705         }
  706     if (poly_no == -1)
  707       XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
  708     else
  709       XSetForeground(display, gc, sp->polyomino[poly_no].color);
  710     XFillRectangles(display, window, gc, sp->rectangles, nr_rectangles);
  711   }
  712 
  713   XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
  714 
  715   nr_lines = 0;
  716   for (x=0;x<sp->width-1;x++) for (y=0;y<sp->height;y++) {
  717     if (ARRAY(x,y) == -1 && ARRAY(x+1,y) == -1
  718         && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x+1,y))) {
  719       sp->lines[nr_lines].x1 = sp->x_margin + sp->box*(x+1);
  720       sp->lines[nr_lines].y1 = sp->y_margin + sp->box*y;
  721       sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
  722       sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
  723       nr_lines++;
  724     }
  725   }
  726   XDrawSegments(display, window, gc, sp->lines, nr_lines);
  727 
  728   nr_lines = 0;
  729   for (x=0;x<sp->width;x++) for (y=0;y<sp->height-1;y++) {
  730     if (ARRAY(x,y) == -1 && ARRAY(x,y+1) == -1
  731         && (CHANGED_ARRAY(x,y) || CHANGED_ARRAY(x,y+1))) {
  732       sp->lines[nr_lines].x1 = sp->x_margin + sp->box*x;
  733       sp->lines[nr_lines].y1 = sp->y_margin + sp->box*(y+1);
  734       sp->lines[nr_lines].x2 = sp->x_margin + sp->box*(x+1);
  735       sp->lines[nr_lines].y2 = sp->y_margin + sp->box*(y+1);
  736       nr_lines++;
  737     }
  738   }
  739   XDrawSegments(display, window, gc, sp->lines, nr_lines);
  740   XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
  741   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));
  743 
  744   nr_lines = 0;
  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);
  751       nr_lines++;
  752     }
  753   }
  754   XDrawSegments(display, window, gc, sp->lines, nr_lines);
  755 
  756   nr_lines = 0;
  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);
  763       nr_lines++;
  764     }
  765   }
  766   XDrawSegments(display, window, gc, sp->lines, nr_lines);
  767   XSetLineAttributes(display,gc,1,LineSolid,CapRound,JoinRound);
  768   XFlush(display);
  769 }
  770 
  771 static void create_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
  772   int x,y,n;
  773   char *data;
  774 
  775   for (n=0;n<256;n++) {
  776 
  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];
  786 
  787     else /* if (bitmap_needed(n)) */ {
  788       data = (char *) malloc(sizeof(char)*(sp->box*ROUND8(sp->box)/8));
  789       if (data == NULL) {
  790         sp->use_bitmaps = 0;
  791         return;
  792       }
  793 
  794       for (y=0;y<sp->box;y++) for (x=0;x<sp->box;x++) {
  795         if (!sp->use3D) {
  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)
  799             NOTHALFBIT(n,x,y)
  800           else
  801 #endif
  802             HALFBIT(n,x,y)
  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)))
  806           SETBIT(n,x,y)
  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)))
  810           TWOTHIRDSBIT(n,x,y)
  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)))
  814           HALFBIT(n,x,y)
  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)))
  818           THIRDBIT(n,x,y)
  819       }
  820 
  821       if (IS_LEFT(n))
  822         for (y=0;y<sp->box;y++)
  823           for (x=G;x<G+T;x++)
  824             SETBIT(n,x,y)
  825       if (IS_RIGHT(n))
  826         for (y=0;y<sp->box;y++)
  827           for (x=G;x<G+T;x++)
  828             SETBIT(n,sp->box-1-x,y)
  829       if (IS_UP(n))
  830         for (x=0;x<sp->box;x++)
  831           for (y=G;y<G+T;y++)
  832             SETBIT(n,x,y)
  833       if (IS_DOWN(n))
  834         for (x=0;x<sp->box;x++)
  835           for (y=G;y<G+T;y++)
  836             SETBIT(n,x,sp->box-1-y)
  837       if (IS_LEFT(n))
  838         for (y=0;y<sp->box;y++)
  839           for (x=0;x<G;x++)
  840             RESBIT(n,x,y)
  841       if (IS_RIGHT(n))
  842         for (y=0;y<sp->box;y++)
  843           for (x=0;x<G;x++)
  844             RESBIT(n,sp->box-1-x,y)
  845       if (IS_UP(n))
  846         for (x=0;x<sp->box;x++)
  847           for (y=0;y<G;y++)
  848             RESBIT(n,x,y)
  849       if (IS_DOWN(n))
  850         for (x=0;x<sp->box;x++)
  851           for (y=0;y<G;y++)
  852             RESBIT(n,x,sp->box-1-y)
  853 
  854       if (IS_LEFT(n) && IS_UP(n))
  855         for (x=G;x<=G+R;x++)
  856           for (y=G;y<=R+2*G-x;y++) {
  857             if (x+y>R+2*G-RT)
  858               SETBIT(n,x,y)
  859             else
  860               RESBIT(n,x,y)
  861           }
  862       if (IS_LEFT(n) && IS_DOWN(n))
  863         for (x=G;x<=G+R;x++)
  864           for (y=G;y<=R+2*G-x;y++) {
  865             if (x+y>R+2*G-RT)
  866               SETBIT(n,x,sp->box-1-y)
  867             else
  868               RESBIT(n,x,sp->box-1-y)
  869           }
  870       if (IS_RIGHT(n) && IS_UP(n))
  871         for (x=G;x<=G+R;x++)
  872           for (y=G;y<=R+2*G-x;y++) {
  873             if (x+y>R+2*G-RT)
  874               SETBIT(n,sp->box-1-x,y)
  875             else
  876               RESBIT(n,sp->box-1-x,y)
  877           }
  878       if (IS_RIGHT(n) && IS_DOWN(n))
  879         for (x=G;x<=G+R;x++)
  880           for (y=G;y<=R+2*G-x;y++) {
  881             if (x+y>R+2*G-RT)
  882               SETBIT(n,sp->box-1-x,sp->box-1-y)
  883             else
  884               RESBIT(n,sp->box-1-x,sp->box-1-y)
  885           }
  886 
  887       if (!IS_LEFT(n) && !IS_UP(n) && IS_LEFT_UP(n)) {
  888         for (x=0;x<G;x++)
  889           for(y=0;y<G;y++)
  890             RESBIT(n,x,y)
  891         for (x=G;x<G+T;x++)
  892           for(y=0;y<G;y++)
  893             SETBIT(n,x,y)
  894         for (x=0;x<G+T;x++)
  895           for(y=G;y<G+T;y++)
  896             SETBIT(n,x,y)
  897       }
  898       if (!IS_LEFT(n) && !IS_DOWN(n) && IS_LEFT_DOWN(n)) {
  899         for (x=0;x<G;x++)
  900           for(y=0;y<G;y++)
  901             RESBIT(n,x,sp->box-1-y)
  902         for (x=G;x<G+T;x++)
  903           for(y=0;y<G;y++)
  904             SETBIT(n,x,sp->box-1-y)
  905         for (x=0;x<G+T;x++)
  906           for(y=G;y<G+T;y++)
  907             SETBIT(n,x,sp->box-1-y)
  908       }
  909       if (!IS_RIGHT(n) && !IS_UP(n) && IS_RIGHT_UP(n)) {
  910         for (x=0;x<G;x++)
  911           for(y=0;y<G;y++)
  912             RESBIT(n,sp->box-1-x,y)
  913         for (x=G;x<G+T;x++)
  914           for(y=0;y<G;y++)
  915             SETBIT(n,sp->box-1-x,y)
  916         for (x=0;x<G+T;x++)
  917           for(y=G;y<G+T;y++)
  918             SETBIT(n,sp->box-1-x,y)
  919       }
  920       if (!IS_RIGHT(n) && !IS_DOWN(n) && IS_RIGHT_DOWN(n)) {
  921         for (x=0;x<G;x++)
  922           for(y=0;y<G;y++)
  923             RESBIT(n,sp->box-1-x,sp->box-1-y)
  924         for (x=G;x<G+T;x++) 
  925           for(y=0;y<G;y++)
  926             SETBIT(n,sp->box-1-x,sp->box-1-y)
  927         for (x=0;x<G+T;x++)
  928           for(y=G;y<G+T;y++)
  929             SETBIT(n,sp->box-1-x,sp->box-1-y)
  930       }
  931 
  932 #ifdef LARGE_BELLYBUTTON
  933       if (!sp->use3D) {
  934         if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
  935           for (x=0;x<G+T;x++)
  936             for(y=0;y<G+T;y++)
  937               SETBIT(n,x,y)
  938         if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
  939           for (x=0;x<G+T;x++)
  940             for(y=sp->box-G-T;y<sp->box;y++)
  941               SETBIT(n,x,y)
  942         if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
  943           for (x=sp->box-G-T;x<sp->box;x++)
  944             for(y=0;y<G+T;y++)
  945               SETBIT(n,x,y)
  946         if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
  947           for (x=sp->box-G-T;x<sp->box;x++)
  948             for(y=sp->box-G-T;y<sp->box;y++)
  949               SETBIT(n,x,y)
  950       } else
  951 #else
  952       if (sp->use3D)
  953 #endif
  954       {
  955         if (!IS_LEFT(n) && !IS_UP(n) && !IS_LEFT_UP(n))
  956           for (x=0;x<sp->box/2-RR;x++)
  957             for(y=0;y<sp->box/2-RR;y++)
  958               THREEQUARTERSBIT(n,x,y)
  959         if (!IS_LEFT(n) && !IS_DOWN(n) && !IS_LEFT_DOWN(n))
  960           for (x=0;x<sp->box/2-RR;x++)
  961             for(y=sp->box/2+RR;y<sp->box;y++)
  962               THREEQUARTERSBIT(n,x,y)
  963         if (!IS_RIGHT(n) && !IS_UP(n) && !IS_RIGHT_UP(n))
  964           for (x=sp->box/2+RR;x<sp->box;x++)
  965             for(y=0;y<sp->box/2-RR;y++)
  966               THREEQUARTERSBIT(n,x,y)
  967         if (!IS_RIGHT(n) && !IS_DOWN(n) && !IS_RIGHT_DOWN(n))
  968           for (x=sp->box/2+RR;x<sp->box;x++)
  969             for(y=sp->box/2+RR;y<sp->box;y++)
  970               THREEQUARTERSBIT(n,x,y)
  971       }
  972 
  973       sp->bitmaps[n] = XCreateImage(MI_DISPLAY(mi), MI_VISUAL(mi), 1, XYBitmap,
  974                                     0, data, sp->box, sp->box, 8, 0);
  975       if (sp->bitmaps[n] == None) {
  976         free(data);
  977         sp->use_bitmaps = 0;
  978         return;
  979       }
  980       sp->bitmaps[n]->byte_order = MSBFirst;
  981       sp->bitmaps[n]->bitmap_unit = 8;
  982       sp->bitmaps[n]->bitmap_bit_order = LSBFirst;
  983     }
  984   }
  985 
  986   sp->use_bitmaps = 1;
  987 }
  988 
  989 static void draw_with_bitmaps(ModeInfo * mi, polyominoesstruct *sp) {
  990   Display *display = MI_DISPLAY(mi);
  991   Window  window = MI_WINDOW(mi);
  992   GC gc = MI_GC(mi);
  993   int x,y,t,bitmap_index;
  994 
  995   for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) {
  996     if (ARRAY(x,y) == -1) {
  997       if (CHANGED_ARRAY(x,y)) {
  998         XSetForeground(display, gc, MI_BLACK_PIXEL(mi));
  999         XFillRectangle(display,window,gc,
 1000                        sp->x_margin + sp->box*x,
 1001                        sp->y_margin + sp->box*y,
 1002                        sp->box,sp->box);
 1003       }
 1004     }
 1005     else {
 1006       XSetForeground(display, gc, sp->polyomino[ARRAY(x,y)].color);
 1007       bitmap_index = 0;
 1008       if (ARR(x,y) != ARR(x-1,y))   bitmap_index |= LEFT;
 1009       if (ARR(x,y) != ARR(x+1,y))   bitmap_index |= RIGHT;
 1010       if (ARR(x,y) != ARR(x,y-1))   bitmap_index |= UP;
 1011       if (ARR(x,y) != ARR(x,y+1))   bitmap_index |= DOWN;
 1012       if (ARR(x,y) != ARR(x-1,y-1)) bitmap_index |= LEFT_UP;
 1013       if (ARR(x,y) != ARR(x-1,y+1)) bitmap_index |= LEFT_DOWN;
 1014       if (ARR(x,y) != ARR(x+1,y-1)) bitmap_index |= RIGHT_UP;
 1015       if (ARR(x,y) != ARR(x+1,y+1)) bitmap_index |= RIGHT_DOWN;
 1016       (void) XPutImage(display,window,gc,
 1017                 sp->bitmaps[bitmap_index],
 1018                 0,0,
 1019                 sp->x_margin + sp->box*x,
 1020                 sp->y_margin + sp->box*y,
 1021                 sp->box,sp->box);
 1022     }
 1023   }
 1024 
 1025   XSetForeground(display, gc, sp->border_color);
 1026   for (t=G;t<G+T;t++)
 1027     XDrawRectangle(display,window,gc,
 1028                    sp->x_margin-t-1,sp->y_margin-t-1,
 1029                    sp->box*sp->width+1+2*t, sp->box*sp->height+1+2*t);
 1030   XFlush(display);
 1031 }
 1032 
 1033 
 1034 /***************************************************
 1035 Routines to initialise and close down polyominoes.
 1036 ***************************************************/
 1037 
 1038 static void free_bitmaps(polyominoesstruct *sp) {
 1039   int n;
 1040 
 1041   for (n=0;n<256;n++)
 1042 /* Don't bother to free duplicates */
 1043     if (IS_LEFT_UP(n) && (IS_LEFT(n) || IS_UP(n)))
 1044       sp->bitmaps[n] = None;
 1045     else if (IS_LEFT_DOWN(n) && (IS_LEFT(n) || IS_DOWN(n)))
 1046       sp->bitmaps[n] = None;
 1047     else if (IS_RIGHT_UP(n) && (IS_RIGHT(n) || IS_UP(n)))
 1048       sp->bitmaps[n] = None;
 1049     else if (IS_RIGHT_DOWN(n) && (IS_RIGHT(n) || IS_DOWN(n)))
 1050       sp->bitmaps[n] = None;
 1051 
 1052     else if (sp->bitmaps[n] != None) {
 1053         XDestroyImage(sp->bitmaps[n]);
 1054         sp->bitmaps[n] = None;
 1055     }
 1056 }
 1057 
 1058 #define deallocate(p,t) if ((p)!=NULL) {free(p); p=(t*)NULL;}
 1059 
 1060 static void
 1061 free_polyominoes_screen(polyominoesstruct *sp) {
 1062   int n;
 1063 
 1064   if (sp == NULL) {
 1065     return;
 1066   }
 1067   for (n=0;n<sp->nr_polyominoes;n++) {
 1068     deallocate(sp->polyomino[n].point, point_type);
 1069   }
 1070 
 1071   deallocate(sp->polyomino, polyomino_type);
 1072   deallocate(sp->attach_list, int);
 1073   deallocate(sp->rectangles, XRectangle);
 1074   deallocate(sp->lines, XSegment);
 1075   deallocate(sp->reason_to_not_attach, int);
 1076   deallocate(sp->array, int);
 1077   deallocate(sp->changed_array, int);
 1078 
 1079   free_bitmaps(sp);
 1080   sp = NULL;
 1081 }
 1082 
 1083 ENTRYPOINT void
 1084 free_polyominoes(ModeInfo *mi)
 1085 {
 1086   free_polyominoes_screen(&polyominoeses[MI_SCREEN(mi)]);
 1087 }
 1088 
 1089 #define set_allocate(p,type,size) p = (type *) malloc(size);        \
 1090   if ((p)==NULL) {free_polyominoes_screen(sp);return 0;}
 1091 
 1092 #define copy_polyomino(dst,src,new_rand)                \
 1093   (dst).len=(src).len;                          \
 1094   (dst).max_white = (src).max_white;                    \
 1095   set_allocate((dst).point,point_type,sizeof(point_type)*(src).len);    \
 1096   (dst).len = (src).len;                        \
 1097   if (new_rand)                             \
 1098     random_permutation((src).len,perm_point);               \
 1099   for (i=0;i<(src).len;i++)                     \
 1100     (dst).point[i] = (src).point[perm_point[i]];            \
 1101   (dst).transform_len = (src).transform_len;                \
 1102   if (new_rand)                             \
 1103     random_permutation((src).transform_len,perm_transform);     \
 1104   for (i=0;i<(src).transform_len;i++)                   \
 1105     (dst).transform_list[i] = (src).transform_list[perm_transform[i]];  \
 1106   (dst).attached = 0
 1107 
 1108 
 1109 /***************************************************
 1110 Puzzle specific initialization routines.
 1111 ***************************************************/
 1112 
 1113 static
 1114 int check_pentomino_puzzle(polyominoesstruct *sp) {
 1115   return check_all_regions_multiple_of(sp, 5) && whites_ok(sp);
 1116 }
 1117 
 1118 static
 1119 int check_hexomino_puzzle(polyominoesstruct *sp) {
 1120   return check_all_regions_multiple_of(sp, 6) && whites_ok(sp);
 1121 }
 1122 
 1123 static
 1124 int check_tetr_pentomino_puzzle(polyominoesstruct *sp) {
 1125   return check_all_regions_positive_combination_of(sp, 5, 4) && whites_ok(sp);
 1126 }
 1127 
 1128 static
 1129 int check_pent_hexomino_puzzle(polyominoesstruct *sp) {
 1130   return check_all_regions_positive_combination_of(sp, 6, 5) && whites_ok(sp);
 1131 }
 1132 
 1133 static
 1134 int check_heptomino_puzzle(polyominoesstruct *sp) {
 1135   return check_all_regions_multiple_of(sp, 7) && whites_ok(sp);
 1136 }
 1137 
 1138 static
 1139 int check_octomino_puzzle(polyominoesstruct *sp) {
 1140   return check_all_regions_multiple_of(sp, 8) && whites_ok(sp);
 1141 }
 1142 
 1143 static
 1144 int check_dekomino_puzzle(polyominoesstruct *sp) {
 1145   return check_all_regions_multiple_of(sp, 10) && whites_ok(sp);
 1146 }
 1147 
 1148 static
 1149 int check_elevenomino_puzzle(polyominoesstruct *sp) {
 1150   return check_all_regions_multiple_of(sp, 11) && whites_ok(sp);
 1151 }
 1152 
 1153 static struct {int len; point_type point[4];
 1154                int transform_len, transform_list[8], max_white;} tetromino[5] =
 1155 {
 1156 /*
 1157 xxxx
 1158 */
 1159   {4, {{0,0}, {1,0}, {2,0}, {3,0}},
 1160    2, {0, 1, -1, -1, -1, -1, -1, -1}, 2},
 1161 /*
 1162 xxx
 1163   x
 1164 */
 1165   {4, {{0,0}, {1,0}, {2,0}, {2,1}},
 1166    8, {0, 1, 2, 3, 4, 5, 6, 7}, 2},
 1167 /*
 1168 xxx
 1169  x
 1170 */
 1171   {4, {{0,0}, {1,0}, {1,1}, {2,0}},
 1172    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
 1173 /*
 1174 xx
 1175  xx
 1176 */
 1177   {4, {{0,0}, {1,0}, {1,1}, {2,1}},
 1178    4, {0, 1, 4, 5, -1, -1, -1, -1}, 2},
 1179 /*
 1180 xx
 1181 xx
 1182 */
 1183   {4, {{0,0}, {0,1}, {1,0}, {1,1}},
 1184    1, {0, -1, -1, -1, -1, -1, -1, -1}, 2}};
 1185 
 1186 
 1187 static struct pentomino_struct {int len; point_type point[5];
 1188                                 int transform_len, transform_list[8], max_white;}
 1189   pentomino[12] =
 1190 {
 1191 /*
 1192 xxxxx
 1193 */
 1194   {5, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}},
 1195    2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
 1196 /*
 1197 xxxx
 1198    x
 1199 */
 1200   {5, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}},
 1201    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1202 /*
 1203 xxxx
 1204   x
 1205 */
 1206   {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}},
 1207    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1208 /*
 1209   x
 1210 xxx
 1211   x
 1212 */
 1213   {5, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}},
 1214    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
 1215 /*
 1216 xxx
 1217   xx
 1218 */
 1219   {5, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}},
 1220    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1221 /*
 1222 xxx
 1223  xx
 1224 */
 1225   {5, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}},
 1226    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1227 /*
 1228 xxx
 1229   x
 1230   x
 1231 */
 1232   {5, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}},
 1233    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
 1234 /*
 1235  x
 1236 xxx
 1237   x
 1238 */
 1239   {5, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}},
 1240    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1241 /*
 1242 xxx
 1243 x x
 1244 */
 1245   {5, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}},
 1246    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
 1247 /*
 1248   x
 1249 xxx
 1250 x
 1251 */
 1252   {5, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}},
 1253    4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
 1254 /*
 1255  x
 1256 xxx
 1257  x
 1258 */
 1259   {5, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}},
 1260    1, {0, -1, -1, -1, -1, -1, -1, -1}, 4},
 1261 /*
 1262 xx
 1263  xx
 1264   x
 1265 */
 1266   {5, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}},
 1267    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3}};
 1268 
 1269 
 1270 static struct hexomino_struct {int len; point_type point[6];
 1271                                int transform_len, transform_list[8], max_white;}
 1272   hexomino[35] =
 1273 {
 1274 /*
 1275 xxxxxx
 1276 */
 1277   {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}},
 1278    2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
 1279 /*
 1280 xxxxx
 1281     x
 1282 */
 1283   {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {4,1}},
 1284    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1285 /*
 1286 xxxxx
 1287    x
 1288 */
 1289   {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,0}},
 1290    8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
 1291 /*
 1292 xxxxx
 1293   x
 1294 */
 1295   {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {4,0}},
 1296    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
 1297 /*
 1298    x
 1299 xxxx
 1300    x
 1301 */
 1302   {6, {{0,0}, {1,0}, {2,0}, {3,-1}, {3,0}, {3,1}},
 1303    4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
 1304 /*
 1305 xxxx
 1306    xx
 1307 */
 1308   {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {4,1}},
 1309    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1310 /*
 1311 xxxx
 1312   xx
 1313 */
 1314   {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,0}, {3,1}},
 1315    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1316 /*
 1317 xxxx
 1318    x
 1319    x
 1320 */
 1321   {6, {{0,0}, {1,0}, {2,0}, {3,0}, {3,1}, {3,2}},
 1322    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1323 /*
 1324   x
 1325 xxxx
 1326    x
 1327 */
 1328   {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {3,0}, {3,1}},
 1329    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1330 /*
 1331 xxxx
 1332  x x
 1333 */
 1334   {6, {{0,0}, {1,0}, {1,1}, {2,0}, {3,0}, {3,1}},
 1335    8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
 1336 /*
 1337  x
 1338 xxxx
 1339    x
 1340 */
 1341   {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {3,0}, {3,1}},
 1342    8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
 1343 /*
 1344 xxxx
 1345 x  x
 1346 */
 1347   {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1}},
 1348    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
 1349 /*
 1350    x
 1351 xxxx
 1352 x
 1353 */
 1354   {6, {{0,0}, {0,1}, {1,0}, {2,0}, {3,-1}, {3,0}},
 1355    4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
 1356 /*
 1357   x
 1358 xxxx
 1359   x
 1360 */
 1361   {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,0}},
 1362    4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
 1363 /*
 1364 xxxx
 1365  xx
 1366 */
 1367   {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,0}},
 1368    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
 1369 /*
 1370 xxxx
 1371   x
 1372   x
 1373 */
 1374   {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,0}},
 1375    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1376 /*
 1377  x
 1378 xxxx
 1379   x
 1380 */
 1381   {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,0}},
 1382    4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
 1383 /*
 1384   xx
 1385 xxx
 1386   x
 1387 */
 1388   {6, {{0,0}, {1,0}, {2,-1}, {2,0}, {2,1}, {3,-1}},
 1389    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1390 /*
 1391  xx
 1392 xxx
 1393   x
 1394 */
 1395   {6, {{0,0}, {1,-1}, {1,0}, {2,-1}, {2,0}, {2,1}},
 1396    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1397 /*
 1398   x
 1399 xxx
 1400 x x
 1401 */
 1402   {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {2,1}},
 1403    8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
 1404 /*
 1405 xxx
 1406   xxx
 1407 */
 1408   {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {4,1}},
 1409    4, {0, 1, 4, 5, -1, -1, -1, -1}, 3},
 1410 /*
 1411 xxx
 1412   xx
 1413    x
 1414 */
 1415   {6, {{0,0}, {1,0}, {2,0}, {2,1}, {3,1}, {3,2}},
 1416    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1417 /*
 1418 xxx
 1419  xxx
 1420 */
 1421   {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {3,1}},
 1422    4, {0, 1, 4, 5, -1, -1, -1, -1}, 4},
 1423 /*
 1424 xxx
 1425   xx
 1426   x
 1427 */
 1428   {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,1}},
 1429    8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
 1430 /*
 1431  x
 1432 xxx
 1433   xx
 1434 */
 1435   {6, {{0,0}, {1,-1}, {1,0}, {2,0}, {2,1}, {3,1}},
 1436    8, {0, 1, 2, 3, 4, 5, 6, 7}, 4},
 1437 /*
 1438 xxx
 1439 x xx
 1440 */
 1441   {6, {{0,0}, {0,1}, {1,0}, {2,0}, {2,1}, {3,1}},
 1442    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1443 /*
 1444 xxx
 1445  xx
 1446   x
 1447 */
 1448   {6, {{0,0}, {1,0}, {1,1}, {2,0}, {2,1}, {2,2}},
 1449    4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
 1450 /*
 1451  x
 1452 xxx
 1453  xx
 1454 */
 1455   {6, {{0,0}, {1,-1}, {1,0}, {1,1}, {2,0}, {2,1}},
 1456    4, {0, 1, 2, 3, -1, -1, -1, -1}, 4},
 1457 /*
 1458 xxx
 1459 xxx
 1460 */
 1461   {6, {{0,0}, {0,1}, {1,0}, {1,1}, {2,0}, {2,1}},
 1462    2, {0, 1, -1, -1, -1, -1, -1, -1}, 3},
 1463 /*
 1464 xxx
 1465   x
 1466   xx
 1467 */
 1468   {6, {{0,0}, {1,0}, {2,0}, {2,1}, {2,2}, {3,2}},
 1469    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1470 /*
 1471 xxx
 1472   x
 1473  xx
 1474 */
 1475   {6, {{0,0}, {1,0}, {1,2}, {2,0}, {2,1}, {2,2}},
 1476    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1477 /*
 1478  x
 1479 xxx
 1480 x x
 1481 */
 1482   {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,0}, {2,1}},
 1483    4, {0, 1, 2, 3, -1, -1, -1, -1}, 3},
 1484 /*
 1485   xx
 1486 xxx
 1487 x
 1488 */
 1489   {6, {{0,0}, {0,1}, {1,0}, {2,-1}, {2,0}, {3,-1}},
 1490    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1491 /*
 1492  xx
 1493 xxx
 1494 x
 1495 */
 1496   {6, {{0,0}, {0,1}, {1,-1}, {1,0}, {2,-1}, {2,0}},
 1497    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3},
 1498 /*
 1499 xx
 1500  xx
 1501   xx
 1502 */
 1503   {6, {{0,0}, {1,0}, {1,1}, {2,1}, {2,2}, {3,2}},
 1504    4, {0, 1, 4, 5, -1, -1, -1, -1}, 3}};
 1505 
 1506 static struct pentomino_struct one_sided_pentomino[60];
 1507 
 1508 static void
 1509 make_one_sided_pentomino(void) {
 1510   int i,j,t,u;
 1511 
 1512   j=0;
 1513   for (i=0;i<12;i++) {
 1514     one_sided_pentomino[j] = pentomino[i];
 1515     for (t=0;t<8;t++)
 1516       if (one_sided_pentomino[j].transform_list[t]>=4) {
 1517         one_sided_pentomino[j].transform_len = t;
 1518         j++;
 1519         one_sided_pentomino[j] = pentomino[i];
 1520         for (u=t;u<8;u++) one_sided_pentomino[j].transform_list[u-t] = one_sided_pentomino[j].transform_list[u];
 1521         one_sided_pentomino[j].transform_len -= t;
 1522         break;
 1523       }
 1524     j++;
 1525   }
 1526 }
 1527 
 1528 static struct hexomino_struct one_sided_hexomino[60];
 1529 
 1530 static void
 1531 make_one_sided_hexomino(void) {
 1532   int i,j,t,u;
 1533 
 1534   j=0;
 1535   for (i=0;i<35;i++) {
 1536     one_sided_hexomino[j] = hexomino[i];
 1537     for (t=0;t<8;t++)
 1538       if (one_sided_hexomino[j].transform_list[t]>=4) {
 1539         one_sided_hexomino[j].transform_len = t;
 1540         j++;
 1541         one_sided_hexomino[j] = hexomino[i];
 1542         for (u=t;u<8;u++) one_sided_hexomino[j].transform_list[u-t] = one_sided_hexomino[j].transform_list[u];
 1543         one_sided_hexomino[j].transform_len -= t;
 1544         break;
 1545       }
 1546     j++;
 1547   }
 1548 }
 1549 
 1550 /*
 1551 Find all the ways of placing all twelve pentominoes
 1552 into a rectangle whose size is 20x3, 15x4, 12x5 or 10x6.
 1553 */
 1554 
 1555 static
 1556 int set_pentomino_puzzle(polyominoesstruct *sp) {
 1557   int perm_poly[12], perm_point[5], perm_transform[8], i, p;
 1558 
 1559   switch (NRAND(4)) {
 1560     case 0:
 1561       sp->width = 20;
 1562       sp->height = 3;
 1563       break;
 1564     case 1:
 1565       sp->width = 15;
 1566       sp->height = 4;
 1567       break;
 1568     case 2:
 1569       sp->width = 12;
 1570       sp->height = 5;
 1571       break;
 1572     case 3:
 1573       sp->width = 10;
 1574       sp->height = 6;
 1575       break;
 1576   }
 1577 
 1578   sp->nr_polyominoes = 12;
 1579   set_allocate(sp->polyomino,polyomino_type,12*sizeof(polyomino_type));
 1580   random_permutation(12,perm_poly);
 1581   for (p=0;p<12;p++) {
 1582     copy_polyomino(sp->polyomino[p],pentomino[perm_poly[p]],1);
 1583   }
 1584 
 1585   sp->check_ok = check_pentomino_puzzle;
 1586 
 1587   return 1;
 1588 }
 1589 
 1590 /*
 1591 Many of the following puzzles are inspired by
 1592 http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
 1593 */
 1594 
 1595 /*
 1596 Find all the ways of placing all eighteen one-sided pentominoes
 1597 into a rectangle.
 1598 */
 1599 
 1600 static
 1601 int set_one_sided_pentomino_puzzle(polyominoesstruct *sp) {
 1602   int perm_poly[18], perm_point[5], perm_transform[8], i, p;
 1603 
 1604   make_one_sided_pentomino();
 1605 
 1606   switch (NRAND(4)) {
 1607     case 0:
 1608       sp->width = 30;
 1609       sp->height = 3;
 1610       break;
 1611     case 1:
 1612       sp->width = 18;
 1613       sp->height = 5;
 1614       break;
 1615     case 2:
 1616       sp->width = 15;
 1617       sp->height = 6;
 1618       break;
 1619     case 3:
 1620       sp->width = 10;
 1621       sp->height = 9;
 1622       break;
 1623   }
 1624 
 1625   sp->nr_polyominoes = 18;
 1626   set_allocate(sp->polyomino,polyomino_type,18*sizeof(polyomino_type));
 1627   random_permutation(18,perm_poly);
 1628   for (p=0;p<18;p++) {
 1629     copy_polyomino(sp->polyomino[p],one_sided_pentomino[perm_poly[p]],1);
 1630   }
 1631 
 1632   sp->check_ok = check_pentomino_puzzle;
 1633 
 1634   return 1;
 1635 }
 1636 
 1637 /*
 1638 Find all the ways of placing all sixty one-sided hexominoes
 1639 into a rectangle.
 1640 */
 1641 
 1642 static
 1643 int set_one_sided_hexomino_puzzle(polyominoesstruct *sp) {
 1644   int perm_poly[60], perm_point[6], perm_transform[8], i, p;
 1645 
 1646   make_one_sided_hexomino();
 1647 
 1648   switch (NRAND(8)) {
 1649     case 0:
 1650       sp->width = 20;
 1651       sp->height = 18;
 1652       break;
 1653     case 1:
 1654       sp->width = 24;
 1655       sp->height = 15;
 1656       break;
 1657     case 2:
 1658       sp->width = 30;
 1659       sp->height = 12;
 1660       break;
 1661     case 3:
 1662       sp->width = 36;
 1663       sp->height = 10;
 1664       break;
 1665     case 4:
 1666       sp->width = 40;
 1667       sp->height = 9;
 1668       break;
 1669     case 5:
 1670       sp->width = 45;
 1671       sp->height = 8;
 1672       break;
 1673     case 6:
 1674       sp->width = 60;
 1675       sp->height = 6;
 1676       break;
 1677     case 7:
 1678       sp->width = 72;
 1679       sp->height = 5;
 1680       break;
 1681   }
 1682 
 1683   sp->nr_polyominoes = 60;
 1684   set_allocate(sp->polyomino,polyomino_type,60*sizeof(polyomino_type));
 1685   random_permutation(60,perm_poly);
 1686   for (p=0;p<60;p++) {
 1687     copy_polyomino(sp->polyomino[p],one_sided_hexomino[perm_poly[p]],1);
 1688   }
 1689 
 1690   sp->check_ok = check_hexomino_puzzle;
 1691 
 1692   return 1;
 1693 }
 1694 
 1695 /*
 1696 Find all the ways of placing all five tetrominoes and all twelve
 1697 pentominoes into a rectangle.
 1698 */
 1699 
 1700 static
 1701 int set_tetr_pentomino_puzzle(polyominoesstruct *sp) {
 1702   int perm_poly[17], perm_point[5], perm_transform[8], i, p;
 1703 
 1704   switch (NRAND(3)) {
 1705     case 0:
 1706       sp->width = 20;
 1707       sp->height = 4;
 1708       break;
 1709     case 1:
 1710       sp->width = 16;
 1711       sp->height = 5;
 1712       break;
 1713     case 2:
 1714       sp->width = 10;
 1715       sp->height = 8;
 1716       break;
 1717   }
 1718 
 1719   sp->nr_polyominoes = 17;
 1720   set_allocate(sp->polyomino,polyomino_type,17*sizeof(polyomino_type));
 1721   random_permutation(17,perm_poly);
 1722   for (p=0;p<5;p++) {
 1723     copy_polyomino(sp->polyomino[perm_poly[p]],tetromino[p],1);
 1724   }
 1725   for (p=0;p<12;p++) {
 1726     copy_polyomino(sp->polyomino[perm_poly[p+5]],pentomino[p],1);
 1727   }
 1728 
 1729   sp->check_ok = check_tetr_pentomino_puzzle;
 1730 
 1731   return 1;
 1732 }
 1733 /*
 1734 Find all the ways of placing all twelve pentominoes and all thirty five
 1735 hexominoes into a rectangle whose size is 18x15.
 1736 */
 1737 
 1738 static
 1739 int set_pent_hexomino_puzzle(polyominoesstruct *sp) {
 1740   int perm_poly[47], perm_point[6], perm_transform[8], i, p;
 1741 
 1742   switch (NRAND(5)) {
 1743     case 0:
 1744       sp->width = 54;
 1745       sp->height = 5;
 1746       break;
 1747     case 1:
 1748       sp->width = 45;
 1749       sp->height = 6;
 1750       break;
 1751     case 2:
 1752       sp->width = 30;
 1753       sp->height = 9;
 1754       break;
 1755     case 3:
 1756       sp->width = 27;
 1757       sp->height = 10;
 1758       break;
 1759     case 4:
 1760       sp->width = 18;
 1761       sp->height = 15;
 1762       break;
 1763   }
 1764 
 1765   sp->nr_polyominoes = 47;
 1766   set_allocate(sp->polyomino,polyomino_type,47*sizeof(polyomino_type));
 1767   random_permutation(47,perm_poly);
 1768   for (p=0;p<12;p++) {
 1769     copy_polyomino(sp->polyomino[perm_poly[p]],pentomino[p],1);
 1770   }
 1771   for (p=0;p<35;p++) {
 1772     copy_polyomino(sp->polyomino[perm_poly[p+12]],hexomino[p],1);
 1773   }
 1774 
 1775   sp->check_ok = check_pent_hexomino_puzzle;
 1776 
 1777   return 1;
 1778 }
 1779 
 1780 /*
 1781 Other puzzles:
 1782 
 1783 Science News September 20, 1986 Vol 130, No 12
 1784 Science News November 14, 1987 Vol 132, Pg 310
 1785 */
 1786 
 1787 /*
 1788 
 1789  *
 1790 **** fills a 10x5 rectangle
 1791 
 1792 */
 1793 
 1794 static struct {int len; point_type point[5];
 1795                int transform_len, transform_list[8], max_white;} pentomino1 =
 1796   {5, {{0,0}, {1,0}, {2,0}, {3,0}, {1,1}},
 1797    8, {0, 1, 2, 3, 4, 5, 6, 7}, 3};
 1798 
 1799 static
 1800 int set_pentomino_puzzle1(polyominoesstruct *sp) {
 1801   int perm_point[5], perm_transform[8], i, p;
 1802 
 1803   sp->width = 10;
 1804   sp->height =5;
 1805 
 1806   sp->nr_polyominoes = 10;
 1807   set_allocate(sp->polyomino,polyomino_type,10*sizeof(polyomino_type));
 1808   for (p=0;p<10;p++) {
 1809     copy_polyomino(sp->polyomino[p],pentomino1,1);
 1810   }
 1811 
 1812   sp->check_ok = check_pentomino_puzzle;
 1813 
 1814   return 1;
 1815 }
 1816 
 1817 /*
 1818 
 1819  *
 1820 ***** fills a 24x23 rectangle
 1821 
 1822 */
 1823 
 1824 static struct {int len; point_type point[6];
 1825                int transform_len, transform_list[8], max_white;} hexomino1 =
 1826   {6, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}},
 1827    8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
 1828 
 1829 static
 1830 int set_hexomino_puzzle1(polyominoesstruct *sp) {
 1831   int perm_point[6], perm_transform[8], i, p;
 1832 
 1833   sp->width = 24;
 1834   sp->height =23;
 1835 
 1836   sp->nr_polyominoes = 92;
 1837   set_allocate(sp->polyomino,polyomino_type,92*sizeof(polyomino_type));
 1838   for (p=0;p<92;p++) {
 1839     copy_polyomino(sp->polyomino[p],hexomino1,1);
 1840   }
 1841 
 1842   sp->check_ok = check_hexomino_puzzle;
 1843 
 1844   return 1;
 1845 }
 1846 
 1847 /*
 1848 
 1849  **
 1850 ***** fills a 21x26 rectangle
 1851 
 1852 (All solutions have 180 degree rotational symmetry)
 1853 
 1854 */
 1855 
 1856 static struct {int len; point_type point[7];
 1857                int transform_len, transform_list[8], max_white;} heptomino1 =
 1858   {7, {{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1}, {2,1}},
 1859    8, {0, 1, 2, 3, 4, 5, 6, 7}, 4};
 1860 
 1861 static
 1862 int set_heptomino_puzzle1(polyominoesstruct *sp) {
 1863   int perm_point[7], perm_transform[8], i, p;
 1864 
 1865   sp->rot180 = 1;
 1866 
 1867   sp->width = 26;
 1868   sp->height =21;
 1869 
 1870   sp->nr_polyominoes = 78;
 1871   set_allocate(sp->polyomino,polyomino_type,78*sizeof(polyomino_type));
 1872   for (p=0;p<78;p+=2) {
 1873     copy_polyomino(sp->polyomino[p],heptomino1,1);
 1874     copy_polyomino(sp->polyomino[p+1],heptomino1,0);
 1875   }
 1876 
 1877   sp->check_ok = check_heptomino_puzzle;
 1878 
 1879   return 1;
 1880 }
 1881 
 1882 /* The following puzzles from
 1883 Polyominoes Puzzles, Patterns, Problems, and Packings Revised (2nd) Edition
 1884 by Solomon W. Golomb   Princeton University Press 1994
 1885 */
 1886 
 1887 /*
 1888 
 1889  **
 1890 ***** fills a 28x19 rectangle
 1891 
 1892 */
 1893 static
 1894 int set_heptomino_puzzle2(polyominoesstruct *sp) {
 1895   int perm_point[7], perm_transform[8], i, p;
 1896 
 1897   sp->width = 28;
 1898   sp->height =19;
 1899 
 1900   sp->nr_polyominoes = 76;
 1901   set_allocate(sp->polyomino,polyomino_type,76*sizeof(polyomino_type));
 1902   for (p=0;p<76;p++) {
 1903     copy_polyomino(sp->polyomino[p],heptomino1,1);
 1904   }
 1905 
 1906   sp->check_ok = check_heptomino_puzzle;
 1907 
 1908   return 1;
 1909 }
 1910 
 1911 /*
 1912 
 1913 ***
 1914 **** fills a 25x22 rectangle
 1915 ****
 1916 
 1917 */
 1918 
 1919 static struct {int len; point_type point[11];
 1920                int transform_len, transform_list[8], max_white;} elevenomino1 =
 1921   {11, {{0,0}, {1,0}, {2,0},
 1922         {0,1}, {1,1}, {2,1}, {3,1},
 1923         {0,2}, {1,2}, {2,2}, {3,2}},
 1924    8, {0, 1, 2, 3, 4, 5, 6, 7}, 6};
 1925 
 1926 static
 1927 int set_elevenomino_puzzle1(polyominoesstruct *sp) {
 1928   int perm_point[11], perm_transform[8], i, p;
 1929 
 1930   sp->rot180 = 1;
 1931 
 1932   sp->width = 25;
 1933   sp->height =22;
 1934 
 1935   sp->nr_polyominoes = 50;
 1936   set_allocate(sp->polyomino,polyomino_type,50*sizeof(polyomino_type));
 1937   for (p=0;p<50;p+=2) {
 1938     copy_polyomino(sp->polyomino[p],elevenomino1,1);
 1939     copy_polyomino(sp->polyomino[p+1],elevenomino1,0);
 1940   }
 1941 
 1942   sp->check_ok = check_elevenomino_puzzle;
 1943 
 1944   return 1;
 1945 }
 1946 
 1947 /*
 1948 
 1949  *
 1950  *
 1951 **** fills 32 x 30 rectangle
 1952 ****
 1953 
 1954 */
 1955 
 1956 static struct {int len; point_type point[10];
 1957                int transform_len, transform_list[8], max_white;} dekomino1 =
 1958   {10, {       {1,-1},
 1959                {1,0},
 1960         {0,1}, {1,1}, {2,1}, {3,1},
 1961         {0,2}, {1,2}, {2,2}, {3,2}},
 1962    8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
 1963 
 1964 static
 1965 int set_dekomino_puzzle1(polyominoesstruct *sp) {
 1966   int perm_point[10], perm_transform[8], i, p;
 1967 
 1968   sp->width = 32;
 1969   sp->height =30;
 1970 
 1971   sp->nr_polyominoes = 96;
 1972   set_allocate(sp->polyomino,polyomino_type,96*sizeof(polyomino_type));
 1973   for (p=0;p<96;p++) {
 1974     copy_polyomino(sp->polyomino[p],dekomino1,1);
 1975   }
 1976 
 1977   sp->check_ok = check_dekomino_puzzle;
 1978 
 1979   return 1;
 1980 }
 1981 
 1982 /*
 1983 
 1984  *
 1985 ***  fills 96 x 26 rectangle
 1986 ****
 1987 
 1988 */
 1989 
 1990 static struct {int len; point_type point[10];
 1991                int transform_len, transform_list[8], max_white;} octomino1 =
 1992   {8, {        {1,0},
 1993         {0,1}, {1,1}, {2,1},
 1994         {0,2}, {1,2}, {2,2}, {3,2}},
 1995    8, {0, 1, 2, 3, 4, 5, 6, 7}, 5};
 1996 
 1997 static
 1998 int set_octomino_puzzle1(polyominoesstruct *sp) {
 1999   int perm_point[8], perm_transform[8], i, p;
 2000 
 2001   sp->width = 96;
 2002   sp->height =26;
 2003 
 2004   sp->nr_polyominoes = 312;
 2005   set_allocate(sp->polyomino,polyomino_type,312*sizeof(polyomino_type));
 2006   for (p=0;p<312;p++) {
 2007     copy_polyomino(sp->polyomino[p],octomino1,1);
 2008   }
 2009 
 2010   sp->check_ok = check_octomino_puzzle;
 2011 
 2012   return 1;
 2013 }
 2014 
 2015 /*
 2016 
 2017  *   fills 15 x 15 rectangle
 2018 ****
 2019 
 2020 */
 2021 
 2022 static
 2023 int set_pentomino_puzzle2(polyominoesstruct *sp) {
 2024   int perm_point[5], perm_transform[8], i, p;
 2025 
 2026   sp->width = 15;
 2027   sp->height =15;
 2028 
 2029   sp->nr_polyominoes = 45;
 2030   set_allocate(sp->polyomino,polyomino_type,45*sizeof(polyomino_type));
 2031   for (p=0;p<45;p++) {
 2032     copy_polyomino(sp->polyomino[p],pentomino1,1);
 2033   }
 2034 
 2035   sp->check_ok = check_pentomino_puzzle;
 2036 
 2037   return 1;
 2038 }
 2039 
 2040 /*
 2041 
 2042 ***
 2043 **** fills a 47x33 rectangle
 2044 ****
 2045 
 2046 */
 2047 
 2048 static
 2049 int set_elevenomino_puzzle2(polyominoesstruct *sp) {
 2050   int perm_point[11], perm_transform[8], i, p;
 2051 
 2052   sp->width = 47;
 2053   sp->height =33;
 2054 
 2055   sp->nr_polyominoes = 141;
 2056   set_allocate(sp->polyomino,polyomino_type,141*sizeof(polyomino_type));
 2057   for (p=0;p<141;p++) {
 2058     copy_polyomino(sp->polyomino[p],elevenomino1,1);
 2059   }
 2060 
 2061   sp->check_ok = check_elevenomino_puzzle;
 2062 
 2063   return 1;
 2064 }
 2065 
 2066 /**************************************************
 2067 The main functions.
 2068 **************************************************/
 2069 
 2070 #define allocate(p,type,size) p = (type *) malloc(size); if ((p)==NULL) {free_polyominoes_screen(sp); return;}
 2071 
 2072 ENTRYPOINT void
 2073 init_polyominoes(ModeInfo * mi) {
 2074   polyominoesstruct *sp;
 2075   int i,x,y, start;
 2076   int box1, box2;
 2077   int *perm;
 2078 
 2079   MI_INIT(mi, polyominoeses);
 2080   sp = &polyominoeses[MI_SCREEN(mi)];
 2081 
 2082   free_polyominoes_screen(sp);
 2083 
 2084   sp->rot180 = 0;
 2085   sp->counter = 0;
 2086 
 2087   if (MI_IS_FULLRANDOM(mi)) {
 2088     sp->identical = (Bool) (LRAND() & 1);
 2089     sp->use3D = (Bool) (NRAND(4));
 2090   } else {
 2091     sp->identical = identical;
 2092     sp->use3D = !plain;
 2093   }
 2094   if (sp->identical) {
 2095     switch (NRAND(9)) {
 2096       case 0:
 2097         if (!set_pentomino_puzzle1(sp))
 2098           return;
 2099         break;
 2100       case 1:
 2101         if (!set_hexomino_puzzle1(sp))
 2102           return;
 2103         break;
 2104       case 2:
 2105         if (!set_heptomino_puzzle1(sp))
 2106           return;
 2107         break;
 2108       case 3:
 2109         if (!set_heptomino_puzzle2(sp))
 2110           return;
 2111         break;
 2112       case 4:
 2113         if (!set_elevenomino_puzzle1(sp))
 2114           return;
 2115         break;
 2116       case 5:
 2117         if (!set_dekomino_puzzle1(sp))
 2118           return;
 2119         break;
 2120       case 6:
 2121         if (!set_octomino_puzzle1(sp))
 2122           return;
 2123         break;
 2124       case 7:
 2125         if (!set_pentomino_puzzle2(sp))
 2126           return;
 2127         break;
 2128       case 8:
 2129         if (!set_elevenomino_puzzle2(sp))
 2130           return;
 2131         break;
 2132     }
 2133   } else {
 2134     switch (NRAND(5)) {
 2135       case 0:
 2136         if (!set_pentomino_puzzle(sp))
 2137           return;
 2138         break;
 2139       case 1:
 2140         if (!set_one_sided_pentomino_puzzle(sp))
 2141           return;
 2142         break;
 2143       case 2:
 2144         if (!set_one_sided_hexomino_puzzle(sp))
 2145           return;
 2146         break;
 2147       case 3:
 2148         if (!set_pent_hexomino_puzzle(sp))
 2149           return;
 2150         break;
 2151       case 4:
 2152         if (!set_tetr_pentomino_puzzle(sp))
 2153           return;
 2154         break;
 2155     }
 2156   }
 2157 
 2158   allocate(sp->attach_list,int,sp->nr_polyominoes*sizeof(int));
 2159   sp->nr_attached = 0;
 2160 
 2161   if (sp->identical) {
 2162     allocate(sp->reason_to_not_attach,int,sp->nr_polyominoes*sp->nr_polyominoes*sizeof(int));
 2163   }
 2164 
 2165   allocate(sp->array,int,sp->width*sp->height*sizeof(int));
 2166   allocate(sp->changed_array,int,sp->width*sp->height*sizeof(int));
 2167   for (x=0;x<sp->width;x++) for (y=0;y<sp->height;y++) ARRAY(x,y) = -1;
 2168 
 2169   sp->left_right = NRAND(2);
 2170   sp->top_bottom = NRAND(2);
 2171 
 2172   box1 = MI_WIDTH(mi)/(sp->width+2);
 2173   box2 = MI_HEIGHT(mi)/(sp->height+2);
 2174   if (box1<box2)
 2175     sp->box = box1;
 2176   else
 2177     sp->box = box2;
 2178   if (sp->box >= 12) {
 2179     sp->box = (sp->box/12)*12;
 2180     create_bitmaps(mi,sp);
 2181     if (!sp->use_bitmaps)
 2182       free_bitmaps(sp);
 2183    } else
 2184      sp->use_bitmaps = 0;
 2185 
 2186   if (!sp->use_bitmaps) {
 2187     allocate(sp->rectangles,XRectangle,sp->width*sp->height*sizeof(XRectangle));
 2188     allocate(sp->lines,XSegment,sp->width*sp->height*sizeof(XSegment));
 2189   }
 2190 
 2191   allocate(perm,int,sp->nr_polyominoes*sizeof(int));
 2192   random_permutation(sp->nr_polyominoes, perm);
 2193   sp->mono = MI_NPIXELS(mi) < 12;
 2194   start = NRAND(MI_NPIXELS(mi));
 2195   for (i=0;i<sp->nr_polyominoes;i++)
 2196     if (!sp->mono) {
 2197       sp->polyomino[i].color = MI_PIXEL(mi,(perm[i]*MI_NPIXELS(mi) / sp->nr_polyominoes + start) % MI_NPIXELS(mi));
 2198       if (sp->rot180) {
 2199          sp->polyomino[i+1].color = sp->polyomino[i].color;
 2200          i++;
 2201       }
 2202     }
 2203     else
 2204       if(sp->use_bitmaps)
 2205         sp->polyomino[i].color = MI_WHITE_PIXEL(mi);
 2206       else
 2207         sp->polyomino[i].color = MI_BLACK_PIXEL(mi);
 2208   free(perm);
 2209 
 2210   if (sp->use_bitmaps) {
 2211     if (sp->mono)
 2212       sp->border_color = MI_WHITE_PIXEL(mi);
 2213     else
 2214       sp->border_color = MI_PIXEL(mi,NRAND(MI_NPIXELS(mi)));
 2215   }
 2216 
 2217   sp->x_margin = (MI_WIDTH(mi)-sp->box*sp->width)/2;
 2218   sp->y_margin = (MI_HEIGHT(mi)-sp->box*sp->height)/2;
 2219 
 2220   sp->wait = 0;
 2221 
 2222   /* Clear the background. */
 2223   MI_CLEARWINDOW(mi);
 2224 
 2225 }
 2226 
 2227 ENTRYPOINT void
 2228 draw_polyominoes(ModeInfo * mi) {
 2229   polyominoesstruct *sp;
 2230   int poly_no,point_no,transform_index,done,another_attachment_try;
 2231   point_type attach_point;
 2232   int i,detach_until;
 2233 
 2234   if (polyominoeses == NULL)
 2235     return;
 2236   sp = &polyominoeses[MI_SCREEN(mi)];
 2237 
 2238   if (MI_CYCLES(mi) != 0) {
 2239     if (++sp->counter > MI_CYCLES(mi)) {
 2240       init_polyominoes(mi);
 2241       return;
 2242     }
 2243   }
 2244 
 2245   if (sp->box == 0) {
 2246     init_polyominoes(mi);
 2247     return;
 2248   }
 2249 
 2250   MI_IS_DRAWN(mi) = True;
 2251   sp->wait--;
 2252   if (sp->wait>0) return;
 2253 
 2254   (void) memset(sp->changed_array,0,sp->width*sp->height*sizeof(int));
 2255 
 2256   poly_no = first_poly_no(sp);
 2257   point_no = 0;
 2258   transform_index = 0;
 2259   done = 0;
 2260   another_attachment_try = 1;
 2261   find_blank(sp,&attach_point);
 2262   if (sp->identical && sp->nr_attached < sp->nr_polyominoes)
 2263     (void) memset(&REASON_TO_NOT_ATTACH(sp->nr_attached,0),0,sp->nr_polyominoes*sizeof(int));
 2264   while(!done) {
 2265     if (sp->nr_attached < sp->nr_polyominoes) {
 2266       while (!done && another_attachment_try) {
 2267         done = attach(sp,poly_no,point_no,transform_index,attach_point,0,&REASON_TO_NOT_ATTACH(sp->nr_attached,0));
 2268         if (done && sp->rot180) {
 2269           poly_no = first_poly_no(sp);
 2270           done = attach(sp,poly_no,point_no,transform_index,attach_point,1,&REASON_TO_NOT_ATTACH(sp->nr_attached-1,0));
 2271           if (!done)
 2272             detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
 2273         }
 2274         if (!done)
 2275           another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
 2276       }
 2277     }
 2278 
 2279     if (sp->identical) {
 2280       if (!done) {
 2281         if (sp->nr_attached == 0)
 2282           done = 1;
 2283         else {
 2284           detach_until=sp->nr_attached-1;
 2285           if (sp->nr_attached < sp->nr_polyominoes)
 2286             while (detach_until>0 && REASON_TO_NOT_ATTACH(sp->nr_attached,detach_until)==0)
 2287               detach_until--;
 2288           while (sp->nr_attached>detach_until) {
 2289             if (sp->rot180)
 2290               detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
 2291             detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
 2292             if (sp->nr_attached+1+sp->rot180 < sp->nr_polyominoes)
 2293               for (i=0;i<sp->nr_polyominoes;i++)
 2294                 REASON_TO_NOT_ATTACH(sp->nr_attached,i) |= REASON_TO_NOT_ATTACH(sp->nr_attached+1+sp->rot180,i);
 2295           }
 2296           another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
 2297         }
 2298       }
 2299     }
 2300     else {
 2301       if (!done) {
 2302         if (sp->nr_attached == 0)
 2303           done = 1;
 2304         else {
 2305           if (sp->rot180)
 2306             detach(sp,&poly_no,&point_no,&transform_index,&attach_point,1);
 2307           detach(sp,&poly_no,&point_no,&transform_index,&attach_point,0);
 2308         }
 2309         another_attachment_try = next_attach_try(sp,&poly_no,&point_no,&transform_index);
 2310       }
 2311     }
 2312   }
 2313 
 2314   if (sp->use_bitmaps)
 2315     draw_with_bitmaps(mi,sp);
 2316   else
 2317     draw_without_bitmaps(mi,sp);
 2318 
 2319   if (sp->nr_attached == sp->nr_polyominoes)
 2320     sp->wait = 500;
 2321   else
 2322     sp->wait = 0;
 2323 }
 2324 
 2325 ENTRYPOINT void
 2326 release_polyominoes(ModeInfo * mi) {
 2327   int screen;
 2328 
 2329   if (polyominoeses != NULL) {
 2330     for (screen=0;screen<MI_NUM_SCREENS(mi); screen++)
 2331       free_polyominoes_screen(&polyominoeses[screen]);
 2332     free(polyominoeses);
 2333     polyominoeses = (polyominoesstruct *) NULL;
 2334   }
 2335 }
 2336 
 2337 #ifndef STANDALONE
 2338 void
 2339 refresh_polyominoes(ModeInfo * mi) {
 2340   MI_CLEARWINDOW(mi);
 2341 }
 2342 #endif
 2343 
 2344 XSCREENSAVER_MODULE ("Polyominoes", polyominoes)
 2345 
 2346 #endif /* MODE_polyominoes */