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