* or for generating the playfield for Jigsaw Sudoku.
*/
+/*
+ * This code is restricted to simply connected solutions: that is,
+ * no single polyomino may completely surround another (not even
+ * with a corner visible to the outside world, in the sense that a
+ * 7-omino can `surround' a single square).
+ *
+ * It's tempting to think that this is a natural consequence of
+ * all the ominoes being the same size - after all, a division of
+ * anything into 7-ominoes must necessarily have all of them
+ * simply connected, because if one was not then the 1-square
+ * space in the middle could not be part of any 7-omino - but in
+ * fact, for sufficiently large k, it is perfectly possible for a
+ * k-omino to completely surround another k-omino. A simple
+ * example is this one with two 25-ominoes:
+ *
+ * +--+--+--+--+--+--+--+
+ * | |
+ * + +--+--+--+--+--+ +
+ * | | | |
+ * + + + +
+ * | | | |
+ * + + + +--+
+ * | | | |
+ * + + + +--+
+ * | | | |
+ * + + + +
+ * | | | |
+ * + +--+--+--+--+--+ +
+ * | |
+ * +--+--+--+--+--+--+--+
+ *
+ * I believe the smallest k which can manage this is 23, which I
+ * derive by considering the largest _rectangle_ a k-omino can
+ * surround. Consider: to surround an m x n rectangle, a polyomino
+ * must have 2m squares along the two m-sides of the rectangle, 2n
+ * squares along the n-sides, and fill in three of the corners. So
+ * m+n must be at most (k-3)/2. Hence, to find the largest area of
+ * such a rectangle, we must find m so as to maximise the product
+ * m((k-3)/2-m). This is achieved when m is as close as possible
+ * to half of (k-3)/2; so the largest rectangle surroundable by a
+ * k-omino is equal to floor(k'/2)*ceil(k'/2), with k'=(k-3)/2.
+ * The smallest k for which this is at least k is 23: a 23-omino
+ * can surround a 5x5 rectangle, whereas the best a 22-omino can
+ * manage is a 5x4.
+ *
+ * (I don't have a definite argument to show that a k-omino cannot
+ * surround a larger area in non-rectangular than rectangular
+ * form, but it seems intuitively obvious to me that it can't. I
+ * may update this with a more rigorous proof if I think of one.)
+ *
+ * Anyway: the point is, although constructions of this type are
+ * possible for sufficiently large k, divvy_rectangle() will never
+ * generate them. This could be considered a weakness for some
+ * purposes, in the sense that we can't generate all possible
+ * divisions. However, there are many divisions which we are
+ * highly unlikely to generate anyway, so in practice it probably
+ * isn't _too_ bad.
+ *
+ * If I wanted to fix this issue, I would have to make the rules
+ * more complicated for determining when a square can safely be
+ * _removed_ from a polyomino. Adding one becomes easier (a square
+ * may be added to a polyomino iff it is 4-adjacent to any square
+ * currently part of the polyomino, and the current test for loop
+ * formation may be dispensed with), but to determine which
+ * squares may be removed we must now resort to analysis of the
+ * overall structure of the polyomino rather than the simple local
+ * properties we can currently get away with measuring.
+ */
+
+/*
+ * Possible improvements which might cut the fail rate:
+ *
+ * - instead of picking one omino to extend in an iteration, try
+ * them all in succession (in a randomised order)
+ *
+ * - (for real rigour) instead of bfsing over ominoes, bfs over
+ * the space of possible _removed squares_. That way we aren't
+ * limited to randomly choosing a single square to remove from
+ * an omino and failing if that particular square doesn't
+ * happen to work.
+ *
+ * However, I don't currently think it's necessary to do either of
+ * these, because the failure rate is already low enough to be
+ * easily tolerable, under all circumstances I've been able to
+ * think of.
+ */
+
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
*
* When adding a square to an omino, this is precisely the
* criterion which tells us that adding the square won't leave a
- * hole in the middle of the omino. (There's no explicit
- * requirement in the statement of our problem that the ominoes be
- * simply connected, but we do know they must be all of equal size
- * and so it's clear that we must avoid leaving holes, since a
- * hole would necessarily be smaller than the maximum omino size.)
+ * hole in the middle of the omino. (If it did, then things get
+ * more complicated; see above.)
*
* When removing a square from an omino, the _same_ criterion
* tells us that removing the square won't disconnect the omino.
+ * (This only works _because_ we've ensured the omino is simply
+ * connected.)
*/
static int addremcommon(int w, int h, int x, int y, int *own, int val)
{
* In both of the above suggested use cases, the user would
* probably want w==h==k, but that isn't a requirement.
*/
-int *divvy_rectangle(int w, int h, int k, random_state *rs)
+static int *divvy_internal(int w, int h, int k, random_state *rs)
{
int *order, *queue, *tmp, *own, *sizes, *addable, *removable, *retdsf;
int wh = w*h;
int dir;
if (curr < 0) {
- removable[yx] = 0; /* can't remove if it's not owned! */
+ removable[yx] = FALSE; /* can't remove if not owned! */
+ } else if (sizes[curr] == 1) {
+ removable[yx] = TRUE; /* can always remove a singleton */
} else {
/*
* See if this square can be removed from its
if (j == 0)
break; /* all ominoes are complete! */
j = tmp[random_upto(rs, j)];
+#ifdef DIVVY_DIAGNOSTICS
+ printf("Trying to extend %d\n", j);
+#endif
/*
* So we're trying to expand omino j. We breadth-first
tmpsq = tmp[2*j+1];
if (tmpsq >= 0) {
assert(own[tmpsq] == j);
- own[tmpsq] = -1;
+ own[tmpsq] = -3;
}
/*
for (i = 0; i < wh; i++) {
int dir;
- if (own[order[i]] >= 0)
+ if (own[order[i]] != -1)
continue; /* this square is claimed */
+
+ /*
+ * Special case: if our current omino was size 1
+ * and then had a square stolen from it, it's now
+ * size zero, which means it's valid to `expand'
+ * it into _any_ unclaimed square.
+ */
+ if (sizes[j] == 1 && tmpsq >= 0)
+ break; /* got one */
+
+ /*
+ * Failing that, we must do the full test for
+ * addability.
+ */
for (dir = 0; dir < 4; dir++)
if (addable[order[i]*4+dir] == j) {
/*
* addable to this omino when the omino is
* missing a square. To do this it's only
* necessary to re-check addremcommon.
-~|~ */
+ */
if (!addremcommon(w, h, order[i]%w, order[i]/w,
own, j))
continue;
}
if (dir == 4)
continue; /* we can't add this square to j */
+
break; /* got one! */
}
if (i < wh) {
i = order[i];
/*
+ * Restore the temporarily removed square _before_
+ * we start shifting ownerships about.
+ */
+ if (tmpsq >= 0)
+ own[tmpsq] = j;
+
+ /*
* We are done. We can add square i to omino j,
* and then backtrack along the trail in tmp
* moving squares between ominoes, ending up
* expanding our starting omino by one.
*/
+#ifdef DIVVY_DIAGNOSTICS
+ printf("(%d,%d)", i%w, i/w);
+#endif
while (1) {
own[i] = j;
+#ifdef DIVVY_DIAGNOSTICS
+ printf(" -> %d", j);
+#endif
if (tmp[2*j] == -2)
break;
i = tmp[2*j+1];
j = tmp[2*j];
+#ifdef DIVVY_DIAGNOSTICS
+ printf("; (%d,%d)", i%w, i/w);
+#endif
}
+#ifdef DIVVY_DIAGNOSTICS
+ printf("\n");
+#endif
/*
* Increment the size of the starting omino.
* FIXME: or should we loop over all ominoes before we
* give up?
*/
+#ifdef DIVVY_DIAGNOSTICS
+ printf("FAIL!\n");
+#endif
retdsf = NULL;
goto cleanup;
}
}
+#ifdef DIVVY_DIAGNOSTICS
+ {
+ int x, y;
+ printf("SUCCESS! Final grid:\n");
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++)
+ printf("%3d", own[y*w+x]);
+ printf("\n");
+ }
+ }
+#endif
+
/*
* Construct the output dsf.
*/
}
#ifdef TESTMODE
+static int fail_counter = 0;
+#endif
+
+int *divvy_rectangle(int w, int h, int k, random_state *rs)
+{
+ int *ret;
+
+ do {
+ ret = divvy_internal(w, h, k, rs);
+
+#ifdef TESTMODE
+ if (!ret)
+ fail_counter++;
+#endif
+
+ } while (!ret);
+
+ return ret;
+}
+
+#ifdef TESTMODE
/*
* gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
int main(int argc, char **argv)
{
int *dsf;
- int i, successes;
+ int i;
int w = 9, h = 4, k = 6, tries = 100;
random_state *rs;
if (argc > 4)
tries = atoi(argv[4]);
- successes = 0;
for (i = 0; i < tries; i++) {
- dsf = divvy_rectangle(w, h, k, rs);
- if (dsf) {
- int x, y;
+ int x, y;
- successes++;
-
- for (y = 0; y <= 2*h; y++) {
- for (x = 0; x <= 2*w; x++) {
- int miny = y/2 - 1, maxy = y/2;
- int minx = x/2 - 1, maxx = x/2;
- int classes[4], tx, ty;
- for (ty = 0; ty < 2; ty++)
- for (tx = 0; tx < 2; tx++) {
- int cx = minx+tx, cy = miny+ty;
- if (cx < 0 || cx >= w || cy < 0 || cy >= h)
- classes[ty*2+tx] = -1;
- else
- classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx);
- }
- switch (y%2 * 2 + x%2) {
- case 0: /* corner */
- /*
- * Cases for the corner:
- *
- * - if all four surrounding squares
- * belong to the same omino, we print a
- * space.
- *
- * - if the top two are the same and the
- * bottom two are the same, we print a
- * horizontal line.
- *
- * - if the left two are the same and the
- * right two are the same, we print a
- * vertical line.
- *
- * - otherwise, we print a cross.
- */
- if (classes[0] == classes[1] &&
- classes[1] == classes[2] &&
- classes[2] == classes[3])
- printf(" ");
- else if (classes[0] == classes[1] &&
- classes[2] == classes[3])
- printf("-");
- else if (classes[0] == classes[2] &&
- classes[1] == classes[3])
- printf("|");
- else
- printf("+");
- break;
- case 1: /* horiz edge */
- if (classes[1] == classes[3])
- printf(" ");
- else
- printf("--");
- break;
- case 2: /* vert edge */
- if (classes[2] == classes[3])
- printf(" ");
+ dsf = divvy_rectangle(w, h, k, rs);
+ assert(dsf);
+
+ for (y = 0; y <= 2*h; y++) {
+ for (x = 0; x <= 2*w; x++) {
+ int miny = y/2 - 1, maxy = y/2;
+ int minx = x/2 - 1, maxx = x/2;
+ int classes[4], tx, ty;
+ for (ty = 0; ty < 2; ty++)
+ for (tx = 0; tx < 2; tx++) {
+ int cx = minx+tx, cy = miny+ty;
+ if (cx < 0 || cx >= w || cy < 0 || cy >= h)
+ classes[ty*2+tx] = -1;
else
- printf("|");
- break;
- case 3: /* square centre */
- printf(" ");
- break;
+ classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx);
}
+ switch (y%2 * 2 + x%2) {
+ case 0: /* corner */
+ /*
+ * Cases for the corner:
+ *
+ * - if all four surrounding squares belong
+ * to the same omino, we print a space.
+ *
+ * - if the top two are the same and the
+ * bottom two are the same, we print a
+ * horizontal line.
+ *
+ * - if the left two are the same and the
+ * right two are the same, we print a
+ * vertical line.
+ *
+ * - otherwise, we print a cross.
+ */
+ if (classes[0] == classes[1] &&
+ classes[1] == classes[2] &&
+ classes[2] == classes[3])
+ printf(" ");
+ else if (classes[0] == classes[1] &&
+ classes[2] == classes[3])
+ printf("-");
+ else if (classes[0] == classes[2] &&
+ classes[1] == classes[3])
+ printf("|");
+ else
+ printf("+");
+ break;
+ case 1: /* horiz edge */
+ if (classes[1] == classes[3])
+ printf(" ");
+ else
+ printf("--");
+ break;
+ case 2: /* vert edge */
+ if (classes[2] == classes[3])
+ printf(" ");
+ else
+ printf("|");
+ break;
+ case 3: /* square centre */
+ printf(" ");
+ break;
}
- printf("\n");
}
printf("\n");
- sfree(dsf);
}
+ printf("\n");
+ sfree(dsf);
}
- printf("%d successes out of %d tries\n", successes, tries);
+ printf("%d retries needed for %d successes\n", fail_counter, tries);
return 0;
}
~mdw / sgt / puzzles / blobdiff