/* PENTO3.C */ /* 12-pentomino puzzle solver */ /* J.W.Stumpel, 1989 - 1997 */ /* version which uses long long (64 bit) integers (for gcc) */ #include #include #include #include #include /* flags to be OR-ed if pentomino is not to be placed in certain corners of the box. We want to restrict the search space as much as possible for speed */ #define NO_TOP_RIGHT 1 #define NO_TOP_LEFT 2 #define NO_BTM_RIGHT 4 #define NO_BTM_LEFT 8 /* search directions for the "flood" function */ #define UP 1 #define DOWN 2 #define LEFT 3 #define RIGHT 4 /* Console graphics characters, defined for PC-DOS and VT-100 */ #ifdef __MSDOS__ unsigned char GCHAR[11] = {217, 191, 218, 192, 197, 196, 195, 180, 193, 194, 179}; #else unsigned char GCHAR[11] = {106, 107, 108, 109, 110, 113, 116, 117, 118, 119, 120}; #endif typedef struct { int height; int width; int pattern[5]; /* bit-pattern indicating the shape of the pentomino in this orientation */ int flags; /* to indicate forbidden corners */ } olist; /* Description of the pentominoes (in all their possible orientations) */ olist V_pentomino[] = { {3, 3, { 1, 1, 7, 0, 0}, NO_TOP_LEFT }, {3, 3, { 4, 4, 7, 0, 0}, NO_TOP_RIGHT }, {3, 3, { 7, 1, 1, 0, 0}, NO_BTM_LEFT }, {3, 3, { 7, 4, 4, 0, 0}, NO_BTM_RIGHT }}; olist Z_pentomino[] = { {3, 3, { 4, 7, 1, 0, 0}, NO_TOP_RIGHT | NO_BTM_LEFT }, {3, 3, { 6, 2, 3, 0, 0}, NO_TOP_RIGHT | NO_BTM_LEFT }, {3, 3, { 1, 7, 4, 0, 0}, NO_TOP_LEFT | NO_BTM_RIGHT }, {3, 3, { 3, 2, 6, 0, 0}, NO_TOP_LEFT | NO_BTM_RIGHT }}; olist I_pentomino[] = { {1, 5, { 31, 0, 0, 0, 0}, 0}, {5, 1, { 1, 1, 1, 1, 1}, 0}}; olist X_pentomino[] = { {5, 7, { 2, 7, 2, 0, 0}, NO_TOP_RIGHT}}; /* The X_pentomino's height is put at 5 and its width at 7. This restricts the position of its center square to the top-right quadrant of the box, (top-left when displayed) and thereby ensures that reflections and rotations of the whole box are excluded from the solution set. */ olist U_pentomino[] = { {3, 3, { 3, 1, 3, 0, 0}, 0}, {3, 3, { 6, 4, 6, 0, 0}, 0}, {3, 3, { 0, 5, 7, 0, 0}, 0}, {3, 3, { 7, 5, 0, 0, 0}, 0}}; /* The U_pentomino's parameters are defined so as to ensure that the open end of the U is never placed directly against the side of the box. */ olist W_pentomino[] = { {3, 3, { 3, 6, 4, 0, 0}, NO_TOP_LEFT | NO_BTM_RIGHT }, {3, 3, { 6, 3, 1, 0, 0}, NO_TOP_RIGHT | NO_BTM_LEFT }, {3, 3, { 1, 3, 6, 0, 0}, NO_TOP_LEFT | NO_BTM_RIGHT }, {3, 3, { 4, 6, 3, 0, 0}, NO_TOP_RIGHT | NO_BTM_LEFT }}; olist N_pentomino[] = { {2, 4, { 7, 12, 0, 0, 0}, NO_TOP_LEFT | NO_BTM_RIGHT }, {2, 4, { 3, 14, 0, 0, 0}, NO_TOP_LEFT | NO_BTM_RIGHT }, {4, 2, { 1, 3, 2, 2, 0}, NO_TOP_LEFT | NO_BTM_RIGHT }, {2, 4, { 14, 3, 0, 0, 0}, NO_TOP_RIGHT | NO_BTM_LEFT }, {4, 2, { 1, 1, 3, 2, 0}, NO_TOP_LEFT | NO_BTM_RIGHT }, {2, 4, { 12, 7, 0, 0, 0}, NO_TOP_RIGHT | NO_BTM_LEFT }, {4, 2, { 2, 3, 1, 1, 0}, NO_TOP_RIGHT | NO_BTM_LEFT }, {4, 2, { 2, 2, 3, 1, 0}, NO_TOP_RIGHT | NO_BTM_LEFT }}; olist T_pentomino[] = { {3, 3, { 7, 2, 2, 0, 0}, NO_BTM_RIGHT | NO_BTM_LEFT }, {3, 3, { 1, 7, 1, 0, 0}, NO_TOP_LEFT | NO_BTM_LEFT }, {3, 3, { 2, 2, 7, 0, 0}, NO_TOP_RIGHT | NO_TOP_LEFT }, {3, 3, { 4, 7, 4, 0, 0}, NO_TOP_RIGHT | NO_BTM_RIGHT }}; olist F_pentomino[] = { {3, 3, { 2, 7, 4, 0, 0}, NO_TOP_RIGHT | NO_TOP_LEFT | NO_BTM_RIGHT }, {3, 3, { 2, 6, 3, 0, 0}, NO_TOP_RIGHT | NO_TOP_LEFT | NO_BTM_LEFT }, {3, 3, { 3, 6, 2, 0, 0}, NO_TOP_LEFT | NO_BTM_LEFT | NO_BTM_RIGHT }, {3, 3, { 2, 7, 1, 0, 0}, NO_TOP_RIGHT | NO_TOP_LEFT | NO_BTM_LEFT }, {3, 3, { 2, 3, 6, 0, 0}, NO_TOP_RIGHT | NO_TOP_LEFT | NO_BTM_RIGHT }, {3, 3, { 4, 7, 2, 0, 0}, NO_TOP_RIGHT | NO_BTM_LEFT | NO_BTM_RIGHT }, {3, 3, { 6, 3, 2, 0, 0}, NO_TOP_RIGHT | NO_BTM_LEFT | NO_BTM_RIGHT }, {3, 3, { 1, 7, 2, 0, 0}, NO_TOP_LEFT | NO_BTM_LEFT | NO_BTM_RIGHT }}; olist P_pentomino[] = { {3, 2, { 3, 3, 2, 0, 0}, NO_BTM_RIGHT }, {2, 3, { 7, 3, 0, 0, 0}, NO_BTM_LEFT }, {3, 2, { 1, 3, 3, 0, 0}, NO_TOP_LEFT }, {2, 3, { 6, 7, 0, 0, 0}, NO_TOP_RIGHT }, {3, 2, { 3, 3, 1, 0, 0}, NO_BTM_LEFT }, {2, 3, { 3, 7, 0, 0, 0}, NO_TOP_LEFT }, {3, 2, { 2, 3, 3, 0, 0}, NO_TOP_RIGHT }, {2, 3, { 7, 6, 0, 0, 0}, NO_BTM_RIGHT }}; olist L_pentomino[] = { {2, 4, { 15, 8, 0, 0, 0}, NO_BTM_RIGHT }, {2, 4, { 1, 15, 0, 0, 0}, NO_TOP_LEFT }, {4, 2, { 3, 2, 2, 2, 0}, NO_BTM_RIGHT }, {2, 4, { 15, 1, 0, 0, 0}, NO_BTM_LEFT }, {4, 2, { 1, 1, 1, 3, 0}, NO_TOP_LEFT }, {2, 4, { 8, 15, 0, 0, 0}, NO_TOP_RIGHT }, {4, 2, { 3, 1, 1, 1, 0}, NO_BTM_LEFT }, {4, 2, { 2, 2, 2, 3, 0}, NO_TOP_RIGHT }}; olist Y_pentomino[] = { {2, 4, { 15, 2, 0, 0, 0}, NO_BTM_RIGHT | NO_BTM_LEFT }, {4, 2, { 1, 1, 3, 1, 0}, NO_TOP_LEFT | NO_BTM_LEFT }, {2, 4, { 4, 15, 0, 0, 0}, NO_TOP_RIGHT | NO_TOP_LEFT }, {4, 2, { 1, 3, 1, 1, 0}, NO_TOP_LEFT | NO_BTM_LEFT }, {2, 4, { 2, 15, 0, 0, 0}, NO_TOP_RIGHT | NO_TOP_LEFT }, {4, 2, { 2, 2, 3, 2, 0}, NO_TOP_RIGHT | NO_BTM_RIGHT }, {2, 4, { 15, 4, 0, 0, 0}, NO_BTM_RIGHT | NO_BTM_LEFT }, {4, 2, { 2, 3, 2, 2, 0}, NO_TOP_RIGHT | NO_BTM_RIGHT }}; typedef struct { olist *orient; /* list of patterns (for various orientations) */ char name; /* for comment purposes, debugging, etc. */ int N; /* number of orientations of this pentomino */ int M; /* number of positions of pentomino in the box */ long long *pat; /* list of bitmaps for each position */ int pos; /* the chosen position (on output) */ int done; /* flag; nonzero if done */ } pentomino; pentomino P [12] = { {X_pentomino, 'X', 1, 0, NULL, 0, 0}, {I_pentomino, 'I', 2, 0, NULL, 0, 0}, {T_pentomino, 'T', 4, 0, NULL, 0, 0}, {W_pentomino, 'W', 4, 0, NULL, 0, 0}, {Z_pentomino, 'Z', 4, 0, NULL, 0, 0}, {V_pentomino, 'V', 4, 0, NULL, 0, 0}, {U_pentomino, 'U', 4, 0, NULL, 0, 0}, {Y_pentomino, 'Y', 8, 0, NULL, 0, 0}, {F_pentomino, 'F', 8, 0, NULL, 0, 0}, {N_pentomino, 'N', 8, 0, NULL, 0, 0}, {L_pentomino, 'L', 8, 0, NULL, 0, 0}, {P_pentomino, 'P', 8, 0, NULL, 0, 0}}; #define BOXHEIGHT 6 #define BOXWIDTH 10 int plus = 0; long long box = 0; int WIDE = 5; int numsols = 0; time_t inittime, newtime; int mycomp (const long long *a, const long long *b) { long long c = *a - *b; if (c > 0) return 1; if (c < 0) return -1; return 0; } void prepare_pentominoes (void) { /* Create, for each pentomino, an array of long long numbers, corresponding to the bit-pattern when a pentomino is placed anywhere in the box. We assume that a long long number has 60 bits or more (if this is not the case on your system you are out of luck). This is enough to represent the box of 10 x 6 squares into which we are going to fit our pentominoes. Occupied squares are 1, empty ones are 0. Bits 0-9 represent the first row of 10 squares, bits 10-19 the second, etc. Patterns are then sorted for easy retrieval. */ int f, maxhor, maxvert, i, j, k, m, n, M; long long x, *q; for (i = 0; i < 12; i++) { M = 0; for (j = 0; j < P[i].N; j++) { maxhor = BOXWIDTH - P[i].orient[j].width; maxvert = BOXHEIGHT - P[i].orient[j].height; f = P[i].orient[j].flags; M += (maxhor + 1) * (maxvert + 1) - ((f & NO_TOP_RIGHT) != 0) - ((f & NO_TOP_LEFT) != 0) - ((f & NO_BTM_RIGHT) != 0) - ((f & NO_BTM_LEFT) != 0); } P[i].pat = (long long *) malloc (M * sizeof (long long)); if (P[i].pat == NULL) { fprintf (stderr, "pento: not enough memory!\n"); exit (1); } P[i].M = M; q = P[i].pat; for (j = 0; j < P[i].N; j++) { x = 0; for (k = 0; k < 5; k++) x += (long long) P[i].orient[j].pattern[k] << k * BOXWIDTH; maxvert = BOXHEIGHT - P[i].orient[j].height; maxhor = BOXWIDTH - P[i].orient[j].width; f = P[i].orient[j].flags; for (m = 0; m <= maxhor; m++) /* horizontal shift */ for (n = 0; n <= maxvert; n++) /* vertical shift */ { if ((m == 0) && (n == 0) && (f & NO_TOP_RIGHT)) continue; if ((m == maxhor ) && (n == 0) && (f & NO_TOP_LEFT)) continue; if ((m == 0) && (n == maxvert) && (f & NO_BTM_RIGHT)) continue; if ((m == maxhor) && (n == maxvert) && (f & NO_BTM_LEFT)) continue; *q++ = x << (BOXWIDTH * n + m); } } qsort (P[i].pat, P[i].M, sizeof (long long), (__compar_fn_t) mycomp); } } void makepic (int *status, int S) /* Displays a solution by means of "box draw" characters. */ { static char frame[13][92]; static int tens = 0; static char odd = 1; unsigned char *line[13]; int i, j, n, linend, shift; for (j = 0; j < 13; j++) line[j] = &frame [j][0]; tens++; if (WIDE >= 4) { linend = BOXWIDTH * WIDE + 1; shift = 0; } else { linend = 20 * WIDE + 14; if (odd) shift = 0; else { shift = BOXWIDTH * WIDE + BOXWIDTH; for (j = 0; j < 13; j++) for (i = BOXWIDTH * WIDE + 1; i < BOXWIDTH * WIDE + 15; i++) *(line[j] + i) = 32; } } *(line[0] + shift) = GCHAR[2]; for (i = 1; i < (BOXWIDTH * WIDE); i++) *(line[0] + shift + i) = GCHAR[5]; *(line[0] + shift + BOXWIDTH * WIDE) = GCHAR[1]; *(line[0] + linend) = 0; for (j = 1; j < 12; j++) { *(line[j] + shift) = GCHAR[10]; for (i = 1; i < (BOXWIDTH * WIDE); i++) *(line[j] + shift + i) = 32; *(line[j] + shift + BOXWIDTH * WIDE) = GCHAR[10]; *(line[j] + linend) = 0; } *(line[12] + shift) = GCHAR[3]; for (i = 1; i < (BOXWIDTH * WIDE); i++) *(line[12] + shift + i) = GCHAR[5]; *(line[12] + shift + BOXWIDTH * WIDE) = GCHAR[0]; *(line[12] + linend) = 0; for (j = 1; j < BOXWIDTH; j++) { if (status[j] != status[j - 1]) *(line[0] + shift + WIDE * j) = GCHAR[9]; if (status[50 + j] != status[50 + j - 1]) *(line[12] + shift + WIDE * j) = GCHAR[8]; } for (j = 1; j < BOXHEIGHT; j++) { if (status[BOXWIDTH * j] != status[BOXWIDTH * (j - 1)]) *(line[2 * j] + shift) = GCHAR[6]; if (status[BOXWIDTH * j + BOXWIDTH - 1] != status[BOXWIDTH * (j - 1) + BOXWIDTH - 1]) *(line[2 * j] + shift + BOXWIDTH * WIDE) = GCHAR[7]; } for (j = 0; j < BOXHEIGHT; j++) for (i = 1; i < BOXWIDTH; i++) if (status[BOXWIDTH * j + i] != status[BOXWIDTH * j + i - 1]) *(line[2 * j + 1] + shift + WIDE * i) = GCHAR[10]; for (j = 0; j < BOXHEIGHT - 1; j++) for (i = 1; i < BOXWIDTH; i++) { int A = status[BOXWIDTH * j + i - 1], B = status[BOXWIDTH * j + i], C = status[BOXWIDTH * (j + 1) + i - 1], D = status[BOXWIDTH * (j + 1) + i]; char k = ' '; switch (8 * (A == B) + 4 * (C == D) + 2 * (A == C) + (B == D)) { case 0: k = GCHAR[4]; break; case 1: k = GCHAR[7]; break; case 2: k = GCHAR[6]; break; case 3: k = GCHAR[10]; break; case 4: k = GCHAR[8]; break; case 5: k = GCHAR[0]; break; case 6: k = GCHAR[3]; break; case 7: k = ' '; break; case 8: k = GCHAR[9]; break; case 9: k = GCHAR[1]; break; case 10: k = GCHAR[2]; break; case 11: k = ' '; break; case 12: k = GCHAR[5]; break; case 13: k = ' '; break; case 14: k = ' '; break; case 15: k = ' '; break; } *(line[2 * (j + 1)] + shift + WIDE * i) = k; } for (j = 0; j < BOXHEIGHT - 1; j++) for (i = 0; i < BOXWIDTH; i++) if (status[BOXWIDTH * j + i] != status[BOXWIDTH * (j + 1) + i]) for (n = (1 + WIDE * i); n < (1 + i) * WIDE; n++) *(line[2 * (j + 1)] + shift + n) = GCHAR[5]; #ifndef __MSDOS__ printf ("\033(0"); #endif if ((WIDE >= 4) || (!odd)) for (j = 0; j <= 12; j++) puts (line[j]); #ifndef __MSDOS__ printf ("\033(B"); #endif if (WIDE >= 4) printf (" solution nr.%5d \n\n", S); else if (!odd) { printf (" solution nr.%5d " "solution nr.%5d\n\n", S - 1, S); if (tens == BOXWIDTH) { putchar (12); /* Form Feed */ tens = 0; } } odd = !odd; } void showbox (int S) /* Prepare display of a solution */ { int j, p, status[60]; long long x; /* First construct an array of 6 x 10 squares, with a "0" in the squares belonging to pentomino 0, a "1" in 1's squares, etc. */ for (p = 0; p < 12; p++) { x = P[p].pat[P[p].pos]; for (j = 0; j < 60; j++) { if (x & 1) status[j] = p; x >>= 1; } } makepic (status, S); } int findshape (int *status, int type) /* 5 connected squares in the array "status" contain integer "type". The question is: which pentomino is formed by these squares? Done by binary search (from sorted lists). */ { long long t = 0, *f; int j, p; for (j = 59; j >=0; j--) { t <<= 1; if (status [j] == type) t |= 1; } for (p = 0; p < 12; p++) { if (! P[p].done) { f = bsearch (&t, P[p].pat, P[p].M, sizeof (long long), (__compar_fn_t) mycomp); if (f) { P[p].done = 1; P[p].pos = f - P[p].pat; box |= t; plus++; return 1; } } } /*for (p = 0; p < 12; p++) { if (! P[p].done) for (j = 0; j < P[p].M; j++) { if (t == P[p].pat[j]) { P[p].done = 1; P[p].pos = j; box |= t; plus++; return 1; } } }*/ return 0; } int flood (int start, int type, int *status, int direction) /* starting from a empty square, count all adjacent empty squares recursively. */ { int x, y, result = 1; if (status [start]) return 0; x = start % BOXWIDTH; y = start / BOXWIDTH; status [start] = type; /* Try all neighbouring squares (apart from the one we just came from) */ if ((direction != RIGHT) && (x > 0)) result += flood (start - 1, type, status, LEFT); if ((direction != LEFT) && (x < BOXWIDTH - 1)) result += flood (start + 1, type, status, RIGHT); if ((direction != DOWN) && (y > 0)) result += flood (start - BOXWIDTH, type, status, UP); if ((direction != UP) && (y < BOXHEIGHT - 1)) result += flood (start + BOXWIDTH, type, status, DOWN); return result; } int check5 (int p) /* checks if putting a piece in the box does not leave empty regions of area != 0 (mod 5). If an area of size exactly 5 is found, it must have the shape of an unused pentomino. */ { int count = 0, remaining = 55 - 5 * (p + plus); int type = 1, start = 0, status[60], j; long long mybox = box; /* construct array "status" from "box": -1 for "occupied", 0 for "free": */ for (j = 0; j < 60; j++) { status [j] = - (mybox & 1); mybox >>= 1; } while (1) { start = 0; while (status [start]) start++; /* find an empty square */ count = flood (start, type, status, RIGHT); if (count % 5) return 0; if ((p < BOXWIDTH) && (count == 5) && (!findshape (status, type))) return 0; remaining -= count; if (!remaining) break; type ++; } return 1; } void print_solution (void) { int i, j; long long k; char tin [60]; for (i = 0; i < 60; i++) tin [i] = '-'; for (i = 0; i < 12 ; i++) { k = P[i].pat[P[i].pos]; if (P[i].done) for (j = 0; j < 60 ; j++) { if (k & 1) tin[j] = P[i].name; k >>=1; } } for (i = 0; i < 6; i++) { for (j = 0; j < 10; j++) printf ("%c ", tin [j + 10 * i]); printf ("\n"); } printf ("\n"); } void show_solution(void) { time_t hours, mins, secs, eltime; time (&newtime); fprintf (stderr, "Solution nr. %4d found.", numsols); eltime = newtime - inittime; hours = eltime/3600 ; eltime -= 3600 * hours; mins = eltime/60 ; secs = eltime - 60 * mins; fprintf (stderr, " Elapsed time:%3ldh %2ldm %2lds\n", hours, mins, secs); showbox (numsols); } void fit (int p) { /* p is the number of the pentomino (0 - 11) which this recursive procedure tries to fit. If p == 12, we have a solution. At the end of the routine with p == 0, we have all solutions. */ int i, j; long long mybox; int myplus; int myflags[12]; /*print_solution(); getchar();*/ if (p == 12) { numsols++; show_solution(); return; } if (P[p].done) { plus--; fit (p + 1); return; } mybox = box; myplus = plus; for (i = p; i < 12; i++) myflags[i] = P[i].done; for (j = 0; j < P[p].M; j++) { if (box & P[p].pat[j]) /* piece doesn't fit */ continue; P[p].done = 1; box |= P[p].pat[j]; /* put piece in box */ P[p].pos = j; if ((p >= 10) || (check5 (p))) fit (p + 1); /* try next piece */ box = mybox; plus = myplus; for (i = p; i < 12; i++) P[i].done = myflags[i]; } } void main(int argc, char *argv[]) { if ((argc == 2) && (*argv[1] == '/') && (*(argv[1] + 1) > 48) && (*(argv[1] + 1) < 58)) WIDE = *(argv[1] + 1) - 48; else WIDE = 5; prepare_pentominoes(); time (&inittime); fprintf (stderr, "\nPentomino Puzzle Solver, (C) J.W. Stumpel, 1997\n"); fprintf (stderr, "Calculating... please wait\n"); fit (0); if ((WIDE < 4) && (numsols & 1)) showbox (numsols + 1); fprintf (stderr, "\nREADY!! All solutions found."); if ((WIDE < 4) && (numsols & 1)) { fprintf (stderr, "\nLast valid solution was nr. %d", numsols); fprintf (stderr, "\nPlease disregard printout of nr. %d", numsols + 1); } }