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